scientific article; zbMATH DE number 7561735
From MaRDI portal
Publication:5092454
DOI10.4230/LIPIcs.CCC.2020.7zbMath1495.68085arXiv1904.08914MaRDI QIDQ5092454
William Kretschmer, Justin Thaler, Scott Aaronson, Robin Kothari
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1904.08914
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Quantum Arthur-Merlin games
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
- On the limits of nonapproximability of lattice problems
- Complexity measures and decision tree complexity: a survey.
- Quantum lightning never strikes the same state twice
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Error-bounded probabilistic computations between MA and AM
- Rational approximation to \(|x|\)
- The quantum query complexity of approximating the median and related statistics
- Limitations of Quantum Advice and One-Way Communication
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum lower bound for the collision problem
- Adiabatic quantum state generation and statistical zero knowledge
- Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
- On Approximation Algorithms for # P
- The Knowledge Complexity of Interactive Proof Systems
- The Growth of Polynomials Bounded at Equally Spaced Points
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Strengths and Weaknesses of Quantum Computing
- Analysis of Boolean Functions
- The Intersection of Two Halfspaces Has High Threshold Degree
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Advances in Cryptology - CRYPTO 2003
- Multi-letter Reversible and Quantum Finite Automata
- Quantum computing, postselection, and probabilistic polynomial-time
- Quantum lower bounds by polynomials
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
- Quantum cryptanalysis of hash and claw-free functions
- Rectangles Are Nonnegative Juntas
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- Vector analysis
