Approximate Degree in Classical and Quantum Computing
From MaRDI portal
Publication:5060675
DOI10.1561/0400000107OpenAlexW4313319348MaRDI QIDQ5060675
Publication date: 11 January 2023
Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1561/0400000107
Cites Work
- Probabilistic communication complexity
- Boolean function complexity. Advances and frontiers.
- Perceptrons of large weight
- Quantum Arthur-Merlin games
- Halfspace matrices
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- The expressive power of voting polynomials
- Toward efficient agnostic learning
- On the degree of Boolean functions as real polynomials
- Perceptrons, PP, and the polynomial hierarchy
- Inclusion-exclusion: exact and approximate
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- The hardest halfspace
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Polynomial degree vs. quantum query complexity
- Theory of majority decision elements
- Robust polynomials and quantum algorithms
- Bounded Indistinguishability and the Complexity of Recovering Secrets
- Faster Algorithms for Privately Releasing Marginals
- Algebrization
- Faster private release of marginals on small databases
- The Sign-Rank of AC$^0$
- The Pattern Matrix Method
- Parity, circuits, and the polynomial-time hierarchy
- Complexity Lower Bounds using Linear Algebra
- Lower Bounds in Communication Complexity
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
- Quantum lower bounds for the collision and the element distinctness problems
- A Uniform Lower Bound on Weights of Perceptrons
- Agnostically Learning Halfspaces
- Learning Complexity vs Communication Complexity
- Hardness of Learning Halfspaces with Noise
- Quantum lower bound for the collision problem
- Composition Theorems in Communication Complexity
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- A theory of the learnable
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- The Growth of Polynomials Bounded at Equally Spaced Points
- Computational Complexity of Probabilistic Turing Machines
- Strengths and Weaknesses of Quantum Computing
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The Power of Asymmetry in Constant-Depth Circuits
- On polynomial approximations to AC
- Quantum Query Algorithms Are Completely Bounded Forms
- Quantum communication complexity of symmetric predicates
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- Formula lower bounds via the quantum method
- Sign-rank Can Increase under Intersection
- Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
- On the Power of Statistical Zero Knowledge
- UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY
- Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Algorithmic polynomials
- Bounded Independence Fools Halfspaces
- The Intersection of Two Halfspaces Has High Threshold Degree
- Making polynomials robust to noise
- A Lower Bound for Agnostically Learning Disjunctions
- Quantum lower bounds by polynomials
- Quantum Walk Algorithm for Element Distinctness
- Communication Lower Bounds Using Directional Derivatives
- Approximate Degree, Secret Sharing, and Concentration Phenomena
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- Lower bounds in communication complexity based on factorization norms
- Bipartite perfect matching as a real polynomial
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximate Degree in Classical and Quantum Computing
