Article

Free access

Circuit minimization problem

Authors:

Valentine Kabanets,

Jin-Yi CaiAuthors Info & Claims

STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing

Pages 73 - 79

https://doi.org/10.1145/335305.335314

Published: 01 May 2000 Publication History

PDF eReader

References

[1]

A. Andreev, A. Clementi, and J. Rolim. A new general derandomization method. Journal of the Association for Computing Machinery, 45(1):179-213, 1998. (preliminary version in ICALP'96).

Digital Library

Google Scholar

[2]

A. Andreev, A. Clementi, J. Rolim, and L. Trevisan. Weak random sources, hitting sets, and BPP simulations. In Proceedings of the Thirty-Eighth Annual IEEE Symposium on Foundations of Computer Science, pages 264-272, 1997.

Digital Library

Google Scholar

[3]

L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EX- PTiME has publishable proofs. Complexity, 3:307-318, 1993.

Digital Library

Google Scholar

[4]

H. Buhrman and L. Fortnow. One-sided versus twosided error in probabilistic computation. In C. Meinel and S. Tison, editors, Proceedings of the Sixteenth Annual Symposium on Theoretical Aspects of Computer Science, volume 1563 of Lecture Notes in Computer Science, pages 100-109. Springer Verlag, 1999.

Digital Library

Google Scholar

[5]

S. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual A CM Symposium on Theory of Computing, pages 151-158, 1971.

Digital Library

Google Scholar

[6]

M. Garey and D. johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.

Digital Library

Google Scholar

[7]

O. Goldreich and A. Wigderson. Improved derandomization of BPP using a. hitting set generator. In D. Hochbaum, K. Jansen, J. Rolim, and A. Sinclair, editors, Randomization, Approximation, and Combinatorial Optimization, volume 1671 of Lecture Notes in Computer Science, pages 131-137. Springer Verlag, 1999. (RANDOM-APPROX'99).

Digital Library

Google Scholar

[8]

O. Goldreich and D. Zuckerman. Another proof that BPPCPH (and more). Electronic Colloquium on Computational Complexity, TR97-045, 1997.

Google Scholar

[9]

R. Impagliazzo, R. Shaltiel, and A. Wigderson. Near-optimal conversion of hardness into pseudorandomness. In Proceedings of the Fortieth Annual IEEE Symposium on Foundations of Computer Science, pages 181-190, 1999.

Digital Library

Google Scholar

[10]

R. Impagliazzo and A. Wigderson. P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-Ninth Annual A CM Symposium on Theory of Computing, pages 220-229, 1997.

Digital Library

Google Scholar

[11]

R. Kannan. Circuit-size lower bounds and nonreducibility to sparse sets. Information and Control, 55'40-56, 1982.

Google Scholar

[12]

J. KSbler and O. Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing, 28(1):311-324, 1998.

Digital Library

Google Scholar

[13]

C. Lautemann. BPP and the polynomial time hierarchy. Information Processing Letters, 17:215-218, 1983.

Crossref

Google Scholar

[14]

H. Lenstra Jr. and C. Pomerance. A rigorous time bound for factoring integers. Journal of the American Mathematical Society, 5(3):483-516, 1992.

Crossref

Google Scholar

[15]

O. Lupanov. A method of circuit synthesis. Izvestiya VUZ, Radiofizika, 1(1):120-140, 1959. (in Russian).

Google Scholar

[16]

O. Lupanov. On the synthesis of certain classes of control systems. In Problemy Kibernetiki 10, pages 63-97. Fizmatgiz, Moscow, 1963. (in Russian).

Google Scholar

[17]

W. Masek. Some NP-complete set covering problems. Manuscript, 1979.

Google Scholar

[18]

P. B. Miltersen, N. Vinodchadran, and O. Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In T. Asano, H. Imai, D. Lee, S. Nakano, and T. Tokuyama, editors, Proceedings of the Fifth Annual International Conference on Computing and Combinatorics, volume 1627 of Lecture Notes in Computer Science, pages 210-220. Springer Verlag, 1999. (COCOON'99).

Digital Library

Google Scholar

[19]

N. Nisan and A. Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149-167, 1994.

Digital Library

Google Scholar

[20]

J. Pollard. Theorems on factorization and primality testing. Proceedings of the Cambridge Philosophical Society, 76:521-528, 1974.

Crossref

Google Scholar

[21]

A. Razborov and S. Rudich. Natural proofs. Journal of Computer and System Sciences, 55:24-35, 1997.

Digital Library

Google Scholar

[22]

C. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28(1):59-98, 1949.

Crossref

Google Scholar

[23]

M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the Fifteenth Annual A CM Symposium on Theory of Computing, pages 330-335, 1983.

Digital Library

Google Scholar

[24]

V. Strassen. Einige Resultate /iber Berechnungskomplexit~it. Jahresberichte der DMV, 78:1-8, 1976.

Google Scholar

[25]

B. Trakhtenbrot. A survey of Russian approaches to perebor (brute-force search) algorithms. Annals of the History of Computing, 6(4):384-400, 1984.

Digital Library

Google Scholar

[26]

C. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31:169-181, 1985.

Digital Library

Google Scholar

[27]

S. Yablonski. The algorithmic difficulties of synthesizing minimal switching circuits. In Problemy Kibernetiki 2, pages 75-121. Fizmatgiz, Moscow, 1959. English translation in Problems of Cybernetics II.

Google Scholar

[28]

S. Yablonski. On the impossibility of eliminating perebor in solving some problems of circuit theory. Doklady Akademii Nauk SSSR, 124(1):44-47, 1959. English translation in Soviet Mathematics Doklady.

Google Scholar

[29]

S. Zachos and H. Heller. A decisive characterization of BPP. Information and Control, 69(1-3):125-135, 1986.

Digital Library

Google Scholar

Cited By

View all

Chen LHirahara SRen HMohar BShinkar IO'Donnell R(2024)Symmetric Exponential Time Requires Near-Maximum Circuit SizeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649624(1990-1999)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649624
Liu YPass R(2024)On One-Way Functions, the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity, and Computational DepthTheory of Cryptography10.1007/978-3-031-78011-0_8(222-252)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_8
Brandt N(2024)Lower Bounds for Levin–Kolmogorov ComplexityTheory of Cryptography10.1007/978-3-031-78011-0_7(191-221)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_7
Show More Cited By

Index Terms

Circuit minimization problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Reversible Logic Synthesis for Minimization of Full-Adder Circuit
DSD '03: Proceedings of the Euromicro Symposium on Digital Systems Design

Reversible logic is of the growing importance to manyfuture technologies. A reversible circuit maps eachoutput vector, into a unique input vector, and vice versa.This paper introduces an approach to synthesis thegeneralized multi-rail reversible ...
Nonlocal image denoising via adaptive tensor nuclear norm minimization

Nonlocal self-similarity shows great potential in image denoising. Therefore, the denoising performance can be attained by accurately exploiting the nonlocal prior. In this paper, we model nonlocal similar patches through the multi-linear approach and ...
Clock-delayed domino for dynamic circuit design

Clock-delayed (CD) domino is a self-timed dynamic logic family developed to provide single-rail gates with inverting or noninverting outputs. CD domino is a complete logic family and is as easy to design with as static CMOS circuits from a logic design ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing

May 2000

756 pages

ISBN:1581131844

DOI:10.1145/335305

Chairmen:
Frances Yao,
Eugene Luks

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 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC00

Sponsor:

SIGACT

STOC00: The 32nd Annual ACM Symposium on Theory of Computing

May 21 - 23, 2000

Oregon, Portland, USA

Acceptance Rates

STOC '00 Paper Acceptance Rate 85 of 182 submissions, 47%;

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

115
Total Citations
View Citations
1,777
Total Downloads

Downloads (Last 12 months)302
Downloads (Last 6 weeks)39

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen LHirahara SRen HMohar BShinkar IO'Donnell R(2024)Symmetric Exponential Time Requires Near-Maximum Circuit SizeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649624(1990-1999)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649624
Liu YPass R(2024)On One-Way Functions, the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity, and Computational DepthTheory of Cryptography10.1007/978-3-031-78011-0_8(222-252)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_8
Brandt N(2024)Lower Bounds for Levin–Kolmogorov ComplexityTheory of Cryptography10.1007/978-3-031-78011-0_7(191-221)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_7
Liu YPass R(2024)A Direct PRF Construction from Kolmogorov ComplexityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_14(375-406)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-3-031-58737-5_14
Hirahara SLu ZRen H(2023)Bounded RelativizationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.6(1-45)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.6
Austrin PRisse K(2023)Sum-of-Squares Lower Bounds for the Minimum Circuit Size ProblemProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.31(1-21)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.31
Ilango RLi JWilliams RSaha BServedio R(2023)Indistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585187(1076-1089)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585187
Huang YIlango RRen HSaha BServedio R(2023)NP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585154(1067-1075)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585154
Hirahara SSaha BServedio R(2023)Capturing One-Way Functions via NP-Hardness of Meta-ComplexityProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585130(1027-1038)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585130
Ilango R(2023)SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00048(733-742)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00048
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

Reversible Logic Synthesis for Minimization of Full-Adder Circuit

Nonlocal image denoising via adaptive tensor nuclear norm minimization

Clock-delayed domino for dynamic circuit design