Computer Science and Discrete Mathematics (CSDM)

The Brunn-Minkowski inequality is a fundamental result in convex geometry controlling the volume of  the sum of subsets of ℝn. It asserts that for  sets A,B⊂ℝn of equal volume and a parameter t∈(0,1), we have |tA+(1−t)B|≥|A| with equality iff A=B is...

Tree decompositions, and in particular path decompositions, are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”...

The Brunn-Minkowski inequality is a fundamental result in convex geometry controlling the volume of  the sum of subsets of ℝn. It asserts that for  sets A,B⊂ℝn of equal volume and a parameter t∈(0,1), we have |tA+(1−t)B|≥|A| with equality iff A=B is...

Recent advancements in quantum error correction have led to breakthroughs in good quantum low-density parity-check (qLDPC) codes, which offer asymptotically optimal code rates and distances. However, several open questions remain, including the...

In this talk, I will elaborate on the main technical component of our PCP—the construction of routing protocols on high-dimensional expanders (HDX) that can withstand a constant fraction of edge corruptions. We consider the following routing problem...

The theory of probabilistically checkable proofs (PCPs) shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. The PCP Theorem [ALMSS] is a...

I will discuss the Hanna Neumann conjecture of the 1950's and some tools in graph theory that I used to solve it.  The tools include sheaf theory on graphs, Galois theory for graphs, and the preservation of "local properties" under base change (for...

Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved.  What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving...

The well-known Zig-Zag product and related graph operators, like derandomized squaring, are fundamentally combinatorial in nature. Classical bounds on their behavior often rely on a mix of combinatorics and linear algebra. However, these traditional...

The well-known Zig-Zag product and related graph operators, like derandomized squaring, are fundamentally combinatorial in nature. Classical bounds on their behavior often rely on a mix of combinatorics and linear algebra. However, these traditional...