Blackboard, Winslow Homer (1877)

Theory of Computation Seminar

We meet every Tuesday at Check Point 420.
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 Shir Peleg, the seminar coordinator.


Archive of Previous Talks

Spring 2021

  • March 9, 2021 Tal Yankovitz (Tel Aviv University) Rate Amplification and Query-Efficient Distance Amplification for linear LCC and LDC We show a rate amplification procedure for Locally Correctable Codes (LCC). The procedure converts any $q$-query linear LCC, having rate $\rho$ and, say, constant distance to an asymptotically good LCC with $q^{\poly(1/\rho)}$ queries. We also show a distance amplification procedure for Locally Decodable Codes (LDC) that converts any linear LDC with distance $\delta$ and, say, constant rate to an asymptotically good LDC. The query complexity only suffers a multiplicative overhead that is roughly equal to the query complexity of a length $1/\delta$ asymptotically good LDC. This improves upon the $\poly(1/\delta)$ overhead obtained by the AEL distance amplification procedure by [AL96, AEL95]. As linear LCC are LDC, this establishes that the construction of asymptotically good LDC is reduced, with a minor overhead in query complexity, to the problem of constructing (somewhat) negligible rate, (extremely) negligible distance linear LDC.
  • April 6, 2021 Yuval Filmus (Technion) Bounded indistinguishability for simple sources Suppose that X,Y are two distributions on n bits. What amount of indistinguishability is needed to fool AC^0? If X,Y are arbitrary sources, then sqrt{n}-indistinguishability doesn't even suffice to fool OR. In contrast, if Y is the uniform distribution, then Braverman showed that polylog(n)-indistinguishability suffices to fool all of AC^0. We explore what happens when Y is a simple distribution, say samplable in low degree or locality. Joint work with Andrej Bogdanov & K. Dinesh (CUHK), Yuval Ishai and Avi Kaplan (Technion), and Akshay Srinivasan (TIFR).
  • April 20, 2021 Mika Goos (EPFL) Unambiguous DNFs and Alon-Saks-Seymour We exhibit an unambiguous k-DNF formula that requires CNF width Omega(k^2). As a corollary, we get a near-optimal solution for the Alon-Saks-Seymour problem in graph theory, which asks: How large a gap can there be between the chromatic number of a graph and its biparite packing number? Joint work with Kaspars Balodis, Shalev Ben-David, Siddhartha Jain, and Robin Kothari.
  • April 27, 2021 Dor Minzer (MIT) Optimal tiling of the Euclidean space using permutation-symmetric bodies What is the least surface area of a body $B$ whose $\mathbb{Z}^n$ translations tile $\mathbb{R}^n$? The isoperimetric inequality gives the bound $\Omega(\sqrt{n})$, and remarkably Kindler et al. showed that this is achievable. In this work, we consider permutation-symmetric tilings. We show that in this case the answer is $\Theta(n/\sqrt{\log n})$. Our work is motivated by the study of strong versions of the parallel repetition theorem, which if true would have significant applications. Unfortunately, strong parallel repetition fails in general [Raz]. Our result suggests there may be important special cases where it still applies. Joint work with Mark Braverman.
  • May 4, 2021 Ronen Shaltiel (Haifa University) Uniquely Decodable Codes for Space Bounded Channels We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a $p$ fraction of the bits of the codeword. We show that for every $0
  • May 18, 2021 Tom Gur (University of Warwick) Relaxed sunflower lemmas and locally decodable codes A recent line of work established a connection between a notion of relaxed combinatorial sunflowers and local algorithms in various settings, ranging from property testing and PCPs to learning and coding theory. This talk will survey a couple of these results, and in particular, we will discuss the foregoing notion of relaxed sunflowers and show how it can be used to derive lower bounds on relaxed locally decodable codes, resolving an open problem raised by Goldreich in 2004.
  • June 1, 2021 Ron Rothblum (Technion) Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge) In a seminal work, Goldreich, Micali and Wigderson (JACM, '86) constructed a zero-knowledge protocol for the NP-complete problem of graph 3-colorability. Their base protocol has a large soundness error that can be reduced by repeating the protocol sequentially. A natural idea to save on the round complexity is to instead perform the repetition in *parallel*. In this work we resolve this long standing open question in the negative by showing that parallel repetition of the GMW protocol does *not* preserve zero-knowledge (assuming a standard cryptographic assumption). This result is obtained by making *positive* progress on the question of securely realizing the Fiat-Shamir transform for a much richer class of interactive proofs than was previously known. Joint work with Justin Holmgren and Alex Lombardi
  • June 1, 2021 Clara Shikhelman (ChainCode Labs) Expanding the hub and spoke model When two parties transact often using banks, Bitcoin, or any other financial device that entails fees, they might choose to turn to second-layer solutions. In these solutions, both parties lock a certain amount as escrow in a channel and transact freely with reduced fees. This gives rise to a network of channels in which any two nodes can transact with each other. A downside of these solutions, especially if they are decentralized, is the tendency of the network toward the hub and spoke model. Most nodes in this model, the “spokes”, are connected to a single “hub”, a high degree node that the spokes believe to be well connected. This graph topology is known to be prone to various attacks and privacy issues. In this work, we present a solution that benefits the spokes, by saving on costs, and the network, by giving it higher connectivity and good expansion properties. We use probabilistic and spectral techniques for the proofs.