Document Open Access Logo

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

Authors Alexander S. Kulikov, Vladimir V. Podolskii

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.49.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Alexander S. Kulikov
Vladimir V. Podolskii

Cite As Get BibTex

Alexander S. Kulikov and Vladimir V. Podolskii. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.49

Abstract

We study the following computational problem: for which values of k, the majority of n bits MAJ_n can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJ_k o MAJ_k. We observe that the minimum value of k for which there exists a MAJ_k o MAJ_k circuit that has high correlation with the majority of n bits  is equal to Theta(sqrt(n)). We then show that for a randomized MAJ_k o MAJ_k circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n^(2/3+o(1)). We show a worst case lower bound: if a MAJ_k o MAJ_k circuit computes the majority of n bits correctly on all inputs, then k <= n^(13/19+o(1)). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k= O(n^(2/3)) can compute MAJ_n correctly on all inputs.

Subject Classification

Keywords
  • circuit complexity
  • computational complexity
  • threshold
  • majority
  • lower bound
  • upper bound

Metrics

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

References

  1. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3), 2010. URL: http://dx.doi.org/10.1145/1706591.1706594.
  2. Xi Chen, Igor Carboni Oliveira, and Rocco A. Servedio. Addition is exponentially harder than counting for shallow monotone circuits. Electronic Colloquium on Computational Complexity (ECCC), 22:123, 2015. URL: http://eccc.hpi-web.de/report/2015/123.
  3. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/.
  4. Mikael Goldmann, Johan Håstad, and Alexander A. Razborov. Majority gates VS. general weighted threshold gates. Computational Complexity, 2:277-300, 1992. URL: http://dx.doi.org/10.1007/BF01200426.
  5. Oded Goldreich. Valiant’s polynomial-size monotone formula for majority, 2001. Available at URL: http://www.wisdom.weizmann.ac.il/~oded/PDF/mono-maj.pdf.
  6. Thomas Hofmeister. The power of negative thinking in constructing threshold circuits for addition. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992, pages 20-26, 1992. URL: http://dx.doi.org/10.1109/SCT.1992.215377.
  7. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-24508-4.
  8. Stasys Jukna, Alexander A. Razborov, Petr Savický, and Ingo Wegener. On P versus NP cap co-NP for decision trees and read-once branching programs. Computational Complexity, 8(4):357-370, 1999. URL: http://dx.doi.org/10.1007/s000370050005.
  9. Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput., 36(5):1231-1247, 2007. URL: http://dx.doi.org/10.1137/S0097539705446846.
  10. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 633-643. ACM, 2016. URL: http://dl.acm.org/citation.cfm?id=2897518, URL: http://dx.doi.org/10.1145/2897518.2897636.
  11. Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, and David Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. Random Struct. Algorithms, 48(3):612-638, 2016. URL: http://dx.doi.org/10.1002/rsa.20598.
  12. Marvin Minsky and Seymour Papert. Perceptrons - an introduction to computational geometry. MIT Press, 1987. Google Scholar
  13. Elchanan Mossel and Ryan O'Donnell. On the noise sensitivity of monotone functions. Random Struct. Algorithms, 23(3):333-350, 2003. URL: http://dx.doi.org/10.1002/rsa.10097.
  14. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
  15. Robert Sedgewick and Philippe Flajolet. An introduction to the analysis of algorithms. Addison-Wesley-Longman, 1996. Google Scholar
  16. Kai-Yeung Siu and Jehoshua Bruck. On the power of threshold circuits with small weights. SIAM J. Discrete Math., 4(3):423-435, 1991. URL: http://dx.doi.org/10.1137/0404038.
  17. Leslie G. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5(3):363-366, 1984. URL: http://dx.doi.org/10.1016/0196-6774(84)90016-6.
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