All reports by Author Avishay Tal:

__
TR21-046
| 22nd March 2021
__

Uma Girish, Avishay Tal, Kewen Wu#### Fourier Growth of Parity Decision Trees

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

Revisions: 1

__
TR21-004
| 10th January 2021
__

Vishnu Iyer, Avishay Tal, Michael Whitmeyer#### Junta Distance Approximation with Sub-Exponential Queries

__
TR21-002
| 8th January 2021
__

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell#### Fooling Constant-Depth Threshold Circuits

Revisions: 1

__
TR20-180
| 2nd December 2020
__

Yuval Filmus, Or Meir, Avishay Tal#### Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathbf{AC}^0$

Revisions: 2

__
TR20-075
| 6th May 2020
__

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal#### Rigid Matrices From Rectangular PCPs

Revisions: 2

__
TR20-066
| 28th April 2020
__

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal#### Quantum Implications of Huang's Sensitivity Theorem

__
TR19-179
| 7th December 2019
__

Avishay Tal#### Towards Optimal Separations between Quantum and Randomized Query Complexities

Revisions: 1

__
TR19-152
| 6th November 2019
__

Uma Girish, Ran Raz, Avishay Tal#### Quantum versus Randomized Communication Complexity, with Efficient Players

__
TR19-089
| 21st June 2019
__

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal#### Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

__
TR19-071
| 14th May 2019
__

Sumegha Garg, Ran Raz, Avishay Tal#### Time-Space Lower Bounds for Two-Pass Learning

__
TR19-018
| 18th February 2019
__

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal#### AC0[p] Lower Bounds against MCSP via the Coin Problem

__
TR18-160
| 12th September 2018
__

Anna Gal, Avishay Tal, Adrian Trejo Nuñez#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

__
TR18-155
| 8th September 2018
__

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal#### Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

__
TR18-112
| 5th June 2018
__

Raghu Meka, Omer Reingold, Avishay Tal#### Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

__
TR18-107
| 31st May 2018
__

Ran Raz, Avishay Tal#### Oracle Separation of BQP and PH

__
TR17-193
| 31st December 2017
__

Oded Goldreich, Avishay Tal#### On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

__
TR17-171
| 6th November 2017
__

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

__
TR17-148
| 6th October 2017
__

Or Meir, Avishay Tal#### The Choice and Agreement Problems of a Random Function

Revisions: 3

__
TR17-121
| 31st July 2017
__

Sumegha Garg, Ran Raz, Avishay Tal#### Extractor-Based Time-Space Lower Bounds for Learning

Revisions: 1

__
TR17-025
| 16th February 2017
__

Pooya Hatami, Avishay Tal#### Pseudorandom Generators for Low-Sensitivity Functions

__
TR16-181
| 15th November 2016
__

Avishay Tal#### The Bipartite Formula Complexity of Inner-Product is Quadratic

__
TR16-179
| 15th November 2016
__

Avishay Tal#### Computing Requires Larger Formulas than Approximating

__
TR16-113
| 22nd July 2016
__

Gillat Kol, Ran Raz, Avishay Tal#### Time-Space Hardness of Learning Sparse Parities

__
TR16-069
| 25th April 2016
__

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson#### Degree and Sensitivity: tails of two distributions

__
TR16-062
| 18th April 2016
__

Avishay Tal#### On The Sensitivity Conjecture

__
TR15-114
| 18th July 2015
__

Avishay Tal#### #SAT Algorithms from Shrinkage

__
TR15-079
| 7th May 2015
__

Oded Goldreich, Avishay Tal#### Matrix Rigidity of Random Toeplitz Matrices

__
TR14-174
| 14th December 2014
__

Avishay Tal#### Tight bounds on The Fourier Spectrum of $AC^0$

Revisions: 2

__
TR14-048
| 10th April 2014
__

Avishay Tal#### Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.

Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ...
more >>>

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>

Pooya Hatami, William 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}$ ... more >>>

Yuval Filmus, Or Meir, Avishay Tal

Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $\widetilde{\Omega}(n^{3})$ formula size lower bound for the Andreev function, ... more >>>

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 ... more >>>

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... more >>>

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. ... more >>>

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean ... more >>>

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Recently, Bravyi, Gosset, and König (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, ... more >>>

Sumegha Garg, Ran Raz, Avishay Tal

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{2})$ or an exponential number ... more >>>

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

Anna Gal, Avishay Tal, Adrian Trejo Nuñez

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

Raghu Meka, Omer Reingold, Avishay Tal

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

Ran Raz, Avishay Tal

We present a distribution $D$ over inputs in $\{-1,1\}^{2N}$, 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 $\Omega(1/\log N)$.

(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ ...
more >>>

Oded Goldreich, Avishay Tal

We consider new complexity measures for the model of multilinear circuits with general multilinear gates introduced by Goldreich and Wigderson (ECCC, 2013).

These complexity measures are related to the size of canonical constant-depth Boolean circuits, which extend the definition of canonical depth-three Boolean circuits.

We obtain matching lower and upper ...
more >>>

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

We present an explicit pseudorandom generator with seed length $\tilde{O}((\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 Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

Or Meir, Avishay Tal

The direct-sum question is a classical question that asks whether

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice ... more >>>

Sumegha Garg, Ran Raz, Avishay Tal

A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in 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) \ldots$, where for every $i$, $a_i \in A$ is chosen ... more >>>

Pooya Hatami, Avishay Tal

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at ... more >>>

Avishay Tal

A bipartite formula on binary variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the $x$ or $y$ variables. We show that any bipartite formula for the Inner-Product ... more >>>

Avishay Tal

A de Morgan formula over Boolean variables $x_1, \ldots, 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 ... more >>>

Gillat Kol, Ran Raz, Avishay Tal

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ 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 ... more >>>

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-$s$ Boolean function ... more >>>

Avishay Tal

The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>>

Avishay Tal

We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula $F$ of size at most $n^{3-16\epsilon}$ in time $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant $\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>>

Oded Goldreich, Avishay Tal

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{n^3}{r^2\log n})$ for rank $r \ge \sqrt{n}$, with high probability. This improves, for $r = o(n/\log n \log\log n)$, over the $\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$ bound that is known for many explicit matrices.

Our result implies that the explicit ... more >>>

Avishay Tal

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up ... more >>>

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: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size ... more >>>