More Web Proxy on the site http://driver.im/

Article

Free access

Exponential lower bounds for restricted monotone circuits

Author:

L. G. ValiantAuthors Info & Claims

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

Pages 110 - 117

https://doi.org/10.1145/800061.808739

Published: 01 December 1983 Publication History

Abstract

In this paper we consider monotone Boolean circuits with three alternations, in the order “or”, “and”, “or.” Whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. We shall therefore refer to this measure interchangeably as ΣπΣ-formula size or ΣπΣ-circuit size. We shall prove that any such circuit or formula for detecting the existence of cliques in an N-node graph has at least 2^{Ω(N^ε)} gates for some ε > 0 independent of N.

References

[1]

S. Berkowitz. Personal communication. (1982)

[2]

M. Furst, J.B. Saxe, and M. Sipser. Parity, circuits and the polynomial time hierarchy. Proc. 22nd IEEE Symp. on Foundations of Computer Science (1981) 260-270.

[3]

M.R. Jerrum and M. Snir. Some exact complexity results for straight-line computations over semirings. JACM 29 (1982) 874-898.

Digital Library

[4]

E.A. Lamagna and J.E. Savage. Combinatorial complexity of some monotone functions. Proc. 15th IEEE Symposium on Switching and Automata Theory (1974) 140-144.

[5]

K. Mehlhorn and Z. Galil. Monotone switching circuits and Boolean matrix product. Computing 16 (1976) 99-111.

[6]

M.S. Paterson. Complexity of monotone networks for Boolean matrix product. Theor. Comp. Sci. 1 (1975) 13-20.

[7]

V.R. Pratt. The power of negative thinking in multiplying Boolean matrices. SIAM J. Computing 4 (1975) 326-330.

Digital Library

[8]

J.E. Savage. The Complexity of Computing. Wiley, New York (1976).

Digital Library

[9]

C.P. Schnorr. A lower bound on the number of additions in monotone computations. TCS 2 (1976) 305-315.

[10]

E. Shamir and M. Snir. Lower bounds on the number of multiplications and the number of additions in monotone computations. Tech. Rep. RC6757, T.J. Watson Research Center, IBM (1977).

[11]

S. Skyum and L.G. Valiant. A complexity theory based on Boolean algebra, Proc. 22nd IEEE Symp. on Foundations of Computer Science (1981) 244-254.

[12]

L.G. Valiant. Negation can be exponentially powerful. TCS 12 (1980) 303-314.

[13]

L.G. Valiant. Completeness classes in algebra. Proc. 11th ACM STOC (1979) 249-261.

Digital Library

[14]

L.G. Valiant. Graph-theoretic arguments in low-level complexity. Lecture Notes in Computer Science, Springer Verlag, Vol 53 (1977) 162-176.

[15]

I. Wegner. Boolean functions whose monotone complexity is of size n2/log n. TCS 21 (1982) 213-224.

Cited By

Lecomte VRamakrishnan PTan L(2022)The composition complexity of majorityProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.19(1-26)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.19
Goldreich O(2022)Improved bounds on the AN-complexity of -linear functionsComputational Complexity10.1007/s00037-022-00224-731:2Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00037-022-00224-7
Goldreich OWigderson A(2020)On the Size of Depth-Three Boolean Circuits for Computing Multilinear FunctionsComputational Complexity and Property Testing10.1007/978-3-030-43662-9_6(41-86)Online publication date: 4-Apr-2020
https://doi.org/10.1007/978-3-030-43662-9_6
Show More Cited By

Recommendations

Lower Bounds for Monotone q-Multilinear Boolean Circuits
SOFSEM 2023: Theory and Practice of Computer Science
Abstract
A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is multilinear if for any AND gate the two input functions have no variable in common. We consider a ... $_{}$ $_{}$ $^{}$ $_{}$ $_{}$ $_{}$ $_{}$
Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata
Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures - Volume 5504

The nonemptiness problem for nondeterministic automata on infinite words can be reduced to a sequence of reachability queries. The length of a shortest witness to the nonemptiness is then polynomial in the automaton. Nonemptiness algorithms for ...
Tight Lower Bounds on the Size of Sweeping Automata

A sweeping automaton is a two-way deterministic finite automaton which makes turns only at the endmarkers. We say that a sweeping automaton is degenerate if the automaton has no left-moving transitions. We show that for each positive integer n, there is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

December 1983

487 pages

ISBN:0897910990

DOI:10.1145/800061

Copyright © 1983 ACM.

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 December 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

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

35
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lecomte VRamakrishnan PTan L(2022)The composition complexity of majorityProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.19(1-26)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.19
Goldreich O(2022)Improved bounds on the AN-complexity of -linear functionsComputational Complexity10.1007/s00037-022-00224-731:2Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00037-022-00224-7
Goldreich OWigderson A(2020)On the Size of Depth-Three Boolean Circuits for Computing Multilinear FunctionsComputational Complexity and Property Testing10.1007/978-3-030-43662-9_6(41-86)Online publication date: 4-Apr-2020
https://doi.org/10.1007/978-3-030-43662-9_6
Goldreich OTal A(2020)On Constant-Depth Canonical Boolean Circuits for Computing Multilinear FunctionsComputational Complexity and Property Testing10.1007/978-3-030-43662-9_17(306-325)Online publication date: 4-Apr-2020
https://doi.org/10.1007/978-3-030-43662-9_17
Ball MDachman-Soled DGuo SMalkin TTan L(2018)Non-Malleable Codes for Small-Depth Circuits2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00083(826-837)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00083
Kulikov A(2018)Lower Bounds for Unrestricted Boolean Circuits: Open ProblemsComputer Science – Theory and Applications10.1007/978-3-319-90530-3_2(15-22)Online publication date: 25-Apr-2018
https://doi.org/10.1007/978-3-319-90530-3_2
van Breugel F(2017)Probabilistic bisimilarity distancesACM SIGLOG News10.1145/3157831.31578374:4(33-51)Online publication date: 3-Nov-2017
https://dl.acm.org/doi/10.1145/3157831.3157837
Bertrand NGenest BGimbert H(2017)Qualitative Determinacy and Decidability of Stochastic Games with SignalsJournal of the ACM10.1145/310792664:5(1-48)Online publication date: 15-Sep-2017
https://dl.acm.org/doi/10.1145/3107926
Ameloot TGeck GKetsman BNeven FSchwentick T(2017)Parallel-Correctness and Transferability for Conjunctive QueriesJournal of the ACM10.1145/310641264:5(1-38)Online publication date: 4-Sep-2017
https://dl.acm.org/doi/10.1145/3106412
Ambainis ABalodis KBelovs ALee TSantha MSmotrovs J(2017)Separations in Query Complexity Based on Pointer FunctionsJournal of the ACM10.1145/310623464:5(1-24)Online publication date: 4-Sep-2017
https://dl.acm.org/doi/10.1145/3106234
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents