Approximate Degree in Classical and Quantum Computing
From MaRDI portal
Publication:5060675
Recommendations
Cites work
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- A linear lower bound on the unbounded error probabilistic communication complexity.
- A Lower Bound for Agnostically Learning Disjunctions
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
- A separation of NP and conp in multiparty communication complexity
- A theory of the learnable
- A Uniform Lower Bound on Weights of Perceptrons
- Agnostically Learning Halfspaces
- Algebrization: a new barrier in complexity theory
- Algorithmic polynomials
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Approximate bounded indistinguishability
- Approximate degree and the complexity of depth three circuits
- Approximate Degree, Secret Sharing, and Concentration Phenomena
- Approximating the AND-OR tree
- Boolean function complexity. Advances and frontiers.
- Bounded Independence Fools Halfspaces
- Bounded indistinguishability and the complexity of recovering secrets
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Communication lower bounds using directional derivatives
- Complexity Lower Bounds using Linear Algebra
- Composition theorems in communication complexity
- Computational Complexity of Probabilistic Turing Machines
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Formula lower bounds via the quantum method
- Halfspace matrices
- Hardness amplification and the approximate degree of constant-depth circuits
- Hardness of learning halfspaces with noise
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- scientific article; zbMATH DE number 5568623 (Why is no real title available?)
- scientific article; zbMATH DE number 4125012 (Why is no real title available?)
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- scientific article; zbMATH DE number 7651029 (Why is no real title available?)
- scientific article; zbMATH DE number 7829258 (Why is no real title available?)
- Impossibility of succinct quantum proofs for collision-freeness
- Inclusion-exclusion: exact and approximate
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Learning complexity vs communication complexity
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Lower bounds for the approximate degree of block-composed functions
- Lower bounds in communication complexity
- Lower bounds in communication complexity based on factorization norms
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Making polynomials robust to noise
- Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
- Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)
- On multiparty communication with large versus unbounded error
- On polynomial approximations to \(\mathrm{AC}^0\)
- On the degree of Boolean functions as real polynomials
- On the power of statistical zero knowledge
- Parity, circuits, and the polynomial-time hierarchy
- Perceptrons of large weight
- Perceptrons, PP, and the polynomial hierarchy
- Polynomial degree vs. quantum query complexity
- Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
- PP is closed under intersection
- Probabilistic communication complexity
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum Arthur-Merlin games
- Quantum communication complexity of symmetric predicates
- Quantum lower bound for the collision problem
- Quantum lower bounds by polynomials
- Quantum lower bounds for approximate counting via Laurent polynomials
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum query algorithms are completely bounded forms
- Quantum Walk Algorithm for Element Distinctness
- Reflections for quantum query algorithms
- Robust polynomials and quantum algorithms
- Separating AC\(^0\) from depth-2 majority circuits
- Sign-rank can increase under intersection
- Strengths and Weaknesses of Quantum Computing
- The expressive power of voting polynomials
- The Growth of Polynomials Bounded at Equally Spaced Points
- The hardest halfspace
- The intersection of two halfspaces has high threshold degree
- The large-error approximate degree of \(\mathrm{AC}^0\)
- The pattern matrix method
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- The power of asymmetry in constant-depth circuits
- The quantum query complexity of \(\mathrm{AC}^0\)
- The Sign-Rank of AC^0
- Theory of majority decision elements
- Toward efficient agnostic learning
- Understanding quantum algorithms via query complexity
Cited in
(3)
This page was built for publication: Approximate Degree in Classical and Quantum Computing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5060675)
