Document Open Access Logo

Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials

Author Richard Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.6.pdf
  • Filesize: 0.56 MB
  • 24 pages

Document Identifiers

Author Details

Richard Ryan Williams
  • EECS and CSAIL, MIT, 32 Vassar St., Cambridge MA, USA

Funding

  • Williams, Richard Ryan: Supported by NSF CCF-1553288. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Cite AsGet BibTex

Richard Ryan Williams. Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.6

Abstract

We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over R) of functions from some "simple" class C. In particular, given C we are interested in finding low-complexity functions lacking sparse representations. When C forms a basis for the space of Boolean functions (e.g., the set of PARITY functions or the set of conjunctions) this sort of problem has a well-understood answer; the problem becomes interesting when C is "overcomplete" and the set of functions is not linearly independent. We focus on the cases where C is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of low-degree polynomials over a finite field, all of which are well-studied in different contexts. We provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for "semi-explicit" Boolean functions. Let alpha(n) be an unbounded function such that n^{alpha(n)} is time constructible (e.g. alpha(n) = log^*(n)). We show: - Functions in NTIME[n^{alpha(n)}] that require super-polynomially many linear threshold functions to represent (depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds). - Functions in NTIME[n^{alpha(n)}] that require super-polynomially many ReLU gates to represent (depth-two neural networks with ReLU activation function). - Functions in NTIME[n^{alpha(n)}] that require super-polynomially many O(1)-degree F_p-polynomials to represent exactly, for every prime p (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in E^{NP} requiring 2^{Omega(n)} linear combinations. - Functions in NTIME[n^{poly(log n)}] that require super-polynomially many ACC ° THR circuits to represent exactly (further generalizing the recent lower bounds of Murray and the author). We also obtain "fixed-polynomial" lower bounds for functions in NP, for the first three representation classes. All our lower bounds are obtained via algorithms for analyzing linear combinations of simple functions in the above scenarios, in ways which substantially beat exhaustive search.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Computer systems organization → Neural networks
Keywords
  • linear threshold functions
  • lower bounds
  • neural networks
  • low-degree polynomials

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In FOCS, pages 25-36, 2017. Google Scholar
  2. Josh Alman, Timothy M. Chan, and R. Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In FOCS, pages 467-476, 2016. Google Scholar
  3. Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv:1611.01491, 2016. Google Scholar
  4. László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, and Xiaoming Sun. Weights of exact threshold functions. In Mathematical Foundations of Computer Science, pages 66-77, 2010. Google Scholar
  5. David A. Mix Barrington, Howard Straubing, and Denis Thérien. Non-uniform automata over groups. Inf. Comput., 89(2):109-132, 1990. Google Scholar
  6. Richard Beigel and Jun Tarui. On ACC. Computational Complexity, pages 350-366, 1994. Google Scholar
  7. Eli Ben-Sasson and Emanuele Viola. Short PCPs with projection queries. In ICALP, pages 163-173, 2014. Google Scholar
  8. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546-563, 2009. Google Scholar
  9. Jean Bourgain. Estimation of certain exponential sums arising in complexity theory. C.R. Acad. Sci. Paris Ser. I, 340:627-631, 2005. Google Scholar
  10. Jin-yi Cai, Frederic Green, and Thomas Thierauf. On the correlation of symmetric functions. Mathematical Systems Theory, 29(3):245-258, 1996. Google Scholar
  11. Chris Calabro. A lower bound on the size of series-parallel graphs dense in long paths. Electronic Colloquium on Computational Complexity (ECCC), 15(110), 2008. Google Scholar
  12. Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and more: Quickly derandomizing Razborov-Smolensky. In SODA, pages 1246-1255, 2016. Google Scholar
  13. Arkadev Chattopadhyay and Nikhil S. Mande. Weights at the bottom matter when the top is heavy. Electronic Colloquium on Computational Complexity (ECCC), 24:83, 2017. Google Scholar
  14. Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-case lower bounds and satisfiability algorithms for small threshold circuits. In CCC, pages 1:1-1:35, 2016. Google Scholar
  15. Amit Daniely. Depth separation for neural networks. In Proceedings of COLT, pages 690-696, 2017. Google Scholar
  16. Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Proceedings of COLT, pages 907-940, 2016. Google Scholar
  17. Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O'Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer. Real Analysis in Computer Science: A collection of open problems, Simons Institute, 2014. URL: https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf.
  18. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. Google Scholar
  19. Anna Gál and Vladimir Trifonov. On the correlation between parity and modular polynomials. Theory Comput. Syst., 50(3):516-536, 2012. Google Scholar
  20. Frederic Green. The correlation between parity and quadratic polynomials mod 3. Journal of Computer and System Sciences, 69(1):28-44, 2004. Google Scholar
  21. Jacques Hadamard. Résolution d'une question relative aux déterminants. Bull. Sci. Math., 17:30-31, 1893. Google Scholar
  22. András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. J. Comput. Syst. Sci., 46(2):129-154, 1993. Google Scholar
  23. Kristoffer Arnsfelt Hansen and Vladimir V Podolskii. Exact threshold circuits. In CCC, pages 270-279, 2010. Google Scholar
  24. Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1:113-129, 1991. Google Scholar
  25. Hamed Hatami, Pooya Hatami, and Shachar Lovett. Higher-order Fourier analysis and applications. Manuscript, 2016. URL: https://cseweb.ucsd.edu/~slovett/files/survey-higher_order_fourier.pdf.
  26. Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. JACM, 21(2):277-292, 1974. Google Scholar
  27. Hamid Jahanjou, Eric Miles, and Emanuele Viola. Local reductions. In Proceedings of ICALP, pages 749-760, 2015. Google Scholar
  28. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In STOC, pages 633-643, 2016. Google Scholar
  29. Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu. Beating brute force for systems of polynomial equations over finite fields. In SODA, pages 2190-2202, 2017. Google Scholar
  30. Shachar Lovett. Personal communication, 2017. Google Scholar
  31. Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets. SIAM Journal on Computing, 26(3):708-732, 1997. Google Scholar
  32. Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In COCOON, Springer LNCS 1627, pages 210-220, 1999. Google Scholar
  33. Anirbit Mukherjee and Amitabh Basu. Lower bounds over Boolean inputs for deep neural networks with ReLU gates. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1711.03073.
  34. S. Muroga, I. Toda, and S. Takasu. Theory of majority decision elements. Journal of the Franklin Institute, 271:376-418, 1961. Google Scholar
  35. Cody Murray and Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: An easy witness lemma for NP and NQP. Electronic Colloquium on Computational Complexity (ECCC), TR17-188, 2017. Google Scholar
  36. Noam Nisan. The communication complexity of threshold gates. In Proceedings of "Combinatorics, Paul Erdos is Eighty", pages 301-315, 1994. Google Scholar
  37. Mihai Pǎtraşcu and Ryan Williams. On the possibility of faster sat algorithms. In SODA, pages 1065-1075, 2010. Google Scholar
  38. Vwani P. Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu. Lower bounds on threshold and related circuits via communication complexity. IEEE Transactions on Information Theory, 40(2):467-474, 1994. Google Scholar
  39. Itay Safran and Ohad Shamir. Depth-width tradeoffs in approximating natural functions with neural networks. In International Conference on Machine Learning, pages 2979-2987, 2017. Google Scholar
  40. Rahul Santhanam. Circuit lower bounds for Merlin-Arthur classes. SIAM J. Comput., 39(3):1038-1061, 2009. Google Scholar
  41. Rahul Santhanam and Ryan Williams. On medium-uniformity and circuit lower bounds. In IEEE Conf. Computational Complexity, pages 15-23, 2013. Google Scholar
  42. Joel Seiferas, Michael Fischer, and Albert Meyer. Separating nondeterministic time complexity classes. Journal of the ACM, 25(1):146-167, jan 1978. Google Scholar
  43. Suguru Tamaki. A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates. Electronic Colloquium on Computational Complexity (ECCC), 23:100, 2016. Google Scholar
  44. Matus Telgarsky. benefits of depth in neural networks. In Proceedings of COLT, pages 1517-1539, 2016. Google Scholar
  45. Roei Tell. Proving that prBPP=prP is as hard as "almost" proving that P ≠ NP. Electronic Colloquium on Computational Complexity (ECCC), 18(3), 2018. Google Scholar
  46. S. Toda. PP is as hard as the polynomial-time hierarchy. sicomp, 20(5):865-877, 1991. Google Scholar
  47. L. G. Valiant. Graph-theoretic arguments in low-level complexity. In J. Gruska, editor, MFCS, volume 53 of LNCS, pages 162-176, Tatranská Lomnica, Czechoslovakia, sep 1977. Springer. Google Scholar
  48. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal on Computing, 42(3):831-854, 2013. Google Scholar
  49. Emanuele Viola. Guest column: correlation bounds for polynomials over 0, 1. SIGACT News, 40(1):27-44, 2009. Google Scholar
  50. Ryan Williams. A casual tour around a circuit complexity bound. SIGACT News, 42(3):54-76, 2011. Google Scholar
  51. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. sicomp, 42(3):1218-1244, 2013. Google Scholar
  52. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. In STOC, pages 194-202, 2014. Google Scholar
  53. Ryan Williams. Nonuniform ACC circuit lower bounds. JACM, 61(1):2, 2014. Google Scholar
  54. Ryan Williams. Counting solutions to polynomial systems via reductions. In Raimund Seidel, editor, 1st Symposium on Simplicity in Algorithms (SOSA 2018), pages 6:1-6:15, 2018. Google Scholar
  55. R. O. Winder. Threshold Logic. PhD thesis, Princeton University, 1962. Preliminary version in FOCS'60. Google Scholar
  56. Stanislav Žák. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327-333, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact