Blackboard, Winslow Homer (1877)

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 1-2 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.


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, PCP-like 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 nearly-tight. In particular, for the first three problems we obtain nearly-polynomial factors of $2^{(\log n)^{1-o(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 re-look 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 two-player 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 Ben-Sasson (Technion) The quest for concretely efficient "PCP-based" 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 "post-quantum 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 "PCP-based" ZK proofs.
  • May 23, 2017 Amnon Ta-Shma (TAU) Explicit, Almost Optimal, Epsilon-Balanced Codes The question of finding an epsilon-biased 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 Gilbert-Varshamov 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 Gilbert-Varshamov 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 Gilbert-Varshamov 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 Gilbert-Varshamov bound (which is the best rate-distance tradeoff known for general binary error-correcting codes). Our constructions use a number of ingredients: Thommesen's random concatenation technique, the Guruswami-Sudan-Indyk strategy for list-decoding concatenated codes, the Alon-Edmonds-Luby distance amplification method, and the local list-decodability and local testability of Reed-Muller 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 Ron-Zewi 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 super-polynomial 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 k-wise indistinguishable if their marginal distributions over any subset of k symbols are identical and that a function f
    is epsilon-fooled by k-wise indistinguishability if f cannot distinguish with advantage epsilon between any two k-wise 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 k-wise indistinguishability. This is closely related to the approximate degree of f (the degree necessary of real-valued 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 trade-offs 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 non-entangled 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 d-cover
    (a.k.a. d-lift) 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.