Document Open Access Logo

On the Limits of Gate Elimination

Authors Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.46.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Alexander Golovnev
Edward A. Hirsch
Alexander Knop
Alexander S. Kulikov

Cite As Get BibTex

Alexander Golovnev, Edward A. Hirsch, Alexander Knop, and Alexander S. Kulikov. On the Limits of Gate Elimination. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.46

Abstract

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There  has been a (very slow) progress in proving linear lower bounds with the latest record of 3 1/86*n-o(n). All known lower bounds are based on the so-called gate elimination technique. A typical gate elimination argument shows that it is possible to eliminate several gates from an optimal circuit by making one or several substitutions to the input variables and repeats this inductively. In this note we prove that this method cannot achieve linear bounds of cn beyond a certain constant c, where c depends only on the number of substitutions made at a single step of the induction.

Subject Classification

Keywords
  • circuit complexity
  • lower bounds
  • gate elimination

Metrics

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

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory (TOCT), 1(1):2, 2009. Google Scholar
  2. Kazuyuki Amano and Jun Tarui. A well-mixed function with circuit complexity 5n± o(n): Tightness of the Lachish-Raz-type bounds. In Proceedings of Theory and Applications of Models of Computation, volume 4978 of Lecture Notes in Computer Science, pages 342-350. Springer, 2008. Google Scholar
  3. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the 𝒫 = ?NP question. SIAM Journal on computing, 4(4):431-442, 1975. Google Scholar
  4. Eli Ben-Sasson and Swastik Kopparty. Affine dispersers from subspace polynomials. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 65-74, 2009. Google Scholar
  5. Norbert Blum. A boolean function requiring 3n network size. Theor. Comput. Sci., 28:337-345, 1984. Google Scholar
  6. Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, and Grigory Yaroslavtsev. New upper bounds on the Boolean circuit complexity of symmetric functions. Information Processing Letters, 110(7):264-267, 2010. Google Scholar
  7. Evgeny Demenkov and Alexander S. Kulikov. An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers. In Proceedings of International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 256-265, 2011. Google Scholar
  8. Evgeny Demenkov and Alexander S. Kulikov. Computing All MOD-Functions Simultaneously. Computer Science – Theory and Applications, pages 81-88, 2012. Google Scholar
  9. Irit Dinur and Or Meir. Toward the krw composition conjecture: Cubic formula lower bounds via communication complexity. In LIPIcs-Leibniz International Proceedings in Informatics, volume 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  10. Paul E. Dunne. Techniques for the analysis of monotone Boolean networks. PhD thesis, University of Warwick, 1984. Google Scholar
  11. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. Electronic Colloquium on Computational Complexity (ECCC), 22:166, 2015. Google Scholar
  12. Lance Fortnow. The role of relativization in complexity theory. Bulletin of the EATCS, pages 1-15, 1994. Google Scholar
  13. Alexander Golovnev and Alexander S. Kulikov. Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds. In Innovations in Theoretical Computer Science, ITCS '16, pages 405-411, 2016. Google Scholar
  14. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 6-20. ACM, 1986. Google Scholar
  15. Johan Håstad. The shrinkage exponent is 2. In Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on, pages 114-123. IEEE, 1993. Google Scholar
  16. Pavel Hrubeš, Stasys Jukna, Alexander Kulikov, and Pavel Pudlak. On convex complexity measures. Theoretical Computer Science, 411(16):1842-1854, 2010. Google Scholar
  17. Kazuo Iwama and Hiroki Morizumi. An Explicit Lower Bound of 5n-o(n) for Boolean Circuits. In Proceedings of International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 2420 of Lecture Notes in Computer Science, pages 353-364. Springer, 2002. Google Scholar
  18. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science & Business Media, 2012. Google Scholar
  19. Valeriy M. Khrapchenko. Method of determining lower bounds for the complexity of P-schemes. Mathematical Notes, 10(1):474-479, 1971. Google Scholar
  20. Richard J. Lipton. The 𝒫 = NP Question and Gödel’s Lost Letter. Springer Science & Business Media, 2010. Google Scholar
  21. Edward I. Nechiporuk. On a Boolean function. Doklady Akademii Nauk. SSSR, 169(4):765-766, 1966. Google Scholar
  22. Ilan Newman and Avi Wigderson. Lower bounds on formula size of boolean functions using hypergraph entropy. SIAM Journal on Discrete Mathematics, 8(4):536-542, 1995. Google Scholar
  23. Roshal G. Nigmatullin. Are lower bounds on the complexity lower bounds for universal circuits? In Fundamentals of Computation Theory, pages 331-340. Springer, 1985. Google Scholar
  24. Roshal G. Nigmatullin. Complexity lower bounds and complexity of universal circuits. Kazan University, 1990. Google Scholar
  25. Wolfgang J. Paul. A 2.5n-lower bound on the combinational complexity of boolean functions. SIAM J. Comput., 6(3):427-443, 1977. Google Scholar
  26. Alexander A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81-93, 1990. Google Scholar
  27. Alexander A. Razborov. On submodular complexity measures. In Poceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 76-83, New York, NY, USA, 1992. Cambridge University Press. Google Scholar
  28. Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  29. Claus-Peter Schnorr. Zwei lineare untere schranken für die komplexität boolescher funktionen. Computing, 13(2):155-171, 1974. Google Scholar
  30. Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28:59-98, 1949. Google Scholar
  31. Larry J. Stockmeyer. On the combinational complexity of certain symmetric boolean functions. Mathematical Systems Theory, 10:323-336, 1977. Google Scholar
  32. Avishay Tal. Shrinkage of De Morgan formulae by spectral techniques. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 551-560. IEEE, 2014. Google Scholar
  33. Salil Vadhan and Ryan Williams. Personal communication, 2013. Google Scholar
  34. Leslie G. Valiant. Universal circuits (preliminary report). In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 196-203. ACM, 1976. Google Scholar
  35. Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987. 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 About DROPS Imprint Privacy Contact