CoChat
Sign Up
Cited by 237Complexity and Algorithms in GraphsAdvanced Graph Theory ResearchComputability, Logic, AI Algorithms

The DOI matches its Crossref record.

Threshold circuits of bounded depth

Open access
Hajnal, András, Maass, Wolfgang, Pudlák, Pavel, Szegedy, Márió, Turán, György·1993·Journal of Computer and System Sciences
DOI 10.1016/0022-0000(93)90001-d
Open this paper in CoChat — free account

Overview

Integrity signals

Registry

Crossref · 10.1016/0022-0000(93)90001-d

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 18

  1. Ajtai, 1984, Σ11 formulae on finite structures, Ann. Pure Appl. Logic, 24, 1, 10.1016/0168-0072(83)90038-6 · DOI
  2. Beame, 1986, Log depth circuits for division and related problems, SIAM J. Comput., 15, 994, 10.1137/0215070 · DOI
  3. Chandra, 1984, Constant depth reducibility, SIAM J. Comput., 13, 423, 10.1137/0213028 · DOI
  4. Dobrushin, 1977, Upper bound for the redundancy of self-correcting arrangements of unreliable functional elements, Problems Inform. Transmission, 13, 59
  5. Fagin, 1985, Bounded depth, polynomial size circuits for symmetric functions, Theoret. Comput. Sci., 36, 239, 10.1016/0304-3975(85)90045-3 · DOI
  6. Gurevich, 1984, A logic for constant depth circuits, Inform. and Control, 61, 65, 10.1016/S0019-9958(84)80062-5 · DOI
  7. Lupanov, 1961, Implementing the algebra of logic functions in terms of bounded depth formulas in the basis +, ∗, −, Dokl. Acad. Nauk. SSSR, 136, 5
  8. Lupanov, 1961, Implementing the algebra of logic functions in terms of bounded depth formulas in the basis +, ∗, -, Dokl. Acad. Nauk. SSSR, 136, 1041
  9. 1961, Sov. Phys. Dokl., 6, 107
  10. McColl, 1977, The depth of all Boolean functions, SIAM J. Comput., 6, 373, 10.1137/0206026 · DOI
  11. Parberry, 1986, Parallel computation with threshold functions, Vol. 223, 272
  12. Razborov, 1985, Lower bounds for the monotone complexity of some Boolean functions, Dokl. Akad. Nauk., 281, 798
  13. Razborov, 1987, Lower bounds for the size of circuits of bounded depth with basis { ∨, ⊕ }, Mat. Zametki, 41, 598
  14. Rumelhardt, 1986, Vol. 1
  15. Simon, 1983, A tight Ω(log log n) bound on the time for parallel RAM's to compute nondegenerate Boolean functions, Vol. 158, 151
  16. Skyum, 1983, A measure in which Boolean negation is exponentially powerful, Inform. Process. Lett., 17, 125, 10.1016/0020-0190(83)90051-0 · DOI
  17. Skyum, 1985, A complexity theory based on Boolean algebra, J. Assoc. Comput. Mach., 32, 484, 10.1145/3149.3158 · DOI
  18. Turán, 1984, The critical complexity of graph properties, Inform. Process. Lett., 18, 151, 10.1016/0020-0190(84)90019-X · DOI

Cited by

Sorted by citations

Metadata

Authors
Hajnal, A., Maass, W., Pudlák, P., Szegedy, M., & Turán, G.
Affiliations
  • HUN-REN Alfréd Rényi Institute of Mathematics (HU)
  • University of Illinois Chicago (US)
  • Czech Academy of Sciences (CZ)
  • University of Chicago (US)
ORCID
Venue
Journal of Computer and System Sciences
Publisher
Elsevier BV
Published
1993-04
Volume
46
Issue
2
Pages
129-154
ISSN
0022-0000 (ISSN-L)
DOI
10.1016/0022-0000(93)90001-d
OpenAlex
W2080210666
Cited by
237
References
0
Citations by year
2026: 3 · 2025: 3 · 2024: 6 · 2023: 6 · 2022: 6 · 2021: 9 · 2020: 7 · 2019: 8 · 2018: 8 · 2017: 9 · 2016: 8 · 2015: 7 · 2014: 10 · 2013: 6 · 2012: 4
FWCI
8.66
Type
journal article
Language
en
Open access
Licence
Locations
  • Journal of Computer and System Sciences (publishedVersion)
  • Journal of Computer and System Sciences
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
Keywords
threshold circuits, bounded-depth circuits, polynomial-size circuits, parallel computing, circuit lower bounds, probabilistic circuits, threshold gates, graph connectivity, definability

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review