Computer Science and Discrete Mathematics (CSDM)

Around 1992, Aldous made the following bold conjecture. Let A be any set of transpositions in the symmetric group Sym(N). Then the spectral gap of the Cayley graph Cay(Sym(N),A) is identical to that of a relatively tiny N-vertex graph defined by A...

In this talk, I will describe our construction of the first explicit lossless vertex expanders. These are graphs where every small subset of vertices has about as many neighbors as their sparsity allows. Previously, the strongest known explicit...

Around 1992, Aldous made the following bold conjecture. Let A be any set of transpositions in the symmetric group Sym(N). Then the spectral gap of the Cayley graph Cay(Sym(N),A) is identical to that of a relatively tiny N-vertex graph defined by A...

In the NISQ era, where noise limits device coherence times, we are fundamentally constrained to shallow quantum computation. This talk will explore the power, limitations, and learnability of the QAC0

circuit class--i.e. the family of constant-depth...

In this talk, I will begin with a quick primer to parameterized complexity, present some key insights from recent hardness of approximation results in the area, and end with a proof sketch of the following result: Assuming the Exponential Time...

In 1984 W. B. Johnson and J. Lindenstrauss showed that a random projection of an arbitrary point set S into low-dimensional space is approximately distance-preserving, as long as S is of size at most exponential in the target dimension. The...

In this talk, we will discuss new algorithms for solving instances of random and semirandom planted constraint satisfaction problems (CSPs). Random CSP are generated by first choosing a solution x and then sampling constraints so that x satisfies...

In this work, we develop a new method for proving lower bounds for static data structures in the classical cellprobe model of Yao. Our methods give the strongest known lower bounds for any explicit problem in this model (quadratically stronger for...

I will talk about the well known relation between cocycles and covers.  Then, I will discuss the relation of cocycle expansion to approximate covers, and finally how these show up in low-soundness PCP agreement tests.

What is the cost of a task if we have to perform it many times? Can we achieve economies of scale? Such "direct-sum problems" play a central role in many areas of mathematics, physics and computer science. Protagonistic problems of this kind are...