Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Avishay Tal:

TR18-112 | 5th June 2018
Raghu Meka, Omer Reingold, Avishay Tal

Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

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

TR18-107 | 31st May 2018
Ran Raz, Avishay Tal

Oracle Separation of BQP and PH

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

TR17-193 | 31st December 2017
Oded Goldreich, Avishay Tal

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

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

TR17-171 | 6th November 2017
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

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

TR17-148 | 6th October 2017
Or Meir, Avishay Tal

The Choice and Agreement Problems of a Random Function

Revisions: 3

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

TR17-121 | 31st July 2017
Sumegha Garg, Ran Raz, Avishay Tal

Extractor-Based Time-Space Lower Bounds for Learning

Revisions: 1

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

TR17-025 | 16th February 2017
Pooya Hatami, Avishay Tal

Pseudorandom Generators for Low-Sensitivity Functions

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

TR16-181 | 15th November 2016
Avishay Tal

The Bipartite Formula Complexity of Inner-Product is Quadratic

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

TR16-179 | 15th November 2016
Avishay Tal

Computing Requires Larger Formulas than Approximating

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

TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

Time-Space Hardness of Learning Sparse Parities

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

TR16-069 | 25th April 2016
Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

Degree and Sensitivity: tails of two distributions

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

TR16-062 | 18th April 2016
Avishay Tal

On The Sensitivity Conjecture

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

TR15-114 | 18th July 2015
Avishay Tal

#SAT Algorithms from Shrinkage

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

TR15-079 | 7th May 2015
Oded Goldreich, Avishay Tal

Matrix Rigidity of Random Toeplitz Matrices

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

TR14-174 | 14th December 2014
Avishay Tal

Tight bounds on The Fourier Spectrum of $AC^0$

Revisions: 2

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

TR14-048 | 10th April 2014
Avishay Tal

Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

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

ISSN 1433-8092 | Imprint