Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

The deterministic communication complexity of approximate fixed point

Omri Weinstein
New York University
February 22, 2016
We study the two-party communication complexity of the geometric problem of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions $g \circ f$, where Alice knows $f$ and Bob knows $g$. We prove an essentially tight deterministic communication lower bound on this problem, using a novel adaptation of the Raz-McKenzie simulation theorem into geometric settings, allowing us to "lift" the *query* lower bound of approximate fixed-point ([HPV89]) from the oracle model to the two-party model in a "smooth" fashion.

The singularity of symbolic matrices

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
February 16, 2016
While this lecture is a continuation of the lecture from last Tuesday, I will make it self contained. The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of rational functions). As it happens, this problem has a dual life; when the underlying variables commute, and when they do not.

The singularity of symbolic matrices

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
February 9, 2016
The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of rational functions). As it happens, this problem has a dual life; when the underlying variables commute, and when they do not.

Bipartite perfect matching is in quasi-NC

Stephen Fenner
University of South Carolina
February 8, 2016
We show that the bipartite perfect matching problem is in $\textrm{quasi-}\textsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the Isolation Lemma of Mulmuley, Vazirani, & Vazirani, used to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

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.