Article

Free access

Almost optimal lower bounds for small depth circuits

Author:

J HastadAuthors Info & Claims

STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing

Pages 6 - 20

https://doi.org/10.1145/12130.12132

Published: 01 November 1986 Publication History

PDF eReader

References

[1]

Ajtai M. "Z~-Formulae on Finite Structures", Annals of Pure and Applied Logic 24(1983) 1-48

Crossref

Google Scholar

[2]

Alon N. and Boppana R. "The Monotone Circuit Complexity of Boolean Functions", Submitted to Combinatoriea.

Digital Library

Google Scholar

[3]

Andreev A.E. "On one method of obtaining lower bounds of individual monotone function complexity" Dokl. Ak. Nauk. 282 (1085)) pp 1033-1037.

Google Scholar

[4]

Boppana R. "Threshold Functions and Bounded Depth Monotone Circuits" Proceedings of I6th Annual ACM Symposium on Theory of Computing, 1984, 475-479. To appear in Journal of Computer and System Sciences, 1986.

Digital Library

Google Scholar

[5]

Cai J. "With l)robal)ility One, a Random Oracle Separates I'SI)ACE J'rom tile l)olynomial - Time llierarchy" These proceedings.

Digital Library

Google Scholar

[6]

Furst M., Saxe J. and Sipser M., Circuits, and the Polynomial Time Hierarchy", Proceedings of 22nd Annual IEEE Symposium Foundations of Computer Science, 1981, {KPPY} Klawe M.,Paul W, Pippenger Yannakakis M. "On Monotone Formulae Restricted Depth" Proceedings of 16th ACM Symposium on Theory of Computing, 480-487.

Digital Library

Google Scholar

[7]

Razborov A.A. "Lower Bounds Monotone Complexity of some Boolean tions" Dokl. Ak. Nauk. 281 (1985), pp iS} Sipser M. "Borel Sets and Circuit Complexity", Proceeding8 of 15th Annual ACM Symposium Theory of Computing, 1983, 61-69.

Digital Library

Google Scholar

[8]

Valiant L. "Exponential Lower Bounds Restricted Monotone Circuits" Proceedings Annual ACM Symposium on Theory of ing, 1983, 110-117.

Digital Library

Google Scholar

[9]

Yao A. "Separating the Polynomial-Hierarchy by Oracles" Proceedings 26th IEEE Symposium on Foundations of Science, 1985, 1-10.

Digital Library

Google Scholar

Cited By

View all

Gamarnik DJagannath AWein A(2024)Circuit Lower Bounds for the p-Spin Optimization ProblemMarkov Processes And Related Fields10.61102/1024-2953-mprf.2024.30.1.003(81-96)Online publication date: 27-May-2024
https://doi.org/10.61102/1024-2953-mprf.2024.30.1.003
Shen YZhao X(2024)Computationally Hard Problems for Logic Programs under Answer Set SemanticsACM Transactions on Computational Logic10.1145/367696425:4(1-26)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3676964
Rossman BMohar BShinkar IO'Donnell R(2024)Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix MultiplicationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649628(1386-1395)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649628
Show More Cited By

Index Terms

Almost optimal lower bounds for small depth circuits

Recommendations

Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates

We prove superlinear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth ...
Lower bounds for depth three arithmetic circuits with small bottom fanin
CCC '15: Proceedings of the 30th Conference on Computational Complexity

Shpilka and Wigderson [22] had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field F of characteristic zero. We resolve this problem by proving a [EQUATION] ...
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

We prove super-linear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing

November 1986

461 pages

ISBN:0897911938

DOI:10.1145/12130

Chairman:
Juris Hartmanis

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC86

Sponsor:

SIGACT

STOC86: Eighteenth Annaul ACM Symposium on Theory of Computing

May 28 - 30, 1986

California, Berkeley, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

319
Total Citations
View Citations
1,422
Total Downloads

Downloads (Last 12 months)212
Downloads (Last 6 weeks)42

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gamarnik DJagannath AWein A(2024)Circuit Lower Bounds for the p-Spin Optimization ProblemMarkov Processes And Related Fields10.61102/1024-2953-mprf.2024.30.1.003(81-96)Online publication date: 27-May-2024
https://doi.org/10.61102/1024-2953-mprf.2024.30.1.003
Shen YZhao X(2024)Computationally Hard Problems for Logic Programs under Answer Set SemanticsACM Transactions on Computational Logic10.1145/367696425:4(1-26)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3676964
Rossman BMohar BShinkar IO'Donnell R(2024)Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix MultiplicationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649628(1386-1395)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649628
Kilic KSima JBruck J(2024)Nearest Neighbor Representations of Neural Circuits2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619486(3077-3082)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619486
De ANadimpalli SServedio R(2024)Gaussian Approximation of Convex Sets by Intersections of Halfspaces*2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00115(1911-1930)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00115
Sacchi NVacchini EIncremona GFerrara A(2024)On neural networks application in integral sliding mode controlJournal of the Franklin Institute10.1016/j.jfranklin.2024.106989361:13(106989)Online publication date: Sep-2024
https://doi.org/10.1016/j.jfranklin.2024.106989
Emdin GKulikov AMihajlin ISlezkin N(2024)CNF Encodings of Symmetric FunctionsTheory of Computing Systems10.1007/s00224-024-10168-w68:5(1291-1311)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00224-024-10168-w
Filmus YIshai YKaplan AKindler G(2024)Limits of PreprocessingComputational Complexity10.1007/s00037-024-00251-633:1Online publication date: 23-May-2024
https://dl.acm.org/doi/10.1007/s00037-024-00251-6
Santhanam R(2023)An Algorithmic Approach to Uniform Lower BoundsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.35(1-26)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.35
Cavalar BOliveira I(2023)Constant-Depth Circuits vs. Monotone CircuitsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.29(1-37)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.29
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates

Lower bounds for depth three arithmetic circuits with small bottom fanin

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates