Theory of Computation Group

Spring 2022

• February 22, 2022 Dor Minzer (MIT) On global hypercontractivity and optimal testing of Reed-Muller codes. Abstract: Reed-Muller codes are an important family of error correcting codes that plays a crucial role in a number of results in theoretical computer science. For the field of size $q$ and degree $d$, it was proved [Bhattacharyya et al., Haramaty et al.] that the corresponding Reed-Muller code is testable with $C_q * q^{d}/\eps$ queries. We give a new, more natural proof of this result that achieves a better dependency of C_q on the field size q -- from a tower-type bound to a polynomial bound. Our proof applies more generally to the setting of affine lifted codes, and uses the notion of global hypercontractivity, a recent generalization of classical hypercontractive inequalities. In this talk, we will give a gentle introduction to the concept of global hypercontractivity, and explain the relation of the to the problem of optimal testing of Reed-Muller codes. Based on a joint work with Tali Kaufman.
• March 8, 2022 Tom Gur (DCS) Worst-Case to Average-Case Reductions via Additive Combinatorics We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O(T \log T) that are correct *on all* inputs. Using our framework, we obtain such efficient worst-case to average-case reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem. Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma. Joint work with Vahid Asadi, Alexander Golovnev, and Igor Shinkar (to be presented at STOC ’22).
• March 15, 2022 Omri Weinstein (Hebrew U & Columbia U) The Role of Dynamic Data Structures in Optimization Many continuous optimization tasks in both convex and non-convex settings, rely on iterative path following methods. For over a century, optimization research was mainly focused on understanding and minimizing the rate of convergence of gradient methods. By contrast, the last ~3 years have witnessed the vast potential of dynamic data structures in reducing the cost-per-iteration of Newton-type algorithms (e.g., Interior-Point methods), leading to major recent breakthroughs, from linear and semidefinite programming, to max-flows and neural-network training. In the first part of this talk, I will give a brief overview of this framework, and the role of dynamic randomized linear algebra in solving LPs in (almost) matrix-multiplication time. The second part of the talk will focus on the key primitive of the above framework, namely, dynamic approximate linear-systems, where rows of a (tall) n x d data matrix arrive online one-by-one, and the goal is to maintain an \eps-approximate solution to the least-squares regression (LSR) estimator. Our main result is a dynamic data structure which maintains an arbitrarily small constant approximate solution to dynamic LSR, with amortized update time ~O(d), almost matching the *static* (sketching-based) solution. By contrast, for exact (or even 1/poly(n)-accuracy) solutions, we show a separation between the static and dynamic settings, namely, that dynamic LSR requires ~Ω(d^2) amortized update time under the "OMv Conjecture" [Henzinger et al., 2015]. Based on joint works with my students (Shunhua Jiang, Binghui Peng, Bento Natura, Hengjie Zhang and Zhao Song).
• March 22, 2022 Eliad Tsfadia (TAU) On the Complexity of Two-Party Differential Privacy In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS '10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using public-key cryptography primitives. We prove that the use of public-key cryptography is necessary for bypassing the limitation of McGregor et al., showing that a non-trivial solution for the inner-product, or the Hamming distance, implies the existence of a key-agreement protocol. Our bound implies a combinatorial proof for the fact that non-Boolean inner product of independent (strong) Santha-Vazirani sources is a good condenser. We obtain our main result by showing that the inner-product of a (single, strong) SV source with a uniformly random seed is a good condenser, even when the seed and source are dependent. Joint work with Iftach Haitner, Noam Mazor, and Jad Silbak (to be presented at STOC ’22).
• April 5, 2022 Noga Ron-Zewi (Haifa University) Highly-efficient Interactive Oracle Proofs & Cryptographic Applications Interactive oracle proofs (IOPs) extend the classic notion of probabilistically-checkable proofs (PCPs) by allowing a verifier to interact with a prover over a small number of rounds, while querying the prover’s messages in only a few locations. A recent line of work gave highly-efficient IOPs bypassing state-of-the-art PCPs, for example, constant-round and constant-query IOPs with only a linear (and even approaching the witness length) amount of communication, as well as IOPs with linear-time prover complexity. These constructions were leveraged in turn to obtain highly-efficient succinct arguments and zero-knowledge proofs. The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code. In the talk I will survey these highly-efficient IOP constructions, and their cryptographic applications. Based on Joint works with Ron Rothblum, appearing in FOCS 2020, and to appear in FOCS 2022.
• April 12, 2022 Ron Rothblum (Technion) Multi-Collision-Resistance => Collision-Resistance Collision-resistant hash functions (CRH) are shrinking functions for which it is computationally hard to find collisions (even though collisions are abundant). Several recent works have studied a relaxation of CRH called t-way multi-collision-resistance (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision (even though (t-1)-way collisions may be easy to find). Multi-collision-resistance seems to be a qualitatively weaker property than standard collision-resistance. Nevertheless, in this work we show a non-blackbox transformation of any moderately shrinking t-MCRH, for $t \in \{3,4\}$, into an (infinitely often secure and non-uniform) CRH. This transformation is non-constructive -- we can prove the existence of a CRH but cannot explicitly point out a construction. Joint work with Prashant Vasudevan.
• April 26, 2022 Mika Goos (Technion) TFNP: Collapses, separations and characterizations We discuss a range of results for total NP search problem classes (TFNP) that includes new collapses of classes, black-box separations, and characterisations using propositional proof systems. We will focus on a surprising collapse result, EoPL = PLS ∩ PPAD, and see its full proof. Joint work with Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao.
• May 3, 2022 Edward A. Hirsch (St. Petersburg) Expanding the hub and spoke model We consider algebraic and semialgebraic proof systems. It turns out that the equivalence between algebraic and semialgebraic proofs represented by circuits is tightly connected to refuting the bit value principle (BVP): $\sum x_i2^i = -1$. We relate the complexity of BVP to previously known conjectures in algebraic complexity. The talk is based on: Y.Alekseev, D.Grigoriev, E.A.Hirsch, I.Tzameret. Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative? STOC-2020.
• May 10, 2022 Omri Shmueli (TAU) Public-Key Quantum Money with a Classical Bank Quantum money is a main primitive in quantum cryptography, that enables a bank to distribute to parties in the network, called wallets, unclonable quantum banknotes that serve as a medium of exchange between wallets. While quantum money suggests a theoretical solution to some of the fundamental problems in currency systems, it still requires a strong model to be implemented; quantum computation and a quantum communication infrastructure. A central open question in this context is whether we can have a quantum money scheme that uses “minimal quantumness”, namely, local quantum computation and only classical communication. Public-key semi-quantum money (Radian and Sattath, AFT 2019) is a quantum money scheme where the algorithm of the bank is completely classical, and quantum banknotes are publicly verifiable on any quantum computer. In particular, such scheme relies on local quantum computation and only classical communication. The only known construction of public-key semi-quantum is based on quantum lightning (Zhandry, EUROCRYPT 2019), which is based on a computational assumption that is now known to be broken. In this work, we construct public-key semi-quantum money, based on quantum-secure indistinguishability obfuscation and the sub-exponential hardness of the Learning With Errors problem. The technical centerpiece of our construction is a new 3-message protocol, where a classical computer can delegate to a quantum computer the generation of a quantum state that is both, unclonable and publicly verifiable.
• May 17, 2022 Roni Con (TAU) Reed-Solomon Codes Against Adversarial Insertions and Deletions The task of constructing Reed-Solomon that can handle insertions and deletions has received a lot of attention recently. In this work, we prove that there are Reed-Solomon codes that achieve the half-Singleton bound. In other words, there are optimal Reed-Solomon codes also against insdel errors. We also give a set of evaluation points that define a Reed-Solomon code that achieves this bound. As the field size that we get grows very fast, our construction runs in polynomial time only for very small values of $k$, the dimension of the code. We also explicitly construct two-dimensional Reed-Solomon codes over a field of size $O(n^4)$ that can correct from $n-3$ insdel errors. Earlier constructions required an exponential field size. Joint work with Amir Shpilka and Zachi Tamo
• May 24, 2022 David Levit-Gurevitch (Starkware) ECFFT: Elliptic Curve Fast Fourier Transform Abstract: For smooth finite fields Fq (i.e., when q−1 factors into small primes) the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and Reed-Solomon encoding. However, the same operations over fields with no smooth order root of unity suffer from an asymptotic slowdown. A new approach generalizes the basic idea by replacing the group of roots of unity with a subgroup of an elliptic curve. The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse-Weil interval [q+1±2√q] and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. Compare this with multiplicative subgroups whose order must divide q−1.
• May 31, 2022 Klim Efremenko (BGU) Binary Codes with Resilience Beyond 1/4 via Interaction In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error-correcting code. As it is long known that the distance of binary codes is at most 1/2, reliable transmission is possible only if the channel corrupts (flips) at most a 1/4-fraction of the communicated bits. We revisit the reliable transmission problem in the two-way setting, where both Alice and Bob can send bits to each other. Our main result is the construction of two-way error-correcting codes that are resilient to a constant fraction of corruptions strictly larger than 1/4. Moreover, our code has a constant rate and requires Bob to only send one short message. Curiously, our new two-way code requires a fresh perspective on classical error-correcting codes: While classical codes have only one distance guarantee for all pairs of codewords (i.e., the minimum distance), we construct codes where the distance between a pair of codewords depends on the ``compatibility'' of the messages they encode. We also prove that such codes are necessary for our result. Joint work with Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang
• June 07, 2022 Tal Yankovich (TAU) Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring Abstract: In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted codeword. An RLDC, however, is allowed to abort when identifying corruption. The natural analog to locally correctable codes, dubbed relaxed locally correctable codes (RLCC), was introduced by Gur, Ramnarayan and Rothblum (ITCS 2018) who constructed asymptotically-good length-n RLCC and RLDC with (logn)^O(log(log(n))) queries. In this work we construct asymptotically-good RLDC and RLCC with an improved query complexity of (logn)^O(log(log(log(n)))). To achieve this, we devise a mechanism--an alternative to the tensor product--that squares the length of a given code. Compared to the tensor product that was used by Gur et al. and by many other constructions, our mechanism is significantly more efficient in terms of rate deterioration, allowing us to obtain our improved construction. Based on a joint work with Gil Cohen.