Document Open Access Logo

Lower Bounds for (Non-Monotone) Comparator Circuits

Authors Anna Gál, Robert Robere

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.58.pdf
  • Filesize: 467 kB
  • 13 pages

Document Identifiers

Author Details

Anna Gál
  • University of Texas at Austin, Austin TX, United States of America
Robert Robere
  • Institute for Advanced Study, Princeton NJ, United States of America

Funding

  • Robere, Robert: Funding provided by an NSERC Postdoctoral Fellowship and the Charles Simonyi Endowment.

Acknowledgements

Some of this work was done while the authors were visiting the Simons Institute for the Theory of Computing in Berkeley, and while R.R. was at DIMACS.

Cite AsGet BibTex

Anna Gál and Robert Robere. Lower Bounds for (Non-Monotone) Comparator Circuits. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.58

Abstract

Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and Boolean formulas. In this paper we prove the first superlinear lower bounds in the general (non-monotone) version of this model for an explicitly defined function. More precisely, we prove that the n-bit Element Distinctness function requires Ω((n/ log n)^(3/2)) size comparator circuits.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • comparator circuits
  • circuit complexity
  • Nechiporuk
  • lower bounds

Metrics

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

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. An O(n log n) Sorting Network. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 1-9, 1983. URL: https://doi.org/10.1145/800061.808726.
  2. Kenneth E. Batcher. Sorting Networks and Their Applications. In American Federation of Information Processing Societies: AFIPS Conference Proceedings: 1968 Spring Joint Computer Conference, Atlantic City, NJ, USA, 30 April - 2 May 1968, pages 307-314, 1968. URL: https://doi.org/10.1145/1468075.1468121.
  3. Amos Beimel, Anna Gál, and Mike Paterson. Lower Bounds for Monotone Span Programs. Computational Complexity, 6(1):29-45, 1997. URL: https://doi.org/10.1007/BF01202040.
  4. Andrej Bogdanov. Small Bias Requires Large Formulas. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 22:1-22:12, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.22.
  5. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman. Mining Circuit Lower Bound Proofs for Meta-Algorithms. Computational Complexity, 24(2):333-392, 2015. URL: https://doi.org/10.1007/s00037-015-0100-0.
  6. Stephen A. Cook, Yuval Filmus, and Dai Tri Man Le. The complexity of the comparator circuit value problem. TOCT, 6(4):15:1-15:44, 2014. URL: https://doi.org/10.1145/2635822.
  7. Irit Dinur and Or Meir. Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Computational Complexity, 27(3):375-462, 2018. URL: https://doi.org/10.1007/s00037-017-0159-x.
  8. Anna Gál, Avishay Tal, and Adrian Trejo Nuñez. Cubic Formula Size Lower Bounds Based on Compositions with Majority. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 35:1-35:13, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.35.
  9. Michael T. Goodrich. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 684-693, 2014. URL: https://doi.org/10.1145/2591796.2591830.
  10. RL Graham. A mathematical study of a model of magnetic domain interactions. Bell System Technical Journal, 49(8):1627-1644, 1970. Google Scholar
  11. Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20, 1986. URL: https://doi.org/10.1145/12130.12132.
  12. Johan Håstad. The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. URL: https://doi.org/10.1137/S0097539794261556.
  13. Kazuo Iwama and Hiroki Morizumi. An Explicit Lower Bound of 5n - o(n) for Boolean Circuits. In Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings, pages 353-364, 2002. URL: https://doi.org/10.1007/3-540-45687-2_29.
  14. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  15. Mauricio Karchmer and Avi Wigderson. On Span Programs. In Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, pages 102-111, 1993. URL: https://doi.org/10.1109/SCT.1993.336536.
  16. Valeriy M Khrapchenko. Method of determining lower bounds for the complexity of P-schemes. Mathematical Notes, 10(1):474-479, 1971. Google Scholar
  17. Donald Ervin Knuth. The art of computer programming, , Volume III, 2nd Edition. Addison-Wesley, 1998. URL: http://www.worldcat.org/oclc/312994415.
  18. Ilan Komargodski and Ran Raz. Average-case lower bounds for formula size. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 171-180, 2013. URL: https://doi.org/10.1145/2488608.2488630.
  19. Ilan Komargodski, Ran Raz, and Avishay Tal. Improved Average-Case Lower Bounds for DeMorgan Formula Size. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 588-597, 2013. URL: https://doi.org/10.1109/FOCS.2013.69.
  20. Ernst W. Mayr and Ashok Subramanian. The Complexity of Circuit Value and Network Stability. J. Comput. Syst. Sci., 44(2):302-323, 1992. URL: https://doi.org/10.1016/0022-0000(92)90024-D.
  21. Edward I Nechiporuk. A Boolean function. Engl. transl. in Sov. Phys. Dokl., 10:591-593, 1966. Google Scholar
  22. Alexander A Razborov. Lower bounds for the monotone complexity of some Boolean functions. In Soviet Math. Dokl., volume 31, pages 354-357, 1985. Google Scholar
  23. Robert Robere. Notes on Comparator Circuits. Unpublished manuscript, 2014. Google Scholar
  24. Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential Lower Bounds for Monotone Span Programs. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 406-415, 2016. URL: https://doi.org/10.1109/FOCS.2016.51.
  25. Ashok Subramanian. The computational complexity of the circuit value and network stability problems. PhD thesis, Stanford University, 1990. Google Scholar
  26. Avishay Tal. Shrinkage of De Morgan Formulae by Spectral Techniques. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 551-560, 2014. URL: https://doi.org/10.1109/FOCS.2014.65.
  27. Avishay Tal. Formula lower bounds via the quantum method. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1256-1268, 2017. URL: https://doi.org/10.1145/3055399.3055472.
  28. Dietmar Uhlig. Boolean functions with a large number of subfunctions and small complexity and depth. In International Symposium on Fundamentals of Computation Theory, pages 395-404. Springer, 1991. Google Scholar
  29. Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/.
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