Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

A matrix expander Chernoff bound

Ankit Garg
Microsoft Research
December 10, 2018
Chernoff-type bounds study concentration of sums of independent random variables and are extremely useful in various settings. In many settings, the random variables may not be completely independent but only have limited independence. One such setting, which turns out to be useful in derandomization and theoretical computer science, in general, involves random walks on expanders. I will talk about a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander.

Monotone Circuit Lower Bounds from Resolution

Mika Goos
Member, School of Mathematics
November 27, 2018
For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with F has large monotone circuit complexity. As an application, we show that a monotone variant of XOR-SAT has exponential monotone circuit complexity, which improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988).

Classical Verification of Quantum Computations

Urmila Mahadev
UC Berkeley
November 26, 2018
We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a quantum state. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, non-adaptively measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier.

Introduction to Query-to-Communication Lifting

Mika Goos
Member, School of Mathematics
November 20, 2018
I will survey new lower-bound methods in communication complexity that "lift" lower bounds from decision tree complexity. These methods have recently enabled progress on core questions in communication complexity (log-rank conjecture, classical--quantum separations) and related areas (circuit complexity, proof complexity, LP/SDP formulations). I will prove one concrete lifting theorem for non-deterministic (NP) query/communication models.

Sunflowers and friends

Shachar Lovett
University of California San Diego
November 5, 2018
The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will describe several attempts on how to get improved bounds for it. These will lead to surprising connections with several other combinatorial structures, such as randomness extractors, intersecting families and DNFs.

Based on joint works with Xin Li, Noam Solomon and Jiapeng Zhang.

On the NP-hardness of 2-to-2 Games

Dor Minzer
Member, School of Mathematics
October 30, 2018

The Unique-Games Conjecture is a central open problem in the field of PCP’s (Probabilistically Checkable Proofs) and hardness of approximation, implying tight inapproximability results for wide class of optimization problems. 

We will discuss PCPs, the Unique-Games Conjecture and some recent progress. (no familiarity with PCPs or with last week's talk are needed).