Algorithmic Polynomials
DOI10.1137/19M1278831zbMath1495.68096OpenAlexW3037165238MaRDI QIDQ5138783
Publication date: 4 December 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1278831
separationsquantum query complexitysurjectivity problemapproximate degree\(k\)-CNF formulas\(k\)-DNF formulas\(k\)-element distinctness problem\(k\)-subset sum problem
Quantum computation (81P68) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (1)
Cites Work
- Learning intersections and thresholds of halfspaces
- Approximate inclusion-exclusion for arbitrary symmetric functions
- Disjointness is hard in the multiparty number-on-the-forehead model
- Approximate inclusion-exclusion
- On the computational power of depth-2 circuits with threshold and modulo gates
- Computing Boolean functions by polynomials and threshold circuits
- The expressive power of voting polynomials
- Approximating threshold circuits by rational functions
- On the degree of Boolean functions as real polynomials
- Inclusion-exclusion: exact and approximate
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- Polynomial degree vs. quantum query complexity
- Robust polynomials and quantum algorithms
- The Multiparty Communication Complexity of Set Disjointness
- Faster Algorithms for Privately Releasing Marginals
- Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
- Adversary lower bound for the k-sum problem
- Faster private release of marginals on small databases
- Limitations of Quantum Advice and One-Way Communication
- The Sign-Rank of AC$^0$
- Extremal Combinatorics
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- The Pattern Matrix Method
- Quantum lower bounds for the collision and the element distinctness problems
- Agnostically Learning Halfspaces
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Rational approximation techniques for analysis of neural networks
- Quantum communication complexity of symmetric predicates
- Formula lower bounds via the quantum method
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Quantum algorithms and approximating polynomials for composed functions with shared inputs
- Quantum Algorithms for Element Distinctness
- Separations in query complexity using cheat sheets
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum lower bounds by polynomials
- Quantum Walk Algorithm for Element Distinctness
- Communication Lower Bounds Using Directional Derivatives
- New degree bounds for polynomial threshold functions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Algorithmic Polynomials
