Theory of Computation Seminar
We meet every Tuesday at Schreiber 309.
Light lunch is served from 12:45, and the talk starts at 13:10
and lasts 12 hours (with a 10 minute break).
The seminar also has a mailing list. In order to join or leave the list, fill the form on this page, or contact Dean Doron, the seminar coordinator.
Schedule
Archive of Previous Talks
Spring 2017

July 04, 2017
Aviad Rubinstein (Berkeley)
Distributed PCP Theorems for Hardness of Approximation in P
We present a new model of probabilistically checkable proof (PCP), which we call "Distributed PCP":
A satisfying assignment (x in {0,1}^n) to a CNF formula is shared between two parties (Alice knows x_1, ... x_{n/2}, and Bob knows x_{n/2+1},...,x_n).
Their goal is to jointly write a PCP for x, while exchanging little or no information.
Using our new framework, we obtain, for the first time, PCPlike reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in P.
In particular, we show that (assuming SETH) there are no truly subquadratic approximation algorithms for the following problems:
Maximum Inner Product over {0,1}vectors;
LCS Closet Pair over permutations;
Approximate Partial Match;
Approximate Regular Expression Matching; and
Diameter in Product Metric.
All our inapproximability factors are nearlytight. In particular, for the first three problems we obtain nearlypolynomial factors of $2^{(\log n)^{1o(1)}}$;
only (1+o(1)) SETH lower bounds were known for these problems before our work.
Joint work with Amir Abboud. 
June 27, 2017
Prahladh Harsha (TIFR)
On polynomial approximations to AC0
In this talk, we will discuss some questions related to polynomial
approximations of AC0. A classic result due to Tarui (1991) and
Beigel, Reingold, and Spielman (1991), states that any AC0 circuit of size s
and depth d has an Îµerror probabilistic polynomial over the reals of
degree at most (log(s/Îµ))^{O(d)}. We will have a relook at this construction
and show how to improve the bound to (log s)^{O(d)}â log(1/Îµ), which is
much better for small values of Îµ.
As an application of this result, we show that (log s)^{O(d)}â log(1/Îµ)wise
independence fools AC0, improving on Tal's
strengthening of Braverman's theorem that (log(s/Îµ))^{O(d)}wise
independence fools AC0. Time permitting, we will also discuss some
lower bounds on the best polynomial approximations to AC0; in particular,
we will show that any polynomial approximation of the OR_n function
within constant
error must have degree at least \Omega(\sqrt{\log n}).
[Joint work with Srikanth Srinivasan] 
June 13, 2017
Yuval Filmus (Technion)
Twenty (simple) questions
The twenty questions game is a twoplayer game at the basis of combinatorial search theory.
Alice thinks of a number from 1 to n according to a distribution known to Bob,
and Bob identifies the number by asking Alice several Yes/No questions.
Bob's goal is to minimize the expected number of questions he asks.
Bob's optimal strategy, which is often taught in undergraduate algorithms courses,
uses arbitrary Yes/No questions, which is a bit unrealistic.
What happens if we restrict Bob to a small "repertoire" of questions?
Can we recover the performance of the optimal algorithm with a smaller repertoire?
Joint work with Yuval Dagan (Technion), Ariel Gabizon (Zcash) and Shay Moran (UCSD).  June 06, 2017 Eli BenSasson (Technion) The quest for concretely efficient "PCPbased" Zero Knowledge arguments Probabilistically Checkable Proofs (PCPs) can be used to construct highly efficient zero knowledge (ZK) proof/argument systems for any language in NEXP; these proof systems are "postquantum secure" and "transparent"  verification (and setup) requires only public randomness. This talk surveys the prospects, progress and open questions raised by the quest for concrete and practical "PCPbased" ZK proofs.

May 23, 2017
Amnon TaShma (TAU)
Explicit, Almost Optimal, EpsilonBalanced Codes
The question of finding an epsilonbiased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1\eps}{2}$ and rate close to the GilbertVarshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an explicit $\eps$biased set over $k$ bits with support size $O(\frac{k}{\eps^{2+o(1)}})$. This improves upon all previous explicit constructions which were in the order of $\frac{k^2}{\eps^2}$, $\frac{k}{\eps^3}$ or $\frac{k^{5/4}}{\eps^{5/2}}$. The result is close to the GilbertVarshamov bound which is $O(\frac{k}{\eps^2})$ and the lower bound which is $\Omega(\frac{k}{\eps^2 \logeps})$.
The main technical tool we use is bias amplification with the $s$wide replacement product. The sum of two independent samples from an $\eps$biased set is $\eps^2$ biased. Rozenman and Wigderson showed how to amplify the bias more economically by choosing two samples with an expander. Based on that they suggested a recursive
construction that achieves sample size $O(\frac{k}{\eps^4})$. We show that amplification with a long random walk over the $s$wide replacement product reduces the bias almost optimally. 
May 16, 2017
Swastik Kopparty (Rutgers)
Locally testable and locally correctable codes approaching the GilbertVarshamov bound
We show that there exist binary locally testable codes (for all rates) and locally correctable codes (for low rates) with rate and distance approaching the GilbertVarshamov bound (which is the best ratedistance tradeoff known for general binary errorcorrecting codes). Our constructions use a number of ingredients: Thommesen's random concatenation technique, the GuruswamiSudanIndyk strategy for listdecoding concatenated codes, the AlonEdmondsLuby distance amplification method, and the local listdecodability and local testability of ReedMuller codes. Interestingly, this seems to be the first time that local testability is used in the construction of locally correctable codes.
Joint work with Sivakanth Gopi, Rafael Oliveira, Noga RonZewi and Shubhangi Saraf 
April 25, 2017
Ben Lee Volk (TAU)
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
This talk presents a framework of "algebraically natural lower bounds" for algebraic circuits, which is similar to the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, and captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been little concrete evidence demonstrating that this is a barrier to obtaining superpolynomial lower bounds for general algebraic circuits.
We show that the existence of an algebraic natural proofs barrier is equivalent to the existence of succinct derandomization of the polynomial identity testing problem. That is, whether the coefficient vectors of polylog(N)degree polylog (N)size circuits is a hitting set for the class of poly(N)degree poly(N)size circuits. Further, we give an explicit universal construction showing that if such a succinct hitting set exists, then our universal construction suffices.
We assess the existing literature constructing hitting sets for restricted classes of algebraic circuits and modify some of these constructions to obtain succinct hitting sets, thus suggesting evidence supporting the existence of an algebraic natural proofs barrier.
Our framework is similar to the Geometric Complexity Theory (GCT) program of Mulmuley and Sohoni, except that here we emphasize constructiveness of the proofs while the GCT program emphasizes symmetry. Nevertheless, our succinct hitting sets have relevance to the GCT program as they imply lower bounds for the complexity of the defining equations of polynomials computed by small circuits.
(Joint work with Michael Forbes and Amir Shpilka) 
April 04, 2017
Chris Williamson (CUHK)
Bounded Indistinguishability and the Complexity of Recovering Secrets
Motivated by cryptographic applications, we study the notion of bounded indistinguishability, a natural relaxation of the well studied notion of bounded independence.
We say that two distributions are kwise indistinguishable if their marginal distributions over any subset of k symbols are identical and that a function f
is epsilonfooled by kwise indistinguishability if f cannot distinguish with advantage epsilon between any two kwise indistinguishable distributions X and Y. The well known
case of k wise independence (corresponding to one of the distributions being uniform) can behave very differently from our generalization and we are interested in
characterizing the class of functions that are fooled by kwise indistinguishability. This is closely related to the approximate degree of f (the degree necessary of realvalued polynomials
to approximate the boolean function f to within a constant). Our results imply the first efficient secret sharing schemes with a high security threshold in which
the secret can be reconstructed in AC^0. We also consider a further relaxation  where the marginal distributions of X and Y need only be close in statistical distance instead of identical.
This opens up another set of tradeoffs to consider related to the degree versus size of coefficients of polynomial approximations.
Joint work with Andrej Bogdanov, Yuval Ishai, and Emanuele Viola. 
March 29, 2017
Boaz Barak (Harvard)
Sums of squares, quantum entanglement, and the log rank conjecture
We give an exp(sqrt(n))time algorithm for distinguishing, given a subspace V living in n^2 dimensions, between the case that V contains a rank one matrix and the case that every rank one matrix has a constant fraction of its mass outside V.
The algorithm uses the sum of squares semidefinite programming hierarchy, and is based on a surprising connection to Lovett's bound on the communication complexity of low rank matrices.
One motivation for this problem arises in quantum information theory, where rank one matrices correspond to nonentangled quantum states, though the talk will not assume background knowledge in quantum computing, sum of squares, or communication complexity.
Joint work with Pravesh Kothari and David Steurer. 
March 21, 2017
Doron Puder (TAU)
Interlacing Families of Polynomials and Ramanujan Covers of Graphs
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 dcover
(a.k.a. dlift) which is also Ramanujan. This generalizes the d=2 case,
a recent major breakthrough in the subject due to Marcus, Spielman and
Srivastava (MSS). We use interlacing polynomials which were the key tool for
MSS, and also some classical results in group representations.
All notions will be explained. Joint work with Chris Hall and Will Sawin.  March 14, 2017 Amir Yehudayoff (Technion) Pointer chasing via triangular discrimination We shall see how to use information theory to prove lower bounds for the distributional communication complexity of the pointer chasing problem. A key part of the proof is using triangular discrimination instead of total variation distance; this idea may be useful elsewhere.