Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Constant-round interactive-proofs for delegating computations

Ron Rothblum
Massachusetts Institute of Technology
February 1, 2016
Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds.

Toward the KRW conjecture: cubic lower bounds via communication complexity

Or Meir
University of Haifa
December 14, 2015
One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected" with respect to the composition of functions. They showed that this conjecture, if proved, would imply super-polynomial formula lower bounds.

Ramanujan coverings of graphs

Doron Puder
Member, School of Mathematics
December 8, 2015
Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a $d$-covering which is also Ramanujan. This generalizes the $d = 2$ case, a recent major breakthrough in the subject due to Marcus, Spielman and Srivastava. The main tools we use are the Peter-Weyl theory in group representations, as well as the theory of interlacing polynomials. All notions will be explained. Joint work with Chris Hall and Will Sawin.

Bias vs low rank of polynomials with applications to list decoding and effective algebraic geometry

Abhishek Bhowmick
University of Texas at Austin
December 7, 2015
Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields.

Rigidity of random Toeplitz matrices with an application to depth three circuits

Avishay Tal
Member, School of Mathematics
December 1, 2015
Joint work with Oded Goldreich. We prove that random $n$-by-$n$ Toeplitz matrices over $GF(2)$ have rigidity $\Omega(n^3/(r^2 \log n))$ for rank $r > \sqrt{n}$, with high probability. This improves, for $r = o(n / \log n \log\log n)$, over the $\Omega( (n^2 / r) \cdot \log(n/r) )$ bound that is known for many explicit matrices.

Lower bounds on the size of semidefinite programming relaxations

David Steurer
Cornell University
November 30, 2015
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^{\delta}}$, for some constant $\delta > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

General systems of linear forms: equidistribution and true complexity

Pooya Hatami
Member, School of Mathematics
November 24, 2015
Higher-order Fourier analysis is a powerful tool that can be used to analyse the densities of linear systems (such as arithmetic progressions) in subsets of Abelian groups. We are interested in the group $\mathbb{F}_p^n$, for fixed $p$ and large $n$, where it is known that analysing these averages reduces to understanding the joint distribution of a family of sufficiently pseudorandom (formally, high rank) nonclassical polynomials applied to the corresponding system of linear forms.

Advances on Ramsey numbers

Jacob Fox
Stanford University
November 23, 2015
Ramsey theory refers to a large body of deep results in mathematics whose underlying philosophy is captured succinctly by the statement that "Every very large system contains a large well-organized subsystem." Ramsey numbers capture how very large the system should be in order for this to be true. Despite much attention, Ramsey numbers are generally not well understood. This talk will discuss some major problems and recent advances in this area.