The DOI matches its Crossref record.
Universal circuits (Preliminary Report)
Open accessAbstract
We show that there is a combinational (acyclic) Boolean circuit of complexity 0(slog s), that can be made to compute any Boolean function of complexity s by setting its specially designated set of control inputs to appropriate fixed values. We investigate the construction of such “universal circuits” further so as to exhibit directions in which refinements of the asymptotic multiplicative constant factor in the complexity bound can be found. In this pursuit useful detailed guidance is provided by available lower bound arguments. In the final section we discuss some other problems in computational complexity that can be related directly to the graph-theoretic ideas behind our constructions. For motivation we start by illustrating some of the applications of universal circuits themselves.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Improved Garbled Circuit: Free XOR Gates and Applications
Kolesnikov, V., & Schneider, T. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70583-3_40 · Cited by 743
Foundations of garbled circuits
Bellare, M., Hoang, V. T., & Rogaway, P. (2012) · Proceedings of the 2012 ACM conference on Computer and communications security · doi:10.1145/2382196.2382279 · Cited by 541
Universality considerations in VLSI circuits
Valiant, L. G. (1981) · IEEE Transactions on Computers · doi:10.1109/tc.1981.6312176 · Cited by 396
Self-citationTASTY: tool for automating secure two-party computations
Henecka, W., K ögl, S., Sadeghi, A.-R., Schneider, T., & Wehrenberg, I. (2010) · Proceedings of the 17th ACM conference on Computer and communications security · doi:10.1145/1866307.1866358 · Cited by 356
Graph-theoretic arguments in low-level complexity
Valiant, L. G. (1977) · Lecture Notes in Computer Science · doi:10.1007/3-540-08353-7_135 · Cited by 312
Self-citation
Metadata
- Authors
- Valiant, L. G.
- Venue
- Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76
- Publisher
- ACM Press
- Published
- 1976
- Pages
- 196-203
- OpenAlex
- W2002616520
- Cited by
- 170
- References
- 0
- FWCI
- 0.54
- Type
- conference paper
- Language
- en
- Open access
- bronze
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Universal circuits (Preliminary Report). https://app.cochat.ai/papers/10.1145/800113.803649
- The paper
- Valiant, L. G. (1976). Universal circuits (Preliminary Report). Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76. https://doi.org/10.1145/800113.803649
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.