Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Lower bounds for homogeneous depth-5 arithmetic circuits over finite fields

Mrinal Kumar
March 14, 2016
The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth-4 arithmetic circuits. Even though these results seem to come close to resolving the VP vs VNP question, it seems likely that the techniques involved may not be strong enough for this resolution. However, it is conceivable that we might be able to build upon these ideas to show super-polynomial lower bounds for weaker classes of arithmetic circuits, like arithmetic formula or constant depth circuits.

Fast learning requires good memory: a time-space lower bound for parity learning

Ran Raz
Weizmann Institute of Science; Visiting Professor, School of Mathematics
March 8, 2016
We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial. More formally, in the problem of parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random.

Almost optimal sum of squares lower bound for planted clique

Pravesh Kothari
University of Texas, Austin
March 7, 2016
Finding cliques in random graphs and the related planted variant where one wants to recover an added clique of size $k$ added to a random $G(n, 1/2)$ graph, have been extensively studied questions in algorithm design. Despite intense effort, state of the art polynomial time algorithms can find added cliques to random graphs only when $k \gg \sqrt{n}$.This has led to the conjectured hardness of the problem for $k \ll \sqrt{n}$ with many interesting applications.

Graph isomorphism in quasipolynomial time II

László Babai
University of Chicago
March 1, 2016
The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools. In the first talk we outline the algorithm and state the core group theoretic and algorithmic ingredients. Some of the technical details will be given in the second talk, with a focus on the core group theoretic routine ("Local Certificates") and the aggregation of the the local certificates. Time permitting, we also discuss one of the combinatorial partitioning algorithms ("Design lemma").

Graph isomorphism in quasipolynomial time I

László Babai
University of Chicago
February 29, 2016
The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools. In the first talk we outline the algorithm and state the core group theoretic and algorithmic ingredients. Some of the technical details will be given in the second talk, with a focus on the core group theoretic routine ("Local Certificates") and the aggregation of the the local certificates. Time permitting, we also discuss one of the combinatorial partitioning algorithms ("Design lemma").

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.