Seminars

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even \(n\), there exists an explicit bijection \(f\) from the \(n\)-dimensional Boolean cube to the Hamming ball of...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

Most of the cryptosystems we currently use are highly secure, and cannot be broken with reasonable complexity by mathematical cryptanalysis. However, over the last fifteen years researchers have developed many types of physical attacks on their...

We will discuss interactive coding in the setting where there are n parties attempting to compute a joint function of their inputs using error-prone pairwise communication channels. We will present a general protocol that allows one to achieve only...

We will outline the proof that gives a positive solution of to Weaver's conjecture \(KS_2\). That is, we will show that any isotropic collection of vectors whose outer products sum to twice the identity can be partitioned into two parts such that...

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,\(P \not\subseteq NC_1\) ). This problem is interesting both because it is tightly related to understanding the...

Algebraic geometry and representation theory have played an important role in obtaining lower bounds in algebraic complexity theory. After giving an overview of the general set-up, I will present very recent results that indicate a possible role for...

In a profoundly influential 1948 paper, Claude Shannon defined the entropy function \(H\), and showed that the capacity of a symmetric binary channel with noise rate (bit flip rate) \(\mathrm{eps}\) is \(1-H(\mathrm{eps})\). This means that one can...

Machine learning is often employed as one step in a larger application, serving to perform information extraction or data mining for example. The rules obtained by such learning are then used as inputs to a further analysis. As a consequence of the...

In this talk we will present an overview of the hypermatrix generalization of matrix algebra proposed by Mesner and Bhattacharya in 1990. We will discuss a spectral theorem for hypermatrices deduced from this algebra as well as connections with...