Making Polynomials Robust to Noise
Theory of Computing, Volume 9(18), pp. 593-615, 2013
Bibliography with links to cited articles
[1] Scott Aaronson: Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1–28, 2005. Preliminary version in CCC’04. [doi:10.4086/toc.2005.v001a001]
[2] Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. Preliminary version in STOC’02. [doi:10.1145/1008731.1008735]
[3] James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Preliminary version in STOC’91. [doi:10.1007/BF01215346]
[4] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in FOCS’98. [doi:10.1145/502090.502097]
[5] Paul Beame and Dang-Trinh Huynh-Ngoc: Multiparty communication complexity and threshold circuit size of AC0. SIAM Journal on Computing, 41(3):484–518, 2012. Preliminary version in FOCS’09. [doi:10.1137/100792779]
[6] Richard Beigel, Nick Reingold, and Daniel A. Spielman: PP is closed under intersection. J. Comput. System Sci., 50(2):191–202, 1995. Preliminary version in STOC’91. [doi:10.1006/jcss.1995.1017]
[7] Mark Braverman and Anup Rao: Towards coding for maximum errors in interactive communication. In Proc. 43rd STOC, pp. 159–166. ACM Press, 2011. [doi:10.1145/1993636.1993659]
[8] Harry Buhrman, Richard Cleve, and Avi Wigderson: Quantum vs. classical communication and computation. In Proc. 30th STOC, pp. 63–68. ACM Press, 1998. [doi:10.1145/276698.276713]
[9] 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. [doi:10.1109/SFFCS.1999.814607]
[10] Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf: Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379–395, 2007. Preliminary version in STACS’05. [doi:10.1007/s00224-006-1313-z]
[11] Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. on Computational Complexity (CCC’07), pp. 24–32. IEEE Comp. Soc. Press, 2007. (See also SAGA’07.). [doi:10.1109/CCC.2007.18]
[12] Harry Buhrman and Ronald de Wolf: Communication complexity lower bounds by polynomials. In Proc. 16th IEEE Conf. on Computational Complexity (CCC’01), pp. 120–130. IEEE Comp. Soc. Press, 2001. [doi:10.1109/CCC.2001.933879]
[13] Elliott W. Cheney: Introduction to Approximation Theory. Chelsea Publishing, New York, 2nd edition, 1982.
[14] Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, and Jaikumar Radhakrishnan: A tight lower bound for parity in noisy communication networks. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’08), pp. 1056–1065. ACM Press, 2008. [ACM:1347198]
[15] Chinmoy Dutta and Jaikumar Radhakrishnan: Lower bounds for noisy wireless networks using sampling algorithms. In Proc. 49th FOCS, pp. 394–402. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.72]
[16] Alexandre Eremenko and Peter Yuditskii: Uniform approximation of sgn x by polynomials and entire functions. J. d’Analyse Mathématique, 101(1):313–324, 2007. [doi:10.1007/s11854-007-0011-3]
[17] William S. Evans and Nicholas Pippenger: Average-case lower bounds for noisy Boolean decision trees. SIAM J. Comput., 28(2):433–446, 1998. Preliminary version in STOC’96. [doi:10.1137/S0097539796310102]
[18] William S. Evans and Leonard J. Schulman: Signal propagation and noisy circuits. IEEE Trans. Inform. Theory, 45(7):2367–2373, 1999. Preliminary version in FOCS’93. [doi:10.1109/18.796377]
[19] Uriel Feige: On the complexity of finite random functions. Inform. Process. Lett., 44(6):295–296, 1992. [doi:10.1016/0020-0190(92)90102-2]
[20] Uriel Feige and Joe Kilian: Finding OR in a noisy broadcast network. Inform. Process. Lett., 73(1-2):69–75, 2000. [doi:10.1016/S0020-0190(00)00002-8]
[21] Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal: Computing with noisy information. SIAM J. Comput., 23(5):1001–1018, 1994. Preliminary version in STOC’90. [doi:10.1137/S0097539791195877]
[22] Péter Gács and Anna Gál: Lower bounds for the complexity of reliable Boolean circuits with noisy gates. IEEE Trans. Inform. Theory, 40(2):579–583, 1994. Preliminary version in FOCS’91. [doi:10.1109/18.312190]
[23] Robert G. Gallager: Finding parity in a simple broadcast network. IEEE Trans. Inform. Theory, 34(2):176–180, 1988. [doi:10.1109/18.2626]
[24] Ran Gelles, Ankur Moitra, and Amit Sahai: Efficient and explicit coding for interactive communication. In Proc. 52nd FOCS, pp. 768–777. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.51]
[25] Navin Goyal, Guy Kindler, and Michael E. Saks: Lower bounds for the noisy broadcast problem. SIAM J. Comput., 37(6):1806–1841, 2008. Preliminary version in FOCS’05. [doi:10.1137/060654864]
[26] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Boston, Mass., USA, 2nd edition, 1994.
[27] Peter Høyer, Michele Mosca, and Ronald de Wolf: Quantum search on bounded-error inputs. In Proc. 30th Internat. Colloq. on Automata, Languages and Programming (ICALP’03), pp. 291–299. Springer, 2003. [doi:10.1007/3-540-45061-0_25]
[28] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio: Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008. Preliminary version in FOCS’05. [doi:10.1137/060649057]
[29] 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. Preliminary version in FOCS’04. [doi:10.1137/05063235X]
[30] Daniel J. Kleitman, Frank Thomson Leighton, and Yuan Ma: On the design of reliable Boolean circuits that contain partially unreliable gates. J. Comput. System Sci., 55(3):385–401, 1997. Preliminary version in FOCS’94. [doi:10.1006/jcss.1997.1531]
[31] Adam R. Klivans and Rocco A. Servedio: Learning DNF in time 2Õ(n1∕3) . J. Comput. System Sci., 68(2):303–318, 2004. Preliminary version in STOC’01. [doi:10.1016/j.jcss.2003.07.007]
[32] Adam R. Klivans and Alexander A. Sherstov: Unconditional lower bounds for learning intersections of halfspaces. Machine Learning, 69(2-3):97–114, 2007. Preliminary version in COLT’06. [doi:10.1007/s10994-007-5010-1]
[33] Adam R. Klivans and Alexander A. Sherstov: Lower bounds for agnostic learning via approximate rank. Comput. Complexity, 19(4):581–604, 2010. Preliminary version in COLT’07. [doi:10.1007/s00037-010-0296-y]
[34] Matthias Krause and Pavel Pudlák: On the computational power of depth-2 circuits with threshold and modulo gates. Theoret. Comput. Sci., 174(1-2):137–156, 1997. Preliminary version in STOC’94. [doi:10.1016/S0304-3975(96)00019-9]
[35] Matthias Krause and Pavel Pudlák: Computing Boolean functions by polynomials and threshold circuits. Comput. Complexity, 7(4):346–370, 1998. Preliminary version in FOCS’95. [doi:10.1007/s000370050015]
[36] Eyal Kushilevitz and Yishay Mansour: Computation in noisy radio networks. SIAM J. Discrete Math., 19(1):96–108, 2005. Preliminary version in SODA’98. [doi:10.1137/S0895480103434063]
[37] Vladimir A. Markov: On functions of least deviation from zero in a given interval. Russian Academy of Sciences, St. Petersburg, 1892. In Russian.
[38] Ilan Newman: Computing in fault tolerant broadcast networks and noisy decision trees. Random Structures & Algorithms, 34(4):478–501, 2009. Preliminary version in CCC’04. [doi:10.1002/rsa.20240]
[39] Ramamohan Paturi and Michael E. Saks: Approximating threshold circuits by rational functions. Inform. and Comput., 112(2):257–272, 1994. Preliminary version in FOCS’90. [doi:10.1006/inco.1994.1059]
[40] Nicholas Pippenger: On networks of noisy gates. In Proc. 26th FOCS, pp. 30–38. IEEE Comp. Soc. Press, 1985. [doi:10.1109/SFCS.1985.41]
[41] Alexander A. Razborov: Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145–159, 2003. [doi:10.1070/IM2003v067n01ABEH000422]
[42] Alexander A. Razborov and Alexander A. Sherstov: The sign-rank of AC0. SIAM J. Comput., 39(5):1833–1855, 2010. Preliminary version in FOCS’08. [doi:10.1137/080744037]
[43] Rüdiger Reischuk and Bernd Schmeltz: Reliable computation with noisy circuits and decision trees–a general nlog n lower bound. In Proc. 32nd FOCS, pp. 602–611. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SFCS.1991.185425]
[44] Theodore J. Rivlin: An Introduction to the Approximation of Functions. Dover Publications, New York, 1981.
[45] Leonard J. Schulman: Communication on noisy channels: A coding theorem for computation. In Proc. 33rd FOCS, pp. 724–733. IEEE Comp. Soc. Press, 1992. [doi:10.1109/SFCS.1992.267778]
[46] Leonard J. Schulman: Coding for interactive communication. IEEE Trans. Inform. Theory, 42(6):1745–1756, 1996. Preliminary versions in FOCS’92 and STOC’93. [doi:10.1109/18.556671]
[47] Alexander A. Sherstov: Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59–93, 2008. EATCS.
[48] Alexander A. Sherstov: The intersection of two halfspaces has high threshold degree. In Proc. 50th FOCS, pp. 343–362. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.18]
[49] Alexander A. Sherstov: Separating AC0 from depth-2 majority circuits. SIAM J. Comput., 38(6):2113–2129, 2009. Preliminary version in STOC’07. [doi:10.1137/08071421X]
[50] Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. In Proc. 42nd STOC, pp. 523–532. ACM Press, 2010. [doi:10.1145/1806689.1806762]
[51] Kai-Yeung Siu, Vwani P. Roychowdhury, and Thomas Kailath: Rational approximation techniques for analysis of neural networks. IEEE Trans. Inform. Theory, 40(2):455–466, 1994. Preliminary version in NIPS’92. [doi:10.1109/18.312168]
[52] Daniel A. Spielman: Highly fault-tolerant parallel computation. In Proc. 37th FOCS, pp. 154–163. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548474]
[53] Mario Szegedy and Xiaomin Chen: Computing Boolean functions from multiple faulty copies of input bits. Theoret. Comput. Sci., 321(1):149–170, 2004. Preliminary version in LATIN’02. [doi:10.1016/j.tcs.2003.07.001]
[54] Jun Tarui and Tatsuie Tsukiji: Learning DNF by approximating inclusion-exclusion formulae. In Proc. 14th IEEE Conf. on Computational Complexity (CCC’99), pp. 215–221. IEEE Comp. Soc. Press, 1999. [doi:10.1109/CCC.1999.766279]