Document Open Access Logo

Circuits with Medium Fan-In

Authors Pavel Hrubes, Anup Rao

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2015.381.pdf
  • Filesize: 488 kB
  • 11 pages

Document Identifiers

Subject Classification

Keywords
  • Boolean circuit
  • Complexity
  • Communication Complexity

Metrics

Abstract

We consider boolean circuits in which every gate may compute an arbitrary boolean function of k other gates, for a parameter k. We give an explicit function $f:{0,1}^n -> {0,1} that requires at least Omega(log^2(n)) non-input gates when k = 2n/3. When the circuit is restricted to being layered and depth 2, we prove a lower bound of n^(Omega(1)) on the number of non-input gates. When the circuit is a formula with gates of fan-in k, we give a lower bound Omega(n^2/k*log(n)) on the total number of gates. 

Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the Number-On-Forehead model in communication complexity, or for bounded depth circuits in AC_0, or extractors for varieties over small fields would imply strong lower bounds in our model. On the other hand, new lower bounds for our model would prove new time-space tradeoffs for branching programs and impossibility results for (fan-in 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for a known time-space tradeoff for oblivious branching programs.

Cite As Get BibTex

Pavel Hrubes and Anup Rao. Circuits with Medium Fan-In. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 381-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.381

Author Details

Pavel Hrubes
Anup Rao

References

  1. Miklós Ajtai. Determinism versus nondeterminism for linear time RAMs with memory restrictions. Journal of Computer and System Sciences, 65(1):2-37, 2002. Google Scholar
  2. Noga Alon and Wolfgang Maass. Meanders, ramsey theory and lower bounds for branching programs. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, FOCS, pages 410-417, 1986. Google Scholar
  3. László Babai, Noam Nisan, and Mario Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci, 45(2):204-232, 1992. Google Scholar
  4. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. J. Comput. Syst. Sci, 38(1):150-164, 1989. Google Scholar
  5. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM Symposium on Principles of Database Systems, PODS, pages 273-284, 2013. Google Scholar
  6. Paul Beame and Erik Vee. Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, STOC, pages 688-697, 2002. Google Scholar
  7. Allan Borodin, Alexander A. Razborov, and Roman Smolensky. On lower bounds for read-K-times branching programs. Computational Complexity, 3:1-18, 1993. Google Scholar
  8. A. Chandra, M. Furst, and R. Lipton. Multi-party protocols. In Proceedings of the 15th Annual ACM Symposium on Theory of computing, STOC, pages 94-99, 1983. Google Scholar
  9. D. Y. Cherukhin. The lower estimate of complexity in the class of schemes of depth 2 without restrictions on a basis. Moscow University Mathematics Bulletin, 60(4):42-44, 2005. Google Scholar
  10. Pierre Deligne. La conjecture de Weil : I, 1974. Google Scholar
  11. Zeev Dvir. Extractors for varieties. Computational Complexity, 21(4):515-572, 2012. Google Scholar
  12. Oded Goldreich and Avi Wigderson. On the size of depth-three boolean circuits for computing multilinear functions. Electronic Colloquium on Computational Complexity, ECCC, 2013. Google Scholar
  13. Johan Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC, pages 6-20, 1986. Google Scholar
  14. S. Jukna. Extremal combinatorics, with applications in computer science. Springer-Verlag, 2001. Google Scholar
  15. E. I. Nechiporuk. A boolean function. Sov.Math.Dokl., 7(4):999-1000, 1966. Google Scholar
  16. Elizaveta Okolnishnikova. On lower bounds for branching programs. Siberian Advances in Mathematics, 3(1):152-166, 1993. Google Scholar
  17. P. Pudlák, V. Ro\"dl, and J. Sgall. Boolean circuits, tensor ranks, and communication complexity. SIAM J. Comput., 26(3):605-633, 1997. Google Scholar
  18. J. Radhakrishnan and A. Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math. 13(1): 2-24, 13(1):2-24, 200. Google Scholar
  19. Alexander Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. MATHNASUSSR: Mathematical Notes of the Academy of Sciences of the USSR, 41, 1987. Google Scholar
  20. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC, pages 77-82, 1987. Google Scholar
  21. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science, MFCS, volume 53 of Lecture Notes in Computer Science, pages 162-176, 1977. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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