CoChat
Sign Up
Cited by 41Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsQuantum Information and Cryptography

The DOI matches its Crossref record, with a small difference in title or year; 3 of the 3 references it cites were found in a registry or an index.

Quantum proofs for classical theorems

Open access
Andrew Drucker, Ronald de Wolf·2011·Theory of Computing
DOI 10.4086/toc.gs.2011.002
Open this paper in CoChat — free accountOpen PDF

Abstract

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. In this paper we survey these results and the quantum toolbox they use.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.4086/toc.gs.2011.002

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 3 references

Research works printed but not linked: 116

  1. SCOTT AARONSON: Limitations of quantum advice and one-way communication. Theory of Computing, 1:1-28, 2005. Earlier version in Proc. 19th IEEE Conf. Comput. Complex., 2004 and arxiv:quant-ph/0402095. [doi:10.4086/toc.2005.v001a001] · DOI
  2. SCOTT AARONSON: Quantum computing, postselection, and probabilistic polynomial-time. In Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., volume A461(2063), pp. 3473-3482, 2005. Earlier version in arxiv:quant-ph/0412187. [doi:10.1098/rspa.2005.1546] · DOI
  3. SCOTT AARONSON: Lower bounds for local search by quantum arguments. SIAM J. Comput., 35(4):804-824, 2006. Earlier version in STOC '03 and arxiv:quant-ph/0307149. [doi:10.1137/S0097539704447237] 35, 36 · DOI
  4. SCOTT AARONSON AND YAOYUN SHI: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595-605, 2004. [doi:10.1145/1008731.1008735] · DOI
  5. LEONARD M. ADLEMAN, JONATHAN DEMARRAIS, AND MING-DEH A. HUANG: Quantum computability. SIAM J. Comput., 26(5):1524-1540, 1997. [doi:10.1137/S0097539795293639] · DOI
  6. DORIT AHARONOV AND ODED REGEV: A lattice problem in quantum NP. In Proc. 44th FOCS, pp. 210-219. IEEE Comp. Soc. Press, 2003. Earlier version in arxiv:quant-ph/0307220. [doi:10.1109/SFCS.2003.1238195] · DOI
  7. DORIT AHARONOV AND ODED REGEV: Lattice problems in NP intersect coNP. J. ACM, 52(5):749-765, 2005. Earlier version in FOCS '04. [doi:10.1145/1089023.1089025] 38, 39 · DOI
  8. MIKL ÓS AJTAI: Generating hard instances of lattice problems (extended abstract). In Proc. 28th STOC, pp. 99-108. ACM Press, 1996. [doi:10.1145/237814.237838] · DOI
  9. MIKL ÓS AJTAI AND CYNTHIA DWORK: A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th STOC, pp. 284-293. ACM Press, 1997. [doi:10.1145/258533.258604] · DOI
  10. MIKL ÓS AJTAI AND CYNTHIA DWORK: The first and fourth public-key cryptosystems with worst-case/average-case equivalence. Electron. Colloq. on Comput. Complexity (ECCC), 14(097), 2007. [ECCC:TR07-097] 37
  11. MIKL ÓS AJTAI, RAVI KUMAR, AND D. SIVAKUMAR: A sieve algorithm for the short- est lattice vector problem. In Proc. 33rd STOC, pp. 601-610. ACM Press, 2001. [doi:10.1145/380752.380857] · DOI
  12. NOGA ALON AND JOEL H. SPENCER: The Probabilistic Method. Wiley-Interscience, third edition, 2008. 3, 4, 30
  13. ANDRIS AMBAINIS: Quantum lower bounds by quantum arguments. J. Comput. Sys- tem Sci., 64(4):750-767, 2002. Earlier versions in STOC '00 and arxiv:quant-ph/0002066. [doi:10.1006/jcss.2002.1826] 35 · DOI
  14. ANDRIS AMBAINIS: Polynomial degree vs. quantum query complexity. J. Comput. Sys- tem Sci., 72(2):220-238, 2006. Earlier versions in FOCS '03 and arxiv:quant-ph/0305028. [doi:10.1016/j.jcss.2005.06.006] 30, 35 · DOI
  15. ANDRIS AMBAINIS, A. CHILDS, BEN W. REICHARDT, ROBERT ŠPALEK, AND S. ZHANG: Any AND-OR formula of size N can be evaluated in time N 1/2+o(1) on a quantum computer. SIAM J. Comput., 39(6):2513-2530, 2010. Earlier version in FOCS '07. [doi:10.1137/080712167] 22 · DOI · Paper page
  16. ANDRIS AMBAINIS, ASHWIN NAYAK, AMNON TA-SHMA, AND UMESH VAZIRANI: Dense quantum coding and quantum finite automata. J. ACM, 49(4):496-511, 2002. Earlier version in STOC '99. [doi:10.1145/581771.581773] · DOI
  17. L ÁSZL Ó BABAI, P ÉTER FRANKL, AND JANOS SIMON: Complexity classes in communica- tion complexity theory. In Proc. 27th FOCS, pp. 337-347. IEEE Comp. Soc. Press, 1986. [doi:10.1109/SFCS.1986.15] · DOI
  18. W. BANASZCZYK: New bounds in some transference theorems in the geometry of numbers. Math. Ann., 296(4):625-635, 1993. [doi:10.1007/BF01445125] 38 · DOI
  19. ZIV BAR-YOSSEF, T. S. JAYRAM, RAVI KUMAR, AND D. SIVAKUMAR: Information theory methods in communication complexity. In Proc. 17th IEEE Conf. Comput. Complex., 2002, pp. 93-102, 2002. [doi:10.1109/CCC.2002.1004344] · DOI
  20. ZIV BAR-YOSSEF, T. S. JAYRAM, RAVI KUMAR, AND D. SIVAKUMAR: An information statistics approach to data stream and communication complexity. J. Comput. System Sci., 68(4):702-732, 2004. Earlier version in FOCS '02. [doi:10.1016/j.jcss.2003.11.006] · DOI
  21. ROBERT BEALS, HARRY BUHRMAN, RICHARD CLEVE, MICHELE MOSCA, AND RONALD DE WOLF: Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. Earlier versions in FOCS '98 and arxiv:quant-ph/9802049. [doi:10.1145/502090.502097] 13, 14 · DOI · Paper page
  22. RICHARD BEIGEL: Perceptrons, PP, and the polynomial hierarchy. Comput. Complexity, 4:339- 349, 1994. [doi:10.1007/BF01263422] 33 · DOI
  23. RICHARD BEIGEL, NICK REINGOLD, AND DANIEL SPIELMAN: PP is closed under intersection. J. Comput. System Sci., 50(2):191-202, 1995. [doi:10.1006/jcss.1995.1017] 27, 29 · DOI
  24. AVRAHAM BEN-AROYA, ODED REGEV, AND RONALD DE WOLF: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In Proc. 49th FOCS, pp. 477-486. IEEE Comp. Soc. Press, 2008. Earlier version in arxiv:quant-ph/0705.3806. [doi:10.1109/FOCS.2008.45] · DOI
  25. GILLES BRASSARD, P. HØYER, MICHELE MOSCA, AND ALAIN TAPP: Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millen- nium Volume, volume 305 of AMS Contemporary Mathematics Series, pp. 53-74. American Mathematical Society, 2002. Earlier version in arxiv:quant-ph/0005055. 12, 13, 31 · arXiv
  26. HARRY BUHRMAN, RICHARD CLEVE, RONALD DE WOLF, AND CHRISTOF ZALKA: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358-368. IEEE Comp. Soc. Press, 1999. Earlier version in arxiv:cs.CC/9904019. [doi:10.1109/SFFCS.1999.814607] · DOI
  27. HARRY BUHRMAN AND RONALD DE WOLF: Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci., 288(1):21-43, 2002. [doi:10.1016/S0304-3975(01)00144-X] 11 · DOI
  28. HARRY BUHRMAN, P. B. MILTERSEN, JAIKUMAR RADHAKRISHNAN, AND S. VENKATESH: Are bitvectors optimal? SIAM J. Comput., 31(6):1723-1744, 2002. Earlier version in STOC '00. [doi:10.1137/S0097539702405292] 41 · DOI
  29. HARRY BUHRMAN, ILAN NEWMAN, HEIN R ÖHRIG, AND RONALD DE WOLF: Robust poly- nomials and quantum algorithms. Theory Comput. Syst., 40(4):379-395, 2007. Special issue on STACS 2005. Earlier version in arxiv:quant-ph/0309220. [doi:10.1007/s00224-006-1313-z] 24, 25 · DOI
  30. HARRY BUHRMAN, NIKOLAY VERESHCHAGIN, AND RONALD DE WOLF: On computation and communication with small bias. In Proc. 22nd IEEE Conf. Comput. Complex., pp. 24-32, 2007. [doi:10.1109/CCC.2007.18] 32, 33 · DOI
  31. AMIT CHAKRABARTI AND ODED REGEV: An optimal randomised cell probe lower bound for approximate nearest neighbour searching. In Proc. 45th FOCS, pp. 473-482. IEEE Comp. Soc. Press, 2004. [doi:10.1137/080729955] 41 · DOI
  32. AMIT CHAKRABARTI, YAOYUN SHI, ANTHONY WIRTH, AND ANDREW CHI-CHIH YAO: Informational complexity and the direct sum problem for simultaneous message complexity. In Proc. 42nd FOCS, pp. 270-278. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959901] · DOI
  33. BENNY CHOR, ODED GOLDREICH, EYAL KUSHILEVITZ, AND MADHU SUDAN: Pri- vate information retrieval. J. ACM, 45(6):965-981, 1998. Earlier version in FOCS '95. [doi:10.1145/293347.293350] · DOI · Paper page
  34. MATTHIAS CHRISTANDL: A quantum information-theoretic proof of the relation between Horn's problem and the Littlewood-Richardson coefficients. In Proc. 4th Conf. Computabil- ity in Europe (CiE), volume 5028 of Lecture Notes in Comput. Sci., pp. 120-128, 2008. [doi:10.1145/293347.293350] · DOI · Paper page
  35. THOMAS M. COVER AND JOY A. THOMAS: Elements of Information Theory. Wiley, 1991. 3
  36. MART DE GRAAF AND RONALD DE WOLF: On quantum versions of the Yao principle. In Proc. 19th Ann. Symp. Theor. Aspects of Comput. Sci. (STACS), volume 2285 of Lecture Notes in Comput. Sci., pp. 347-358. Springer, 2002. Earlier version in arxiv:quant-ph/0109070. [doi:10.1007/3-540- 45841-7 28] · DOI
  37. RONALD DE WOLF: Quantum communication and complexity. Theoret. Comput. Sci., 287(1):337- 353, 2002. [doi:10.1016/S0304-3975(02)00377-8] · DOI
  38. RONALD DE WOLF: Lower bounds on matrix rigidity via a quantum argument. In Proc. 33rd Intern. Colloq. Autom. Lang. Program. (ICALP), volume 4051 of Lecture Notes in Comput. Sci., pp. 62-71, 2006. Earlier version in arxiv:quant-ph/0505188. [doi:10.1007/11786986 7] 18, 19, 21 · DOI
  39. RONALD DE WOLF: A note on quantum algorithms and the minimal degree of ε-error polyno- mials for symmetric functions. Quantum Inf. Comput., 8(10):943-950, 2008. Earlier version in arxiv:quant-ph/0802.1816. 22
  40. ANDREW DRUCKER AND RONALD DE WOLF: Uniform approximation by (quantum) polynomials. Quantum Information and Computation, (3&4):215-225, 2011. http://www.rintonpress. com/journals/qiconline.html#v11n34. Earlier version in arxiv:1008.1599. 31 · arXiv
  41. KLIM EFREMENKO: 3-query locally decodable codes of subexponential length. In Proc. 41st STOC, pp. 39-44. ACM Press, 2009. [doi:10.1145/1536414.1536422] · DOI
  42. EDWARD FARHI, JEFFREY GOLDSTONE, AND SAM GUTMANN: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169-190, 2008. Earlier version in arxiv:quant-ph/0702144. [doi:10.4086/toc.2008.v004a008] · DOI
  43. URIEL FEIGE, PRABHAKAR RAGHAVAN, DAVID PELEG, AND ELI UPFAL: Computing with noisy information. SIAM J. Comput., 23(5):1001-1018, 1994. Earlier version in STOC '90. [doi:10.1137/S0097539791195877] 25 · DOI
  44. LANCE FORTNOW AND JOSHUA A. GROCHOW: Complexity classes of equivalence problems revisited, 2009. Earlier version in arXiv:0907.4775. 41 · arXiv
  45. LANCE FORTNOW AND NICK REINGOLD: PP is closed under truth-table reductions. Inform. and Comput., 124(1):1-6, 1996. [doi:10.1137/S0097539791195877] 27 · DOI
  46. LANCE FORTNOW AND JOHN ROGERS: Complexity limitations on quantum computation. J. Comput. System Sci., 59(2):240-252, 1999. Earlier version in Proc. 13th IEEE Conf. Comput. Complex., 1998 and arxiv:cs.CC/9811023. [doi:10.1006/jcss.1999.1651] · DOI
  47. NICOLAS GISIN, RENATO RENNER, AND STEFAN WOLF: Linking classical and quantum key agreement: Is there a classical analog to bound entanglement? Algorithmica, 34(4):389-412, 2002. Earlier version in Crypto '00. [doi:10.1007/s00453-002-0972-7] 41 · DOI
  48. ODED GOLDREICH AND SHAFI GOLDWASSER: On the limits of nonapproximability of lat- tice problems. J. Comput. System Sci., 60(3):540-563, 2000. Earlier version in STOC '98. [doi:10.1137/S0097539702405292] 38 · DOI
  49. ODED GOLDREICH, HOWARD KARLOFF, LEONARD J. SCHULMAN, AND LUCA TREVISAN: Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complexity, 15(3):263-296, 2006. Earlier version in Proc. 17th IEEE Conf. Comput. Complex., 2002. [doi:10.1007/s00037-006-0216-3] 17 · DOI
  50. ODED GOLDREICH, DANIELE MICCIANCIO, S. SAFRA, AND J-P. SEIFERT: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inform. Process. Lett., 71(2):55-61, 1999. [doi:10.1016/S0020-0190(99)00083-6] · DOI
  51. JOHAN H ÅSTAD: The shrinkage exponent of de Morgan formulas is 2. SIAM J. Comput., 27(1):48- 64, 1998. [doi:10.1137/S0097539794261556] 41 · DOI
  52. ISHAY HAVIV AND ODED REGEV: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proc. 39th STOC, pp. 469-477. ACM Press, 2007. [doi:10.1145/1250790.1250859] · DOI
  53. A. S. HOLEVO: Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3-11, 1973. English translation in Problems Inform. Transmission, 9:177-183, 1973. http://mi.mathnet.ru/eng/ppi903. 10
  54. P. HØYER, TROY LEE, AND ROBERT ŠPALEK: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526-535. ACM Press, 2007. Earlier version in arxiv:quant-ph/0611054. [doi:10.1145/1250790.1250867] · DOI
  55. P. HØYER, MICHELE MOSCA, AND RONALD DE WOLF: Quantum search on bounded-error inputs. In Proc. 30th Intern. Colloq. Autom. Lang. Program. (ICALP), volume 2719 of Lecture Notes in Comput. Sci., pp. 291-299. Springer, 2003. Earlier version in arxiv:quant-ph/0304052. [doi:10.1007/3-540-45061-0 25] · DOI
  56. KAZUO IWAMA, HARUMICHI NISHIMURA, RUDY RAYMOND, AND SHIGERU YAMASHITA: Unbounded-error classical and quantum communication complexity. In Proc. 18th Intern. Symp. Algorithms Comput. (ISAAC), volume 4835 of Lecture Notes in Comput. Sci., pp. 100-111. Springer, 2007. Earlier version in arXiv:0709.2761. [doi:10.1007/978-3-540-77120-3 11] · DOI
  57. D. JACKSON: Über die Genauigkeit der Annäherung stetiger Funktionen durch ganze rationale Funktionen gegebenen Grades und trigonometrische Summen gegebener Ordnung. PhD thesis, University of Göttingen, 1911. 30
  58. T. S. JAYRAM, S. KOPPARTY, AND P. RAGHAVENDRA: On the communication complexity of read-once AC 0 formulae. In Proc. 24th IEEE Conf. Comput. Complex., pp. 329-340, 2009. [doi:10.1109/CCC.2009.39] · DOI
  59. T. S. JAYRAM, RAVI KUMAR, AND D. SIVAKUMAR: Two applications of information complexity. In Proc. 35th STOC, pp. 673-682. ACM Press, 2003. [doi:10.1145/780542.780640] · DOI
  60. III JOHN T. GILL: Probabilistic Turing Machines and Complexity of Computation. PhD thesis, UC Berkeley, Berkeley, California, 1972. 26
  61. STASYS JUKNA: Extremal Combinatorics, With Applications in Computer Science. EATCS Series. Springer, 2001. 5, 44
  62. B. KASHIN AND ALEXANDER A. RAZBOROV: Improved lower bounds on the rigidity of Hadamard matrices. Mat. Zametki, 63(4):535-540, 1998. In Russian. 19, 21
  63. JONATHAN KATZ AND LUCA TREVISAN: On the efficiency of local decoding procedures for error- correcting codes. In Proc. 32nd STOC, pp. 80-86. ACM Press, 2000. [doi:10.1145/335305.335315] 16, 17 · DOI
  64. IORDANIS KERENIDIS: Quantum multiparty communication complexity and circuit lower bounds. In Proc. 4th Ann. Conf. Theory and Appl. Models of Comput. (TAMC), volume 4484 of Lecture Notes in Comput. Sci., pp. 306-317. Springer, 2007. Earlier version in arxiv:quant-ph/0504087. [doi:10.1007/978-3-540-72504-6 28] · DOI
  65. IORDANIS KERENIDIS AND RONALD DE WOLF: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. System Sci., 69(3):395-420, 2004. Earlier versions in STOC '03 and arxiv:quant-ph/0208062. [doi:10.1016/j.jcss.2004.04.007] 11, 17, 18 · DOI
  66. SUBHASH KHOT: Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789-808, 2005. Earlier version in FOCS '04. [doi:10.1145/1089023.1089027] · DOI
  67. HARTMUT KLAUCK: Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20-46, 2007. Earlier version in FOCS '01 and arxiv:quant-ph/0106160. [doi:10.1137/S0097539702405620] 32, 33 · DOI
  68. HARTMUT KLAUCK, ROBERT ŠPALEK, AND RONALD DE WOLF: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput., 36(5):1472-1493, 2007. Earlier version in FOCS '04 and arxiv:quant-ph/0402123. [doi:10.1137/05063235X] 14, 32 THEORY OF COMPUTING LIBRARY, GRADUATE SURVEYS 2 (2011), pp. 1-54 · DOI
  69. GREG KUPERBERG: Random words, quantum statistics, central limits, random matrices. Methods Appl. Anal., 9(1):99-118, 2002. http://www.intlpress.com/MAA/p/2002/09_1/ MAA-09-1-099-118.pdf. Earlier version in arxiv:math/9909104. 42 · arXiv
  70. GREG KUPERBERG: A tracial quantum central limit theorem. Trans. Amer. Math. Soc., 357:459- 471, 2005. Earlier version in arxiv:math-ph/0202035. [doi:10.1090/S0002-9947-03-03449-4] · DOI
  71. EYAL KUSHILEVITZ AND NOAM NISAN: Communication Complexity. Cambridge University Press, 1997. 14
  72. J. C. LAGARIAS, H. W. LENSTRA, JR., AND C.-P. SCHNORR: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 10(4):333-348, 1990. [doi:10.1007/BF02128669] 38 · DOI
  73. SOPHIE LAPLANTE, TROY LEE, AND MARIO SZEGEDY: The quantum adversary method and classical formula size lower bounds. Comput. Complexity, 15(2):163-196, 2006. Earlier version in Proc. 20th IEEE Conf. Comput. Complex., 2005. [doi:10.1007/s00037-006-0212-7] 41 · DOI
  74. SOPHIE LAPLANTE AND FREDERIC MAGNIEZ: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In Proc. 19th IEEE Conf. Comput. Complex., pp. 294-304, 2004. Earlier version in arxiv:quant-ph/0311189. [doi:10.1109/CCC.2004.1313852] · DOI
  75. TROY LEE: A note on the sign degree of formulas, 2009. [arXiv:0909.4607] · arXiv
  76. TROY LEE, GIDEON SCHECHTMAN, AND ADI SHRAIBMAN: Lower bounds on quantum mul- tiparty communication complexity. In Proc. 24th IEEE Conf. Comput. Complex., pp. 254-262, 2009. [doi:10.1109/CCC.2009.24] · DOI
  77. A. K. LENSTRA, H. W. LENSTRA, JR., AND L. LOV ÁSZ: Factoring polynomials with rational coefficients. Math. Ann., 261(4):515-534, 1982. 37
  78. NIKOS LEONARDOS AND MICHAEL SAKS: Lower bounds on the randomized commu- nication complexity of read-once functions. Comput. Complexity, 19(2):153-181, 2010. [doi:10.1007/s00037-010-0292-2] 15 · DOI
  79. MING LI AND PAUL VIT ÁNYI: An Introduction to Kolmogorov Complexity and its Applications. Springer, Berlin, third edition, 2008. 4
  80. NATI LINIAL AND ADI SHRAIBMAN: Learning complexity vs communication complexity. Com- bin. Probab. Comput., 18(1-2):227-245, 2009. Earlier version in Proc. 22nd IEEE Conf. Computat. Complex., 2008. [doi:10.1017/S0963548308009656] 32 · DOI
  81. NATI LINIAL AND ADI SHRAIBMAN: Lower bounds in communication complexity based on factorization norms. Random Structures Algorithms, 34(3):368-394, 2009. Earlier version in STOC '07. [doi:10.1002/rsa.20232] 32 · DOI
  82. THEORY OF COMPUTING LIBRARY, GRADUATE SURVEYS 2 (2011), pp. 1-54 · DOI
  83. SATYANARAYANA V. LOKAM: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. J. Comput. System Sci., 63(3):449-473, 2001. Earlier version in FOCS '95. [doi:10.1006/jcss.2001.1786] 19, 21 · DOI
  84. SATYANARAYANA V. LOKAM: Quadratic lower bounds on matrix rigidity. In Proc. 3rd Ann. Conf. Theory and Appl. Models of Comput. (TAMC), volume 3959 of Lecture Notes in Comput. Sci., pp. 295-307. Springer, 2006. [doi:10.1007/11750321 28] · DOI
  85. SATYANARAYANA V. LOKAM: Complexity lower bounds using linear algebra. Found. Trends Theor. Comput. Sci., 4(1-2):1-155, 2008. [doi:10.1561/0400000011] 19 · DOI
  86. DANIELE MICCIANCIO: Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. SIAM J. Comput., 34(1):118-169, 2004. [doi:10.1137/S0097539703433511] · DOI
  87. DANIELE MICCIANCIO AND ODED REGEV: Lattice-based cryptography. In D. J. BERNSTEIN, J. BUCHMANN, AND E. DAHMEN, editors, Post-quantum Cryptography, pp. 147-191. Springer, 2009. [doi:10.1007/978-3-540-88702-7 5] · DOI
  88. GATIS MIDRIJANIS: Three lines proof of the lower bound for the matrix rigidity. Technical report, Arxiv e-print, June 2005. [arXiv:cs.CC/0506081] 21 · arXiv
  89. MARVIN MINSKY AND SEYMOUR PAPERT: Perceptrons. MIT Press, Cambridge, MA, 1968. Second, expanded edition 1988. 26
  90. ASHWIN NAYAK: Optimal lower bounds for quantum automata and random access codes. In Proc. 40th FOCS, pp. 369-376. IEEE Comp. Soc. Press, 1999. Earlier version in arxiv:quant-ph/9904093. [doi:10.1109/SFFCS.1999.814608] 10, 11 · DOI
  91. ASHWIN NAYAK AND JULIA SALZMAN: Limits on the ability of quantum states to con- vey classical messages. J. ACM, 53(1):184-206, 2006. Earlier version in STOC '02. [doi:10.1145/1120582.1120587] · DOI
  92. MICHAEL NIELSEN AND ISAAC L. CHUANG: Quantum Computation and Quantum Information. Cambridge University Press, 2000. 27, 35, 43
  93. RYAN O'DONNELL AND ROCCO SERVEDIO: New degree bounds for polynomial threshold functions. In Proc. 35th STOC, pp. 325-334. ACM Press, 2003. [doi:10.1145/780542.780592] · DOI
  94. RAMAMOHAN PATURI: On the degree of polynomials that approximate symmetric Boolean functions. In Proc. 24th STOC, pp. 468-474. ACM Press, 1992. [doi:10.1145/129712.129758] 22 · DOI
  95. RAMAMOHAN PATURI AND JANOS SIMON: Probabilistic communication complexity. J. Comput. System Sci., 33(1):106-123, 1986. Earlier version in FOCS '84. [doi:10.1016/0022-0000(86)90046- 2] · DOI
  96. CHRIS PEIKERT: Public-key cryptosystems from the worst-case shortest vector problem. In Proc. 41st STOC, pp. 333-342. ACM Press, 2009. [doi:10.1145/1536414.1536461] · DOI
  97. JAIKUMAR RADHAKRISHNAN, PRANAB SEN, AND S. VENKATESH: The quantum complexity of set membership. Algorithmica, 34(4):462-479, 2002. Earlier versions in FOCS '00 and arvix:quant-ph/0007021. [doi:10.1007/s00453-002-0979-0] 40 · DOI
  98. ALEXANDER A. RAZBOROV: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics, 67(1):145-159, 2003. Earlier version in arxiv:quant-ph/0204025. [doi:10.1070/IM2003v067n01ABEH000422] 32, 33 · DOI
  99. ODED REGEV: New lattice based cryptographic constructions. J. ACM, 51(6):899-942, 2004. Earlier version in STOC '03. [doi:10.1145/1039488.1039490] · DOI
  100. ODED REGEV: Quantum computation and lattice problems. SIAM J. Comput., 33(3):738-760, 2004. Earlier version in FOCS '02. [doi:10.1137/S0097539703440678] 37 · DOI · Paper page
  101. ODED REGEV: On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Earlier version in STOC '05. [doi:10.1145/1568318.1568324] · DOI · Paper page
  102. BEN W. REICHARDT: Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. 50th FOCS, pp. 544-551. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.55] 22, 35 · DOI
  103. RENATO RENNER AND STEFAN WOLF: New bounds in secret-key agreement: The gap between formation and secrecy extraction. In Proc. Advances in Cryptology -Eurocrypt, volume 2656 of Lecture Notes in Comput. Sci., pp. 562-577. Springer, 2003. [doi:10.1007/3-540-39200-9 35] · DOI
  104. THEODORE J. RIVLIN AND E. W. CHENEY: A comparison of uniform approximations on an interval and a finite subset thereof. SIAM J. Numer. Anal., 3(2):311-320, 1966. 33
  105. PRANAB SEN AND S. VENKATESH: Lower bounds for predecessor searching in the cell probe model. J. Comput. System Sci., 74(3):364-385, 2008. [doi:10.1016/j.jcss.2007.06.016] · DOI
  106. ALEXANDER A. SHERSTOV: Approximate inclusion-exclusion for arbitrary symmetric functions. In Proc. 23rd IEEE Conf. Comput. Complex., pp. 112-123, 2008. [doi:10.1109/CCC.2008.18] · DOI
  107. ALEXANDER A. SHERSTOV: Halfspace matrices. Comput. Complexity, 17(2):149-178, 2008. [doi:10.1007/s00037-008-0242-4] 32 · DOI
  108. PETER W. SHOR: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484-1509, 1997. Earlier versions in FOCS '94 and arxiv:quant-ph/9508027. [doi:10.1137/S0097539795293172] 4 · DOI · Paper page
  109. DANIEL R. SIMON: On the power of quantum computation. SIAM J. Comput., 26(5):1474-1483, 1997. Earlier version in FOCS '94. [doi:10.1137/S0097539796298637] 41 · DOI · Paper page
  110. KOJI TSUDA, GUNNAR R ÄTSCH, AND MANFRED WARMUTH: Matrix exponentiated gradient updates for on-line learning and Bregman projection. J. Mach. Learn. Res., 6:995-1018, 2005. http://www.jmlr.org/papers/volume6/tsuda05a/tsuda05a.pdf. 42
  111. LESLIE G. VALIANT: Graph-theoretic arguments in low-level complexity. In Proc. 6th Conf. Math. Found. Comput. Sci. (MFCS), volume 53 of Lecture Notes in Comput. Sci., pp. 162-176. Springer, 1977. [doi:10.1007/3-540-08353-7 135] 18 · DOI
  112. STEPHANIE WEHNER AND RONALD DE WOLF: Improved lower bounds for locally decodable codes and private information retrieval. In Proc. 32nd Intern. Colloq. Autom. Lang. Program. (ICALP), volume 3580 of Lecture Notes in Comput. Sci., pp. 1424-1436, 2005. Earlier version in arxiv:quant-ph/0403140. [doi:10.1007/11523468 115] 17 · DOI
  113. DAVID P. WOODRUFF: A quadratic lower bound for three-query linear locally decodable codes over any field. In Proc. 13th Intern. Workshop Approx. Randomization Comb. Optim. (APPROX), Lecture Notes in Comput. Sci., pp. 766-779. Springer, 2010. [doi:10.1007/978-3-642-15369-3 57] · DOI
  114. ANDREW CHI-CHIH YAO: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209-213. ACM Press, 1979. [doi:10.1145/800135.804414] 14 · DOI
  115. SERGEY YEKHANIN: Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008. Earlier version in STOC '07. [doi:10.1145/1326554.1326555] · DOI
  116. THEORY OF COMPUTING LIBRARY, GRADUATE SURVEYS 2 (2011), pp. 1-54 · DOI

Cited by

Sorted by citations

Metadata

Authors
Drucker, A., & de Wolf, R.
ORCID
Ronald de Wolf
Venue
Theory of Computing
Publisher
Theory of Computing Exchange
Published
2011
Volume
1
Issue
1
Pages
1-54
ISSN
1557-2862 (ISSN-L)
DOI
10.4086/toc.gs.2011.002
OpenAlex
W2095739278
Cited by
41
References
3
Citations by year
2024: 2 · 2023: 1 · 2019: 2 · 2018: 2 · 2017: 5 · 2016: 5 · 2015: 3 · 2014: 6 · 2013: 3 · 2012: 3
FWCI
4.73
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • Theory of Computing (publishedVersion, cc-by)
  • UvA-DARE (University of Amsterdam) (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands (submittedVersion)
  • Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
  • UvA-DARE (University of Amsterdam) (submittedVersion, cc-by)
  • arXiv (Cornell University)
  • Electronic colloquium on computational complexity
Funders
  • European Commission (015848)
  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek
  • Defense Advanced Research Projects Agency
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
quantum algorithms, quantum complexity, coding theory, communication complexity, polynomial approximation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review