Author name cluster

Avishay Tal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers

1 author row

STOC Conference 2025 Conference Paper

Quantum-Computable One-Way Functions without One-Way Functions

William Kretschmer
Luowen Qian
Avishay Tal

We construct a classical oracle relative to which P = NP but quantum-computable quantum-secure trapdoor one-way functions exist. This is a substantial strengthening of the result of Kretschmer, Qian, Sinha, and Tal (STOC 2023), which only achieved single-copy pseudorandom quantum states relative to an oracle that collapses NP to P . For example, our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes relative to an oracle on which P = NP . Hence, in our new relativized world, classical computers live in ”Algorithmica” whereas quantum computers live in ”Cryptomania,” using the language of Impagliazzo’s worlds. Our proof relies on a new distributional block-insensitivity lemma for AC 0 circuits, wherein a single block is resampled from an arbitrary distribution.

STOC Conference 2024 Conference Paper

The Power of Adaptivity in Quantum Query Algorithms

Uma Girish
Makrand Sinha
Avishay Tal
Kewen Wu 0001

Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with r versus r −1 rounds of adaptivity. We do so by using the k -fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP’18). For k =2 r , this problem can be solved using an r round quantum algorithm with only one query per round, yet we show that any r −1 round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round. Our results are proven following the Fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the Fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.

STOC Conference 2023 Conference Paper

Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees

Pooya Hatami
William M. Hoza
Avishay Tal
Roei Tell

For any n ∈ ℕ and d = o (loglog( n )), we prove that there is a Boolean function F on n bits and a value γ = 2 −Θ( d ) such that F can be computed by a uniform depth-( d + 1) AC 0 circuit with O ( n ) wires, but F cannot be computed by any depth- d TC 0 circuit with n 1 + γ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth d > 2, which were previously known only for functions outside AC 0 such as the parity function. Furthermore, in our result, the AC 0 circuit computing F is a monotone *read-once formula* (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage n −γ . At a high level, our proof strategy combines two prominent approaches in circuit complexity from the last decade: The celebrated *random projections* method of Håstad, Rossman, Servedio, and Tan (J. ACM 2017), which was previously used to show a tight average-case depth hierarchy for AC 0 ; and the line of works analyzing the effect of *random restrictions* on threshold circuits. We show that under a modified version of Håstad, Rossman, Servedio, and Tan’s projection procedure, any depth- d threshold circuit with n 1 + γ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth d + 1 maintains structure.

FOCS Conference 2023 Conference Paper

Fourier Growth of Communication Protocols for XOR Functions

Uma Girish
Makrand Sinha
Avishay Tal
Kewen Wu 0001

The level-k $\ell_{1}$-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations. In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol $\mathcal C$ computes an XOR function, then $\mathcal{C}(x, y)$ is a function of the parity $x \oplus y$. This motivates us to analyze the XOR-fiber of the communication protocol $\mathcal{C}$, defined as $h(z): =\mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}}[\mathcal{C}(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \oplus \boldsymbol{y}=z]$. We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight $O(\sqrt{d})$ bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an $d^{3 / 2} \cdot \operatorname{polylog}(n)$ bound, which improves the previous $O\left(d^{2}\right)$ bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem. Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.

STOC Conference 2023 Conference Paper

Quantum Cryptography in Algorithmica

William Kretschmer
Luowen Qian
Makrand Sinha
Avishay Tal

We construct a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of pseudorandom states in ”Algorithmica,” and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of P vs. NP in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states. We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which P = NP but BQP ≠ QCMA , based on hardness of the OR ∘ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against AC 0 circuits. This variant may be of independent interest.

FOCS Conference 2023 Conference Paper

Tight Time-Space Lower Bounds for Constant-Pass Learning

Xin Lyu 0002
Avishay Tal
Hongxun Wu
Junzhao Yang

In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS’16, JACM’19]. A line of work that followed extended this result to a large class of learning problems. Until recently, all these results considered learning in the streaming model, where each sample is drawn independently, and the learner is allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC’19] considered a stronger model, allowing multiple passes over the stream. In the 2-pass model, they showed that learning parities of size n requires either a memory of size $n^{1. 5}$ or at least $2^{\sqrt{n}}$ samples. (Their result also generalizes to other learning problems.) In this work, for any constant q, we prove tight memory-sample lower bounds for any parity learning algorithm that makes q passes over the stream of samples. We show that such a learner requires either $\Omega\left(n^{2}\right)$ memory size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower bound, this is the first nontrivial lower bound for q-pass learning for any $q \geq 3$. Similar to prior work, our results extend to any learning problem with many nearly-orthogonal concepts. We complement the lower bound with an upper bound, showing that parity learning with q passes can be done efficiently with $O\left(n^{2} / \log q\right)$ memory.

FOCS Conference 2023 Conference Paper

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

Lijie Chen 0001
William M. Hoza
Xin Lyu 0002
Avishay Tal
Hongxun Wu

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs fool width-3 programs, constant-width regular programs, and unbounded-width permutation programs with a single accepting vertex. In all three cases, the seed length is $\widetilde{O}(\log n \cdot \sqrt{\log (1 / \varepsilon)}+\log (1 / \varepsilon))$, where n is the length of the program and $\varepsilon$ is the error of the WPRG. For comparison, for all three of these models, the best explicit unweighted PRGs known have seed length $\widetilde{O}(\log n$. $\log (1 / \varepsilon)$) (Meka, Reingold, and Tal STOC 2019; Braverman, Rao, Raz, and Yehudayoff SICOMP 2014; Hoza, Pyne, and Vadhan ITCS 2021). Our WPRG seed length is superior when $\varepsilon$ is small. For the case of unbounded-width permutation programs, Pyne and Vadhan previously constructed a WPRG with a seed length that is similar to ours (CCC 2021), but their seed length has an extra additive $\log ^{3 / 2} n$ term, so our WPRG is superior when $\varepsilon \gg 1 / n$. Our results are based on a new, general framework for error reduction. Our framework builds on the remarkable recent work by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) that gave a near-logarithmic space algorithm for estimating random walk probabilities in Eulerian digraphs with high precision. Our framework centers around the “inverse analysis” of random walks and a key combinatorial structure termed “shortcut graphs. ” Using our new framework and the recent notion of singular value approximation (Ahmadinejad, Peebles, Pyne, Sidford, and Vadhan arXiv 2023), we also present an alternative, simpler proof of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan’s main theorem. Compared to the original proof, our new proof avoids much of the sophisticated machinery that was imported from recent work on fast Laplacian solvers.

STOC Conference 2021 Conference Paper

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem

Scott Aaronson
Shalev Ben-David
Robin Kothari
Shravas Rao
Avishay Tal

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(adeg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function. D(f) = O(Q(f)^4): The deterministic query complexity of f is at most quartic in the quantum query complexity of f. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa–Karp–Rosenberg conjecture. We show that if f is a nontrivial monotone graph property of an n -vertex graph specified by its adjacency matrix, then Q(f)=Ω(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Θ(√n).

FOCS Conference 2021 Conference Paper

Fooling Constant-Depth Threshold Circuits (Extended Abstract)

Pooya Hatami
William M. Hoza
Avishay Tal
Roei Tell

We present new constructions of pseudorandom generators (PRGs) for two of the most widely studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ and $n^{1+\delta}$ wires, where $\delta=2^{-O(d)}$, using seed length $O(n^{1-\delta})$ and with error $2^{-n^{\delta}}$. This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-analysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds. Our second contribution is a PRG for De Morgan formulas of size $s$ whose seed length is $s^{1/3+o(1)}\cdot\text{polylog}(1/\epsilon)$ for error $\epsilon$. In particular, our PRG can fool formulas of sub-cubic size $s=n^{3-\Omega(1)}$ with an exponentially small error $\epsilon=\exp(-n^{\Omega(1)})$. This significantly improves the inverse-polynomial error of the previous state-of-the-art for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currently-known lower bounds for this class. In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a non-natural “hybrid computational model” that combines several computational models. As part of our proofs we also construct “extremely low-error” PRGs for related circuit classes; for example, we construct a PRG for arbitrary functions of $s$ LTFs that can handle even the extreme setting of parameters $s=n/\text{polylog}(n)$ and $\epsilon=2^{-n/\text{polylog}(n)}$.

FOCS Conference 2020 Conference Paper

Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs

Amey Bhangale
Prahladh Harsha
Orr Paradise
Avishay Tal

We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the row of each query and the other determining the column. We construct PCPs that are efficient, short, smooth and (almost-)rectangular. As a key application, we show that proofs for hard languages in NTIME(2 n ), when viewed as matrices, are rigid infinitely often. This strengthens and simplifies a recent result of Alman and Chen [FOCS, 2019] constructing explicit rigid matrices in FNP. Namely, we prove the following theorem: : There is a constant δ ∈ (0, 1) such that there is an FNP-machine that, for infinitely many N, on input 1 N outputs N×N matrices with entries in F 2 that are δN 2 -far (in Hamming distance) from matrices of rank at most 2 logN/Ω(loglogN). Our construction of rectangular PCPs starts with an analysis of how randomness yields queries in the Reed-Muller-based outer PCP of Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan [SICOMP, 2006; CCC, 2005]. We then show how to preserve rectangularity under PCP composition and a smoothness-inducing transformation. This warrants refined and stronger notions of rectangularity, which we prove for the outer PCP and its transforms.

FOCS Conference 2020 Conference Paper

Towards Optimal Separations between Quantum and Randomized Query Complexities

Avishay Tal

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N 1/2+Ω(1) separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2 O(k) queries to the inputs. 2)Requires at least ~Ω(N 2(k-1)/(3k-1) ) queries for any randomized algorithm. For any constant, this gives a O(1) vs. N 1/2-ε separation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N 1-ε separations between the quantum and randomized query complexities of partial Boolean functions.

STOC Conference 2019 Conference Paper

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Adam Bene Watts
Robin Kothari
Luke Schaeffer
Avishay Tal

Recently, Bravyi, Gosset, and Konig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.

STOC Conference 2019 Conference Paper

Oracle separation of BQP and PH

Ran Raz
Avishay Tal

We present a distribution D over inputs in {−1,1} 2 N , such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O (log N ), that distinguishes between D and the uniform distribution with advantage Ω(1/log N ). (2) No Boolean circuit of quasi-polynomial size and constant depth distinguishes between D and the uniform distribution with advantage better than polylog ( N )/√ N . By well known reductions, this gives a separation of the classes Promise-BQP and Promise-PH in the black-box model and implies an oracle O relative to which BQP O ⊈ PH O .

STOC Conference 2019 Conference Paper

Pseudorandom generators for width-3 branching programs

Raghu Meka
Omer Reingold
Avishay Tal

We construct pseudorandom generators of seed length Õ(log( n )· log(1/є)) that є-fool ordered read-once branching programs (ROBPs) of width 3 and length n . For unordered ROBPs, we construct pseudorandom generators with seed length Õ(log( n ) · poly (1/є)). This is the first improvement for pseudorandom generators fooling width 3 ROBPs since the work of Nisan [Combinatorica, 1992]. Our constructions are based on the “iterated milder restrictions” approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018]. Two conceptual ideas that play an important role in our analysis are: (1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier. (2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions. In addition, we achieve nearly optimal seed-length Õ(log( n /є)) for the classes of: (1) read-once polynomials on n variables, (2) locally-monotone ROBPs of length n and width 3 (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length n having a layer of width 2 in every consecutive poly log( n ) layers.

STOC Conference 2018 Conference Paper

Extractor-based time-space lower bounds for learning

Sumegha Garg
Ran Raz
Avishay Tal

A matrix M : A × X → {−1,1} corresponds to the following learning problem: An unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, ( a 1 , b 1 ), ( a 2 , b 2 ) …, where for every i , a i ∈ A is chosen uniformly at random and b i = M ( a i , x ). Assume that k , l , r are such that any submatrix of M of at least 2 − k · | A | rows and at least 2 − l · | X | columns, has a bias of at most 2 − r . We show that any learning algorithm for the learning problem corresponding to M requires either a memory of size at least Ω( k · l ), or at least 2 Ω( r ) samples. The result holds even if the learner has an exponentially small success probability (of 2 −Ω( r ) ). In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least Ω((log| X |) · (log| A |)) or an exponential number of samples, achieving a tight Ω((log| X |) · (log| A |)) lower bound on the size of the memory, rather than a bound of Ω(min{(log| X |) 2 ,(log| A |) 2 }) obtained in previous works by Raz [FOCS’17] and Moshkovitz and Moshkovitz [ITCS’18]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on the work of Raz [FOCS’17] that gave a general technique for proving memory samples lower bounds.

STOC Conference 2018 Conference Paper

Improved pseudorandomness for unordered branching programs through local monotonicity

Eshan Chattopadhyay
Pooya Hatami
Omer Reingold
Avishay Tal

We present an explicit pseudorandom generator with seed length Õ((log n ) w +1 ) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n 1/2+ o (1) . A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w read-once, oblivious branching program B :{0,1} n → {0,1}, any k ∈ {1,…, n }, [complex formula not displayed] This settles a conjecture posed by Reingold, Steinke and Vadhan (RANDOM’13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.

SODA Conference 2018 Conference Paper

The Robust Sensitivity of Boolean Functions

Shachar Lovett
Avishay Tal
Jiapeng Zhang

The sensitivity conjecture is one of the central open problems in Boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a Boolean function to moments of its sensitivity. We prove the robust sensitivity conjecture in this work with near optimal parameters.

STOC Conference 2017 Conference Paper

Formula lower bounds via the quantum method

Avishay Tal

A de Morgan formula over Boolean variables x 1 ,…, x n is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires a large formula is a central open question in computational complexity. While we believe that some explicit functions require exponential formula size, currently the best lower bound for an explicit function is the Ω( n 3 ) lower bound for Andreev's function. A long line of work in quantum query complexity, culminating in the work of Reichardt [SODA, 2011], proved that for any formula of size s , there exists a polynomial of degree at most O (√ s ) that approximates the formula up to a small point-wise error. This is a classical theorem, arguing about polynomials and formulae, however the only known proof for it involves quantum algorithms. We apply Reichardt result to obtain the following: (1) We show how to trade average-case hardness in exchange for size. More precisely, we show that if a function f cannot be computed correctly on more than 1/2 + 2 - k of the inputs by any formula of size at most s , then computing f exactly requires formula size at least Ω( k ) · s . As an application, we improve the state of the art formula size lower bounds for explicit functions by a factor of Ω(log n ). (2) We prove that the bipartite formula size of the Inner-Product function is Ω( n 2 ). (A bipartite formula on Boolean variables x 1 ,…, x n and y 1 , …, y n is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves can compute any function of either the x or y variables.) We show that any bipartite formula for the Inner-Product modulo 2 function, namely IP ( x , y ) = Σ i =1 n x i y i ( mod 2), must be of size Ω( n 2 ), which is tight up to logarithmic factors. To the best of our knowledge, this is the first super-linear lower bound on the bipartite formula complexity of any explicit function.

STOC Conference 2017 Conference Paper

Time-space hardness of learning sparse parities

Gillat Kol
Ran Raz
Avishay Tal

We define a concept class ℱ to be time-space hard (or memory-samples hard) if any learning algorithm for ℱ requires either a memory of size super-linear in n or a number of samples super-polynomial in n , where n is the length of one sample. A recent work shows that the class of all parity functions is time-space hard [Raz, FOCS'16]. Building on [Raz, FOCS'16], we show that the class of all sparse parities of Hamming weight ℓ is time-space hard, as long as ℓ ≥ ω(log n / loglog n ). Consequently, linear-size DNF Formulas, linear-size Decision Trees and logarithmic-size Juntas are all time-space hard. Our result is more general and provides time-space lower bounds for learning any concept class of parity functions. We give applications of our results in the field of bounded-storage cryptography. For example, for every ωlog n ) ≤ k ≤ n , we obtain an encryption scheme that requires a private key of length k , and time complexity of n per encryption/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses at most o ( nk ) memory bits and the scheme is used at most 2 o ( k ) times. Previously, this was known only for k = n [Raz, FOCS'16].

STOC Conference 2016 Conference Paper

Matrix rigidity of random toeplitz matrices

Oded Goldreich 0001
Avishay Tal

We prove that random n -by- n Toeplitz (alternatively Hankel) matrices over F 2 have rigidity Ω( n 3 / r 2 log n ) for rank r ≥ √ n , with high probability. For r = o ( n /log n · loglog n ), this improves over the Ω( n 2 / r · log( n / r )) bound that is known for many explicit matrices.

FOCS Conference 2014 Conference Paper

Shrinkage of De Morgan Formulae by Spectral Techniques

Avishay Tal

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is 2. Namely, we show that for any Boolean function f: {0, 1} n → {0, 1}, setting each variable out of x1, .. ., xn with probability 1 - p to a randomly chosen constant, reduces the expected formula size of the function by a factor of O(p 2 ). This result is tight and improves the work of Hastad [SIAM J. C. , 1998] by removing logarithmic factors. As a consequence of our results, the function defined by Andreev [MUMB. , 1987], A: {0, 1} n → {0, 1}, which is in P, has formula size at least Ω(n 3/ log 2 n log 3 log n). This lower bound is tight (for the function A) up to the log 3 log n factor, and is the best known lower bound for functions in P. In addition, we strengthen the average-case hardness result of Komargodski et al. ; we show that the functions defined by Komargodski et al. , h r: {0, 1} n → {0, 1}, which are also in P, cannot be computed correctly on a fraction greater than 1/2 + 2 -r of the inputs, by De n 3 Morgan formulae of size at most n 3 /r 2 poly log n, for any parameter r ≤ n 1/3. The proof relies on a result from quantum query complexity by Laplante et al. [CC, 2006], Høyer et al. [STOC, 2007] and Reichardt [SODA, 2011]: for any '/' Boolean function f, Q 2 (f) ≤ O( L(f)), where Q 2 (f) is the bounded-error quantum query complexity of f, and L(f) is the minimal size De Morgan formula computing f.

FOCS Conference 2013 Conference Paper

Improved Average-Case Lower Bounds for DeMorgan Formula Size

Ilan Komargodski
Ran Raz
Avishay Tal

We give an explicit function h: {0, 1} n → {0, 1} such that every deMorgan formula of size n 3-o(1) /r 2 agrees with h on at most a fraction of 1/2+2 -Ω(r) of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013). Our technical contributions include a theorem that shows that the "expected shrinkage" result of Haastad (SIAM J. Comput. , 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), combining ideas of both Impagliazzo, Meka and Zuckerman (FOCS, 2012) and Komargodski and Raz. In addition, using a bit-fixing extractor in the construction of h allows us to simplify a major part of the analysis of Komargodski and Raz 1.