Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polynomial method:
TR95-035 | 30th June 1995
Richard Beigel

Closure Properties of GapP and #P

We classify the univariate functions that are relativizable
closure properties of GapP, solving a problem posed by Hertrampf,
Vollmer, and Wagner (Structures '95). We also give a simple proof of
their classification of univariate functions that are relativizable
closure properties of #P.

more >>>

TR04-026 | 17th February 2004
Scott Aaronson

Limitations of Quantum Advice and One-Way Communication

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones.
First, we show that BQP/qpoly is contained in ... more >>>

TR09-004 | 15th January 2009
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... more >>>

TR09-011 | 31st January 2009
Mark Braverman

Poly-logarithmic independence fools AC0 circuits

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... more >>>

TR11-001 | 2nd January 2011
Scott Aaronson

Impossibility of Succinct Quantum Proofs for Collision-Freeness

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

TR12-117 | 17th September 2012
Loïck Magnin, Jérémie Roland

Explicit relation between all lower bound techniques for quantum query complexity

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>>

TR13-060 | 10th April 2013
Venkatesan Guruswami, Swastik Kopparty

Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

TR15-189 | 25th November 2015
Shay Moran, Cyrus Rashtchian

Shattered Sets and the Hilbert Function

Revisions: 1

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>

TR16-100 | 27th June 2016
Suguru Tamaki

A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>

TR17-022 | 13th February 2017
Benjamin Rossman, Srikanth Srinivasan

Separation of AC$^0[\oplus]$ Formulas and Circuits

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent ... more >>>

TR17-169 | 24th October 2017
Mark Bun, Robin Kothari, Justin Thaler

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and ... more >>>

TR18-017 | 26th January 2018
Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

Lossless dimension expanders via linearized polynomials and subspace designs

For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{F}^n$ of dimension at most $\eta n$, the image of $U$ under all the maps, $\sum_{j=1}^d ... more >>>

ISSN 1433-8092 | Imprint