Alexander A. Sherstov
ABSTRACT
A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has been studied for decision trees, circuits, automata, data structures, broadcast networks, communication protocols, and other models.
Buhrman et al. (2003) posed the noisy computation problem for real polynomials. We give a complete solution to this problem. For any polynomial p:{0,1}n->[-1,1], we construct a polynomial probust:Rn->R of degree O(deg p+log(1/ε)) that epsilon-approximates p and is robust to noise in the inputs: |p(x)-probust(x+δ)|<ε for all x∈ 0,1}n and all delta∈[-1/3,1/3]n. This result is optimal with respect to all parameters. We construct probust explicitly for each p. Previously, it was open to give such a construction even for p=x1 ⊕ x2 ⊕ ... ⊕ xn (Buhrman et al., 2003). The proof contributes a technique of independent interest, which allows one to force partial cancellation of error terms in a polynomial.
Supplemental Material
- S. Aaronson. Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1--28, 2005.Google Scholar
Cross Ref
- S. Aaronson and Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595--605, 2004. Google ScholarDigital Library
- A. Ambainis. Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci., 72(2):220--238, 2006. Google ScholarDigital Library
- A. Ambainis, A. M. Childs, B. Reichardt, R. Spalek, and S. Zhang. Any AND-OR formula of size N can be evaluated in time N1/2 o(1) on a quantum computer. In Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 363--372, 2007. Google ScholarDigital Library
- J. Aspnes, R. Beigel, M. L. Furst, and S. Rudich. The expressive power of voting polynomials. Combinatorica, 14(2):135--148, 1994.Google ScholarCross Ref
- R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778--797, 2001. Google ScholarDigital Library
- P. Beame, T. Huynh, and T. Pitassi. Hardness amplification in proof complexity. In Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing (STOC), pages 87--96, 2010. Google ScholarDigital Library
- P. Beame and D.-T. Huynh-Ngoc. Multiparty communication complexity and threshold circuit complexity of AC0. In Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 53--62, 2009. Google ScholarDigital Library
- R. Beigel, N. Reingold, and D. A. Spielman. ¶P is closed under intersection. J. Comput. Syst. Sci., 50(2):191--202, 1995. Google ScholarDigital Library
- M. Braverman and A. Rao. Towards coding for maximum errors in interactive communication. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), pages 159--166, 2011. Google ScholarDigital Library
- H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), pages 63--68, 1998. Google ScholarDigital Library
- H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. In Proceedings of the Fortieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 358--368, 1999. Google ScholarDigital Library
- H. Buhrman, I. Newman, H. Röhrig, and R. de Wolf. Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379--395, 2007. Preliminary version at http://arxiv.org/abs/quant-ph/0309220v1, September 2003. Google ScholarDigital Library
- H. Buhrman, N. K. Vereshchagin, and R. de Wolf. On computation and communication with small bias. In Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity (CCC), pages 24--32, 2007. Google ScholarDigital Library
- H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC), pages 120--130, 2001. Google ScholarDigital Library
- E. W. Cheney. Introduction to Approximation Theory. Chelsea Publishing, New York, 2nd edition, 1982.Google Scholar
- C. Dutta, Y. Kanoria, D. Manjunath, and J. Radhakrishnan. A tight lower bound for parity in noisy communication networks. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1056--1065, 2008. Google ScholarDigital Library
- C. Dutta and J. Radhakrishnan. Lower bounds for noisy wireless networks using sampling algorithms. In Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 394--402, 2008. Google ScholarDigital Library
- A. Eremenko and P. Yuditskii. Uniform approximation of sgn(x) by polynomials and entire functions. J. d'Analyse Mathématique, 101:313--324, 2007.Google ScholarCross Ref
- W. S. Evans and N. Pippenger. Average-case lower bounds for noisy Boolean decision trees. SIAM J. Comput., 28(2):433--446, 1998. Google ScholarDigital Library
- W. S. Evans and L. J. Schulman. Signal propagation and noisy circuits. IEEE Transactions on Information Theory, 45(7):2367--2373, 1999. Google ScholarDigital Library
- E. Farhi, J. Goldstone, and S. Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169--190, 2008.Google ScholarCross Ref
- U. Feige. On the complexity of finite random functions. Inf. Process. Lett., 44(6):295--296, 1992. Google ScholarDigital Library
- U. Feige and J. Kilian. Finding OR in a noisy broadcast network. Inf. Process. Lett., 73(1--2):69--75, 2000. Google ScholarDigital Library
- U. Feige, P. Raghavan, D. Peleg, and E. Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001--1018, 1994. Google ScholarDigital Library
- P. Gács and A. Gál. Lower bounds for the complexity of reliable Boolean circuits with noisy gates. IEEE Transactions on Information Theory, 40(2):579--583, 1994. Google ScholarDigital Library
- R. G. Gallager. Finding parity in a simple broadcast network. IEEE Transactions on Information Theory, 34(2):176--180, 1988. Google ScholarDigital Library
- R. Gelles, A. Moitra, and A. Sahai. Efficient and explicit coding for interactive communication. In Proceedings of the Fifty-Second Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011. To appear. Google ScholarDigital Library
- N. Goyal, G. Kindler, and M. E. Saks. Lower bounds for the noisy broadcast problem. SIAM J. Comput., 37(6):1806--1841, 2008. Google ScholarDigital Library
- P. Høyer, M. Mosca, and R. de Wolf. Quantum search on bounded-error inputs. In Proc. of the 30th International Colloquium on Automata, Languages, and Programming (ICALP), pages 291--299, 2003. Google ScholarDigital Library
- J. Kahn, N. Linial, and A. Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica, 16(4):465--477, 1996.Google ScholarCross Ref
- A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio. Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777--1805, 2008. Google ScholarDigital Library
- H. Klauck, R. Spalek, and R. de Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput., 36(5):1472--1493, 2007. Google ScholarDigital Library
- D. J. Kleitman, F. T. Leighton, and Y. Ma. On the design of reliable Boolean circuits that contain partially unreliable gates. J. Comput. Syst. Sci., 55(3):385--401, 1997. Google ScholarDigital Library
- A. R. Klivans and R. A. Servedio. Learning DNF in time 2~O(n1/3). J. Comput. Syst. Sci., 68(2):303--318, 2004. Google ScholarDigital Library
- A. R. Klivans and A. A. Sherstov. Unconditional lower bounds for learning intersections of halfspaces. Machine Learning, 69(2--3):97--114, 2007. Preliminary version in Proceedings of the Nineteenth Annual Conference on Computational Learning Theory (COLT), 2006. Google ScholarDigital Library
- A. R. Klivans and A. A. Sherstov. Lower bounds for agnostic learning via approximate rank. Computational Complexity, 19(4):581--604, 2010. Preliminary version in Proceedings of the Twentieth Annual Conference on Computational Learning Theory (COLT), 2007. Google ScholarDigital Library
- M. Krause and P. Pudlák. On the computational power of depth-2 circuits with threshold and modulo gates. Theor. Comput. Sci., 174(1--2):137--156, 1997. Google ScholarDigital Library
- M. Krause and P. Pudlák. Computing Boolean functions by polynomials and threshold circuits. Comput. Complex., 7(4):346--370, 1998. Google ScholarDigital Library
- E. Kushilevitz and Y. Mansour. Computation in noisy radio networks. SIAM J. Discrete Math., 19(1):96--108, 2005. Google ScholarDigital Library
- N. Linial and N. Nisan. Approximate inclusion-exclusion. Combinatorica, 10(4):349--365, 1990.Google ScholarCross Ref
- M. L. Minsky and S. A. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass., 1969. Google ScholarDigital Library
- I. Newman. Computing in fault tolerance broadcast networks. In Proceedings of the Nineteenth Annual IEEE Conference on Computational Complexity (CCC), pages 113--122, 2004. Google ScholarDigital Library
- N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301--313, 1994. Google ScholarDigital Library
- R. Paturi and M. E. Saks. Approximating threshold circuits by rational functions. Inf. Comput., 112(2):257--272, 1994. Google ScholarDigital Library
- N. Pippenger. On networks of noisy gates. In Proceedings of the Twenty-Sixth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 30--38, 1985. Google ScholarDigital Library
- A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics, 67:145--159, 2002.Google Scholar
- A. A. Razborov and A. A. Sherstov. The sign-rank of $\AC^0$. SIAM J. Comput., 39(5):1833--1855, 2010. Preliminary version in Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008. Google ScholarDigital Library
- R. Reischuk and B. Schmeltz. Reliable computation with noisy circuits and decision trees--a general nłog n lower bound. In Proceedings of the Thirty-Second Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 602--611, 1991. Google ScholarDigital Library
- T. J. Rivlin. An Introduction to the Approximation of Functions. Dover Publications, New York, 1981.Google Scholar
- L. J. Schulman. Communication on noisy channels: A coding theorem for computation. In Proceedings of the Thirty-Third Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 724--733, 1992. Google ScholarDigital Library
- L. J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745--1756, 1996. Google ScholarDigital Library
- A. A. Sherstov. Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59--93, 2008.Google Scholar
- A. A. Sherstov. Approximate inclusion-exclusion for arbitrary symmetric functions. Computational Complexity, 18(2):219--247, 2009. Preliminary version in Proceedings of the Twenty-Third Annual IEEE Conference on Computational Complexity (CCC), 2008. Google ScholarDigital Library
- A. A. Sherstov. The intersection of two halfspaces has high threshold degree. In Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 343--362, 2009. Google ScholarDigital Library
- A. A. Sherstov. Separating AC0 from depth-2 majority circuits. SIAM J. Comput., 38(6):2113--2129, 2009. Preliminary version in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC), 2007. Google ScholarDigital Library
- A. A. Sherstov. Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. In Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing (STOC), pages 523--532, 2010. Google ScholarDigital Library
- K.-Y. Siu, V. P. Roychowdhury, and T. Kailath. Rational approximation techniques for analysis of neural networks. IEEE Transactions on Information Theory, 40(2):455--466, 1994. Google ScholarDigital Library
- D. A. Spielman. Highly fault-tolerant parallel computation. In Proceedings of the Thirty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 154--163, 1996. Google ScholarDigital Library
- M. Szegedy and X. Chen. Computing Boolean functions from multiple faulty copies of input bits. Theor. Comput. Sci., 321(1):149--170, 2004. Google ScholarDigital Library
- J. Tarui and T. Tsukiji. Learning DNF by approximating inclusion-exclusion formulae. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (CCC), pages 215--221, 1999. Google ScholarDigital Library
- R. de Wolf. A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. Quantum Information and Computation, 8(10):943--950, 2008. Google ScholarDigital Library
Index Terms
- Making polynomials robust to noise
Recommendations
Approximation by polynomials and smooth functions in Sobolev spaces with respect to measures
The density of polynomials is straightforward to prove in Sobolev spaces Wk,p((a, b)), but there exist only partial results in weighted Sobolev spaces; here we improve some of these theorems. The situation is more complicated in infinite intervals, even ...
Holomorphic Jackson's theorems in polydiscs
The purpose of this article is to establish Jackson-type inequality in the polydiscs U^N of C^N for holomorphic spaces X, such as Bergman-type spaces, Hardy spaces, polydisc algebra and Lipschitz spaces. Namely,E"k"@?(f,X)@?@w1/k->,f,X,where E"k"@?(f,X) ...
An integral formula for generalized Gegenbauer polynomials and Jacobi polynomials
The generalized Gegenbauer polynomials are orthogonal polynomials with respect to the weight function |x|^2^@m(1-x^2)^@l^-^1^/^2. An integral formula for these polynomials is proved, which serves as a transformation between h-harmonic polynomials ...
Comments