Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Non-commutative rank

Visu Makam
University of Michigan; Member, School of Mathematics
February 5, 2019

A linear matrix is a matrix whose entries are linear forms in some indeterminates $t_1,\dots, t_m$ with coefficients in some field $F$. The commutative rank of a linear matrix is obtained by interpreting it as a matrix with entries in the function field $F(t_1,\dots,t_m)$, and is directly related to the central PIT (polynomial identity testing) problem. The

Near-Optimal Strong Dispersers

Dean Doron
The University of Texas at Austin
February 4, 2019

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs. 

PCP and Delegating Computation: A Love Story.

Yael Tauman Kalai
Microsoft Research
January 28, 2019

In this talk, I will give an overview on how PCPs, combined with cryptographic tools,
are used to generate succinct and efficiently verifiable proofs for the correctness of computations.
I will focus on constructing (computationally sound) *succinct* proofs that are *non-interactive*
(assuming the existence of public parameters) and are *publicly verifiable*.
In particular, I will focus on a recent result with Omer Paneth and Lisa Yang,
where we show how to construct such proofs for all polynomial time computations,

New Results on Projections

Guy Moshkovitz
Member, School of Mathematics
January 22, 2019

What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan number, Sauer-Shelah Lemma, Kahn-Kalai-Linial Theorem, and more), and is wide open for most settings of the parameters. We essentially settle the question for linear k and sub-exponential m. 

Based on joint work with Noga Alon and Noam Solomon.

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.