Source author record

Avishay Tal

Avishay Tal appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity quant-ph math.CA math.CO

Catalog footprint

What is connected

5works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Quantum Implications of Huang's Sensitivity Theorem

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, Santha, and Smotrovs (2017). We also use the result 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.

preprint2019arXiv

Towards Optimal Separations between Quantum and Randomized Query Complexities

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. $\sqrt{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 $\tildeΩ(N^{2(k-1)/(3k-1)})$ queries for any randomized algorithm. For any constant $\varepsilon>0$, this gives a $O(1)$ vs. $N^{2/3-\varepsilon}$ 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-\varepsilon}$ separations between the quantum and randomized query complexities of partial Boolean functions.

preprint2016arXiv

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. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.

preprint2014arXiv

Two Structural Results for Low Degree Polynomials and Applications

In this paper, two structural results concerning low degree polynomials over finite fields are given. The first states that over any finite field $\mathbb{F}$, for any polynomial $f$ on $n$ variables with degree $d \le \log(n)/10$, there exists a subspace of $\mathbb{F}^n$ with dimension $Ω(d \cdot n^{1/(d-1)})$ on which $f$ is constant. This result is shown to be tight. Stated differently, a degree $d$ polynomial cannot compute an affine disperser for dimension smaller than $Ω(d \cdot n^{1/(d-1)})$. Using a recursive argument, we obtain our second structural result, showing that any degree $d$ polynomial $f$ induces a partition of $F^n$ to affine subspaces of dimension $Ω(n^{1/(d-1)!})$, such that $f$ is constant on each part. We extend both structural results to more than one polynomial. We further prove an analog of the first structural result to sparse polynomials (with no restriction on the degree) and to functions that are close to low degree polynomials. We also consider the algorithmic aspect of the two structural results. Our structural results have various applications, two of which are: * Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over any finite field, any affine extractor is also an extractor for varieties with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over $F_2$. * Ben-Sasson and Kopparty [SIAM J. C 2012] proved that any degree 3 affine disperser over a prime field is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree.

preprint2013arXiv

On the Structure of Boolean Functions with Small Spectral Norm

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is $\|\hat{f}\|_1=\sum_α|\hat{f}(α)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n \to \{0,1\}$ with $\|\hat{f}\|_1=A$. 1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant. 2. f can be computed by a parity decision tree of size $2^{A^2}n^{2A}$. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) 3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth $A^2 \log s$. 4. For every $0<ε$ there is a parity decision tree of depth $O(A^2 + \log(1/ε))$ and size $2^{O(A^2)} \cdot \min\{1/ε^2,O(\log(1/ε))^{2A}\}$ that ε-approximates f. Furthermore, this tree can be learned, with probability $1-δ$, using $\poly(n,\exp(A^2),1/ε,\log(1/δ))$ membership queries. All the results above also hold (with a slight change in parameters) to functions $f:Z_p^n\to \{0,1\}$.