research-article

Monotone Separation of Logarithmic Space from Logarithmic Depth

Authors:

M. Grigni,

M. SipserAuthors Info & Claims

Journal of Computer and System Sciences, Volume 50, Issue 3

Pages 433 - 437

https://doi.org/10.1006/jcss.1995.1033

Published: 01 June 1995 Publication History

Abstract

We show that the monotone analogue of logspace computation is more powerful than monotone log-depth circuits: monotone bounded fanin circuits for a certain function in monotone logspace require depth (lg2n).

References

[1]

M. Ajtai and Y. Gurevich, Monotone versus positive, Assoc. Comput. Mach. 34 (1987), 1004-1015.

Digital Library

Google Scholar

[2]

R. B. Boppana and M. Sipser, The complexity of finite functions, in "Handbook of Theoretical Computer Science," Vol. A, pp. 757-804, Elsevier and MIT Press, Cambridge, MA, 1990.

Crossref

Google Scholar

[3]

M. Grigni, Structure in Monotone Complexity , Ph.D. thesis, Massachusetts Institute of Technology; Technical Report MIT/LCS/TR-520, 1991.

Crossref

Google Scholar

[4]

M. Grigni and M. Sipser, Monotone complexity, in "Boolean Function Complexity: Selected Papers from the London Math. Soc. Durham Symp., 1990," LMS Lecture Notes, Cambridge Univ. Press, Cambridge, 1992, pp. 57-75.

Crossref

Google Scholar

[5]

N. Immerman, Languages that capture complexity classes, SIAM J. Comput. 16 (1987), 760-778.

Digital Library

Google Scholar

[6]

N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput. 17 (1988), 935-938.

Digital Library

Google Scholar

[7]

M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math. 3 (1990), 255-265; in "Proceedings, 20th Annual ACM Symp. on Theory of Computing, 1988," pp. 539-550.

Crossref

Google Scholar

[8]

R. Raz and A. Wigderson, Probabilistic communication complexity of boolean relations, in "Proceedings, 30th Annual IEEE Symp. on Foundations of Computer Science, 1989," pp. 562-573.

Digital Library

Google Scholar

[9]

R. Raz and A. Wigderson, Monotone circuits for matching require linear depth, in "Proceedings, 22nd Annual ACM Symp. on Theory of Computing, 1990," pp. 287-292.

Digital Library

Google Scholar

[10]

A. A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Dokl. Akad. Nauk SSSR 281 (1985), 798-801; Engl. transl., Soviet Math. Dokl. 31 (1985), 354-357.

Google Scholar

[11]

A. A. Razborov, A lower bound on the monotone network complexity of the logical permanent, Mat. Zametki 37 (1985), 887-900; Engl, transl., Math. Notes 37 (1985), 485-493.

Google Scholar

[12]

R. Szelepcsenyi, The method of forcing for nondeterministic automata, Bull. European Assoc. Theoret. Comput. Sci. 33 (1987), 96-100.

Google Scholar

[13]

A. Yao, Circuits and local computation, in "Proceedings, 21st Annual ACM Symp. on Theory of Computing, 1989," pp. 186-196.

Crossref

Google Scholar

Cited By

View all

de Rezende SGöös MRobere R(2022)Guest ColumnACM SIGACT News10.1145/3532737.353274653:1(59-82)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1145/3532737.3532746
Cseresnyes ESeiwert H(2022)Regular expression length via arithmetic formula complexityJournal of Computer and System Sciences10.1016/j.jcss.2021.10.004125:C(1-24)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.10.004
Gupta NSaha CThankey BAceto L(2020)A super-quadratic lower bound for depth four arithmetic circuitsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.23(1-31)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.23
Show More Cited By

Index Terms

Monotone Separation of Logarithmic Space from Logarithmic Depth
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Constant-Depth Circuits vs. Monotone Circuits
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity Conference

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

• For every k ≥ 1, there is a monotone function in AC⁰ (constant-depth poly-size circuits) that requires monotone circuits of depth Ω(log^k n). ...
Monotone circuits for connectivity require super-logarithmic depth
STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

We prove that every monotone circuit which tests st-connectivity of an undirected graph on n nodes has depth Ω(log²n). This implies a superpolynomial (n^{Ω(log n)}) lower bound on the size of any monotone formula for st-connectivity.

The proof draws ...
Options for Denormal Representation in Logarithmic Arithmetic
Abstract
Economical hardware often uses a FiXed-point Number System (FXNS), whose constant absolute precision is acceptable for many signal-processing algorithms. The almost-constant relative precision of the more expensive Floating-Point (FP) number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 50, Issue 3

June 1995

251 pages

ISSN:0022-0000

Editors:
E. K. Blum
Univ. of Southern California, Los Angeles
,
Neil Immerman,
Timothy Long,
Ming Li

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 1995

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

de Rezende SGöös MRobere R(2022)Guest ColumnACM SIGACT News10.1145/3532737.353274653:1(59-82)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1145/3532737.3532746
Cseresnyes ESeiwert H(2022)Regular expression length via arithmetic formula complexityJournal of Computer and System Sciences10.1016/j.jcss.2021.10.004125:C(1-24)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.10.004
Gupta NSaha CThankey BAceto L(2020)A super-quadratic lower bound for depth four arithmetic circuitsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.23(1-31)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.23
Podolskii V(2017)Bounds in Ontology-Based Data Access via Circuit ComplexityTheory of Computing Systems10.1007/s00224-016-9707-z61:2(464-493)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00224-016-9707-z
Rossman BZuckerman D(2015)Correlation bounds against monotone NCProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833247(392-411)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833247
Kontchakov RRodríguez-Muro MZakharyaschev M(2013)Ontology-based data access with databasesProceedings of the 9th international conference on Reasoning Web: semantic technologies for intelligent data access10.1007/978-3-642-39784-4_5(194-229)Online publication date: 30-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39784-4_5
Chan SPotechin AKarloff HPitassi T(2012)Tight bounds for monotone switching networks via fourier analysisProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214024(495-504)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214024
Demetrescu CFinocchi IRibichini A(2009)Trading off space for passes in graph streaming problemsACM Transactions on Algorithms10.1145/1644015.16440216:1(1-17)Online publication date: 28-Dec-2009
https://dl.acm.org/doi/10.1145/1644015.1644021
Gruber HJohannsen J(2008)Optimal lower bounds on regular expression size using communication complexityProceedings of the Theory and practice of software, 11th international conference on Foundations of software science and computational structures10.5555/1792803.1792823(273-286)Online publication date: 29-Mar-2008
https://dl.acm.org/doi/10.5555/1792803.1792823
Demetrescu CFinocchi IRibichini A(2006)Trading off space for passes in graph streaming problemsProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm10.5555/1109557.1109635(714-723)Online publication date: 22-Jan-2006
https://dl.acm.org/doi/10.5555/1109557.1109635
Show More Cited By

View Options

View options

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Constant-Depth Circuits vs. Monotone Circuits

Monotone circuits for connectivity require super-logarithmic depth

Options for Denormal Representation in Logarithmic Arithmetic

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations