Fetching the paper…
Reading the bibliography…
Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas.
Über die Genauigkeit der Annäherung stetiger Funktionen durch ganze rationale Funktionen gegebenen Grades und trigonometrische Summen gegebener Ordnung
D. Jackson · 1911
Earlier work this paper cites.
Démonstration du théorème de Weierstrass fondée sur le calcul des probabilités
S. N. Bernstein · 1912
Earlier work this paper cites.
Can quantum-mechanical description of physical reality be considered complete?
A. Einstein, B. Podolsky, and N. Rosen · 1935
Earlier work this paper cites.
Schwankung von Polynomen zwischen Gitterpunkten
H. Ehlich and K. Zeller · 1964
Earlier work this paper cites.
A comparison of uniform approximations on an interval and a finite subset thereof
Theodore J. Rivlin and E. W. Cheney · 1966
Earlier work this paper cites.
An Introduction to the Approximation of Functions
Theodore J. Rivlin · 1969
Earlier work this paper cites.
Probabilistic Turing Machines and Complexity of Computation
III John T. Gill · 1972
Earlier work this paper cites.
Bounds for the quantity of information transmitted by a quantum communication channel
A. S. Holevo · 1973
Earlier work this paper cites.
Graph-theoretic arguments in low-level complexity
Leslie G. Valiant · 1977
Earlier work this paper cites.
Some complexity questions related to distributive computing
Andrew Chi-Chih Yao · 1979
Earlier work this paper cites.
Factoring polynomials with rational coefficients
A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász · 1982
Earlier work this paper cites.
Complexity classes in communication complexity theory
László Babai, Péter Frankl, and Janos Simon · 1986
Earlier work this paper cites.
Probabilistic communication complexity
Ramamohan Paturi and Janos Simon · 1986
Earlier work this paper cites.
Perceptrons
Marvin Minsky and Seymour Papert · 1988
Earlier work this paper cites.
On the rigidity of an Hadamard matrix
Noga Alon · 1990
Earlier work this paper cites.
Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
J. C. Lagarias, H. W. Lenstra, Jr., and C.-P. Schnorr · 1990
Earlier work this paper cites.
Elements of Information Theory
Thomas M. Cover and Joy A. Thomas · 1991
Earlier work this paper cites.
Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science
László Babai and Péter Frankl · 1992
Earlier work this paper cites.
On the degree of polynomials that approximate symmetric Boolean functions
Ramamohan Paturi · 1992
Earlier work this paper cites.
New bounds in some transference theorems in the geometry of numbers
W. Banaszczyk · 1993
Earlier work this paper cites.
Perceptrons, PP, and the polynomial hierarchy
Richard Beigel · 1994
Earlier work this paper cites.
Computing with noisy information
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal · 1994
Earlier work this paper cites.
PP is closed under intersection
Richard Beigel, Nick Reingold, and Daniel Spielman · 1995
Earlier work this paper cites.
Generating hard instances of lattice problems (extended abstract)
Miklós Ajtai · 1996
Earlier work this paper cites.
PP is closed under truth-table reductions
Lance Fortnow and Nick Reingold · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Quantum computability
Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang · 1997
Earlier work this paper cites.
A public-key cryptosystem with worst-case/average-case equivalence
Miklós Ajtai and Cynthia Dwork · 1997
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Earlier work this paper cites.
Communication Complexity
Eyal Kushilevitz and Noam Nisan · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1997
Earlier work this paper cites.
On the power of quantum computation
Daniel R. Simon · 1997
Earlier work this paper cites.
Private information retrieval
Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan · 1998
Earlier work this paper cites.
Quantum entanglement and the communication complexity of the inner product function
Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp · 1998
Earlier work this paper cites.
Complexity limitations on quantum computation
Lance Fortnow and John Rogers · 1998
Earlier work this paper cites.
The shrinkage exponent of de Morgan formulas is 2
Johan Håstad · 1998
Earlier work this paper cites.
Improved lower bounds on the rigidity of Hadamard matrices
B. Kashin and Alexander A. Razborov · 1998
Earlier work this paper cites.
Bounds for small-error and zero-error quantum algorithms
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka · 1999
Earlier work this paper cites.
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
Oded Goldreich, Daniele Micciancio, S. Safra, and J-P. Seifert · 1999
Earlier work this paper cites.
Optimal lower bounds for quantum automata and random access codes
Ashwin Nayak · 1999
Earlier work this paper cites.
On the limits of nonapproximability of lattice problems
Oded Goldreich and Shafi Goldwasser · 2000
Earlier work this paper cites.
On the efficiency of local decoding procedures for error-correcting codes
Jonathan Katz and Luca Trevisan · 2000
Earlier work this paper cites.
Quantum Computation and Quantum Information
Michael Nielsen and Isaac L. Chuang · 2000
Earlier work this paper cites.
A sieve algorithm for the shortest lattice vector problem
Miklós Ajtai, Ravi Kumar, and D. Sivakumar · 2001
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Cited alongside, same era.
Informational complexity and the direct sum problem for simultaneous message complexity
Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao · 2001
Cited alongside, same era.
Extremal Combinatorics, With Applications in Computer Science
Stasys Jukna · 2001
Cited alongside, same era.
Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
Satyanarayana V. Lokam · 2001
Cited alongside, same era.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2002
Cited alongside, same era.
Dense quantum coding and quantum finite automata
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani · 2002
Cited alongside, same era.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2006
Later among the works it cites.
Quadratic lower bounds on matrix rigidity
Satyanarayana V. Lokam · 2006
Later among the works it cites.
Limits on the ability of quantum states to convey classical messages
Ashwin Nayak and Julia Salzman · 2006
Later among the works it cites.
Lower bounds on matrix rigidity via a quantum argument
Ronald de Wolf · 2006
Later among the works it cites.
The first and fourth public-key cryptosystems with worst-case/average-case equivalence
Miklós Ajtai and Cynthia Dwork · 2007
Later among the works it cites.
On computation and communication with small bias
Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf · 2007
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Information theory methods in communication complexity
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2002
Cited alongside, same era.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp · 2002
Cited alongside, same era.
Are bitvectors optimal?
Harry Buhrman, P. B. Miltersen, Jaikumar Radhakrishnan, and S. Venkatesh · 2002
Cited alongside, same era.
Complexity measures and decision tree complexity: A survey
Harry Buhrman and Ronald de Wolf · 2002
Cited alongside, same era.
Linking classical and quantum key agreement: Is there a classical analog to bound entanglement?
Nicolas Gisin, Renato Renner, and Stefan Wolf · 2002
Cited alongside, same era.
Lower bounds for linear locally decodable codes and private information retrieval
Oded Goldreich, Howard Karloff, Leonard J. Schulman, and Luca Trevisan · 2002
Cited alongside, same era.
Tensor-based hardness of the shortest vector problem to within almost polynomial factors
Ishay Haviv and Oded Regev · 2007
Later among the works it cites.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Later among the works it cites.
Unbounded-error classical and quantum communication complexity
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita · 2007
Later among the works it cites.
Quantum multiparty communication complexity and circuit lower bounds
Iordanis Kerenidis · 2007
Later among the works it cites.
Lower bounds for quantum communication complexity
Hartmut Klauck · 2007
Later among the works it cites.
Quantum and classical strong direct product theorems and optimal time-space tradeoffs
Hartmut Klauck, Robert Špalek, and Ronald de Wolf · 2007
Later among the works it cites.
New lower bounds for general locally decodable codes
David P. Woodruff · 2007
Later among the works it cites.
The Probabilistic Method
Noga Alon and Joel H. Spencer · 2008
Later among the works it cites.
A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs
Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf · 2008
Later among the works it cites.
A quantum information-theoretic proof of the relation between Horn’s problem and the Littlewood-Richardson coefficients
Matthias Christandl · 2008
Later among the works it cites.
A quantum algorithm for the Hamiltonian NAND tree
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2008
Later among the works it cites.
An Introduction to Kolmogorov Complexity and its Applications
Ming Li and Paul Vitányi · 2008
Later among the works it cites.
Learning complexity vs communication complexity
Nati Linial and Adi Shraibman · 2008
Later among the works it cites.
Complexity lower bounds using linear algebra
Satyanarayana V. Lokam · 2008
Later among the works it cites.
Lower bounds for predecessor searching in the cell probe model
Pranab Sen and S. Venkatesh · 2008
Later among the works it cites.
Approximate inclusion-exclusion for arbitrary symmetric functions
Alexander A. Sherstov · 2008
Later among the works it cites.
Halfspace matrices
Alexander A. Sherstov · 2008
Later among the works it cites.
A note on quantum algorithms and the minimal degree of ε \varepsilon -error polynomials for symmetric functions
Ronald de Wolf · 2008
Later among the works it cites.
Rational degree equals quantum query complexity with postselection
Ronald de Wolf · 2008
Later among the works it cites.
Towards 3-query locally decodable codes of subexponential length
Sergey Yekhanin · 2008
Later among the works it cites.
3-query locally decodable codes of subexponential length
Klim Efremenko · 2009
Closest in time.
Complexity classes of equivalence problems revisited, 2009
Lance Fortnow and Joshua A. Grochow · 2009
Closest in time.
On the communication complexity of read-once A C 0 AC^{0} formulae
T. S. Jayram, Swastik Kopparty, and Prasad Raghavendra · 2009
Closest in time.
A note on the sign degree of formulas, 2009
Troy Lee · 2009
Closest in time.
Lower bounds on quantum multiparty communication complexity
Troy Lee, Gideon Schechtman, and Adi Shraibman · 2009
Closest in time.
Lower bounds in communication complexity based on factorization norms
Nati Linial and Adi Shraibman · 2009
Closest in time.
Erdős and the quantum method, March 28, 2009
Richard Lipton · 2009
Closest in time.
Lattice-based cryptography
Daniele Micciancio and Oded Regev · 2009
Closest in time.
Public-key cryptosystems from the worst-case shortest vector problem
Chris Peikert · 2009
Closest in time.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Closest in time.
Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function
Ben W. Reichardt · 2009
Closest in time.
Any AND-OR formula of size N N can be evaluated in time N 1 / 2 + o ( 1 ) N^{1/2+o(1)} on a quantum computer
Andris Ambainis, A. Childs, Ben W. Reichardt, Robert Špalek, and S. Zhang · 2010
Closest in time.
Lower bounds on the randomized communication complexity of read-once functions
Nikos Leonardos and Michael Saks · 2010
Closest in time.
Span programs and quantum query algorithms
Ben W. Reichardt · 2010
Closest in time.
The pattern matrix method
Alexander A. Sherstov · 2010
Closest in time.
A quadratic lower bound for three-query linear locally decodable codes over any field
David P. Woodruff · 2010
Closest in time.
Uniform approximation by (quantum) polynomials
Andrew Drucker and Ronald de Wolf · 2011
Closest in time.