Computer Science and Discrete Mathematics (CSDM)

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...

In this talk, I'll describe connections between the unique games conjecture (or more precisely, the closely relatedly problem of small-set expansion) and the quantum separability problem. Remarkably, not only are the problems related, but the...

We will discuss space and parallel complexity, ranging from some classical results which motivated the study, to some recent results concerning combinatorial lower bounds in restricted settings. We will highlight some of their connections to boolean...

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...

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...

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) eps is 1−H(eps). This means that one can reliably communicate n bits by...

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...