Document Open Access Logo

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

Authors Pavel Hrubeš, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.72.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Pavel Hrubeš
  • Institute of Mathematics of ASCR, Prague
Sivaramakrishnan Natarajan Ramamoorthy
  • Paul G. Allen School of Computer Science & Engineering, University of Washington, USA
Anup Rao
  • Paul G. Allen School of Computer Science & Engineering, University of Washington, USA
Amir Yehudayoff
  • Department of Mathematics, Technion-IIT, Haifa, Israel

Funding

This work was done while the authors were visiting the Simons Institute for the Theory of Computing.
  • Hrubeš, Pavel: Supported by ERC grant FEALORA 339691 and the GACR grant 19-27871X.
  • Natarajan Ramamoorthy, Sivaramakrishnan: Supported by the National Science Foundation under agreement CCF- 1420268.
  • Rao, Anup: Supported by the National Science Foundation under agreement CCF- 1420268.
  • Yehudayoff, Amir: Partially supported by ISF grant 1162/15.

Cite As Get BibTex

Pavel Hrubeš, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, and Amir Yehudayoff. Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 72:1-72:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.72

Abstract

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets S_1,...,S_k subset [n] is balancing if for every subset X subset {1,2,...,n} of size n/2, there is an i in [k] so that |S_i cap X| = |S_i|/2. We extend and simplify the framework developed by Hegedűs for proving lower bounds on the size of balancing set families. We prove that if n=2p for a prime p, then k >= p. For arbitrary values of n, we show that k >= n/2 - o(n).
We then exploit the connection between balancing families and depth-2 threshold circuits. This connection helps resolve a question raised by Kulikov and Podolskii on the fan-in of depth-2 majority circuits computing the majority function on n bits. We show that any depth-2 threshold circuit that computes the majority on n bits has at least one gate with fan-in at least n/2 - o(n). We also prove a sharp lower bound on the fan-in of depth-2 threshold circuits computing a specific weighted threshold function.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Theory of computation → Circuit complexity
Keywords
  • Balancing sets
  • depth-2 threshold circuits
  • polynomials
  • majority
  • weighted thresholds

Metrics

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

Related Versions

References

  1. M. Ajtai, J. Komlós, and E. Szemerédi. Sorting in c logn parallel steps. Combinatorica, 3(1):1-19, March 1983. URL: http://dx.doi.org/10.1007/BF02579338.
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. Journal of the ACM, 57(3):1-36, March 2010. URL: http://dx.doi.org/10.1145/1706591.1706594.
  3. Noga Alon. Personal Communication, 2019. Google Scholar
  4. Noga Alon, Ernest E. Bergmann, Don Coppersmith, and Andrew M. Odlyzko. Balancing sets of vectors. IEEE Transactions on Information Theory, 34(1):128-130, 1988. Google Scholar
  5. Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. arXiv, 2017. URL: http://arxiv.org/abs/1708.02037.
  6. Kazuyuki Amano. Depth Two Majority Circuits for Majority and List Expanders. In Igor Potapov, Paul Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117, pages 81:1-81:13, 2018. URL: http://drops.dagstuhl.de/opus/volltexte/2018/9663.
  7. Kazuyuki Amano and Masafumi Yoshida. Depth Two (n-2)-Majority Circuits for n-Majority. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101.A(9):1543-1545, 2018. Google Scholar
  8. Roger C. Baker, Glyn Harman, and János Pintz. The difference between consecutive primes, II. Proceedings of the London Mathematical Society, 83(3):532-562, 2001. Google Scholar
  9. Christian Engels, Mohit Garg, Kazuhisa Makino, and Anup Rao. On expressing majority as a majority of majorities. In Electronic Colloquium on Computational Complexity (ECCC), volume 24, page 174, 2017. Google Scholar
  10. Hikoe Enomoto, Peter Frankl, Noboru Ito, and Kazumasa Nomura. Codes with given distances. Graphs and Combinatorics, 3(1):25-38, 1987. Google Scholar
  11. David Eppstein and Daniel S. Hirschberg. From discrepancy to majority. Algorithmica, 80(4):1278-1297, 2018. Google Scholar
  12. Peter Frankl and Vojtěch Rödl. Forbidden intersections. Transactions of the American Mathematical Society, 300(1):259-286, 1987. Google Scholar
  13. Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii. Exact threshold circuits. In 2010 25th Annual IEEE Conference on Computational Complexity, pages 270-279. IEEE, 2010. Google Scholar
  14. Johan Håstad, Guillaume Lagarde, and Joseph Swernofsky. d-Galvin families. arXiv, January 2019. URL: http://arxiv.org/abs/1901.02652.
  15. Gábor Hegedűs. Balancing sets of vectors. Studia Scientiarum Mathematicarum Hungarica, 47(3):333-349, 2009. Google Scholar
  16. Maurice J. Jansen. Lower bounds for syntactically multilinear algebraic branching programs. In International Symposium on Mathematical Foundations of Computer Science, pages 407-418, 2008. Google Scholar
  17. Alexander S. Kulikov and Vladimir V. Podolskii. Computing majority by constant depth majority circuits with low fan-in gates. arXiv, 2016. URL: http://arxiv.org/abs/1610.02686.
  18. L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319-324, 1978. Google Scholar
  19. Gleb Posobin. Computing majority with low-fan-in majority queries. arXiv, 2017. URL: http://arxiv.org/abs/1711.10176.
  20. Ran Raz, Amir Shpilka, and Amir Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM Journal on Computing, 38(4):1624-1647, 2008. Google Scholar
  21. Srikanth Srinivasan. Personal Communication, 2018. Google Scholar
  22. L.G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms, 5(3):363-366, 1984. URL: http://dx.doi.org/10.1016/0196-6774(84)90016-6.
  23. R. Ryan Williams. Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. arXiv, 2018. URL: http://arxiv.org/abs/1802.09121.
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