Circuit minimization problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Circuit minimization problem

Full text

Pdf (733 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 73 - 79

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Valentine Kabanets	Department of Computer Science, University of Toronto, Toronto, Canada
Jin-Yi Cai	Department of Computer Science, State University of New York at Buffalo, Buffalo, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 47, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335314 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, A new general derandomization method, Journal of the ACM (JACM), v.45 n.1, p.179-213, Jan. 1998 [doi>10.1145/273865.273933]
	2	A. E. Andreev , A. E. F. Clementi , J. D. P. Rolim , L. Trevisan, Weak random sources, hitting sets, and BPP simulations, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.264, October 19-22, 1997
	3	László Babai , Lance Fortnow , Noam Nisan , Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Computational Complexity, v.3 n.4, p.307-318, Oct. 1993 [doi>10.1007/BF01275486]
	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.
	5	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	Oded Goldreich , Avi Wigderson, Improved Derandomization of BPP Using a Hitting Set Generator, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.131-137, August 08-11, 1999
	8	O. Goldreich and D. Zuckerman. Another proof that BPPCPH (and more). Electronic Colloquium on Computational Complexity, TR97-045, 1997.
	9	Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Near-Optimal Conversion of Hardness into Pseudo-Randomness, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.181, October 17-18, 1999
	10	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
	11	R. Kannan. Circuit-size lower bounds and nonreducibility to sparse sets. Information and Control, 55'40-56, 1982.
	12	Johannes Köbler , Osamu Watanabe, New Collapse Consequences of NP Having Small Circuits, SIAM Journal on Computing, v.28 n.1, p.311-324, Feb. 1999 [doi>10.1137/S0097539795296206]
	13	C. Lautemann. BPP and the polynomial time hierarchy. Information Processing Letters, 17:215-218, 1983.
	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.
	15	O. Lupanov. A method of circuit synthesis. Izvestiya VUZ, Radiofizika, 1(1):120-140, 1959. (in Russian).
	16	O. Lupanov. On the synthesis of certain classes of control systems. In Problemy Kibernetiki 10, pages 63-97. Fizmatgiz, Moscow, 1963. (in Russian).
	17	W. Masek. Some NP-complete set covering problems. Manuscript, 1979.
	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).
	19	Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
	20	J. Pollard. Theorems on factorization and primality testing. Proceedings of the Cambridge Philosophical Society, 76:521-528, 1974.
	21	Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
	22	C. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28(1):59-98, 1949.
	23	Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
	24	V. Strassen. Einige Resultate /iber Berechnungskomplexit~it. Jahresberichte der DMV, 78:1-8, 1976.
	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.
	26	Christopher B Wilson, Relativized circuit complexity, Journal of Computer and System Sciences, v.31 n.2, p.169-181, Sept. 1985 [doi>10.1016/0022-0000(85)90040-6]
	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.
	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.
	29	Stathis Zachos , Hans Heller, A decisive characterization of BPP, Information and Control, v.69 n.1-3, p.125-135, April/May/June 1986 [doi>10.1016/S0019-9958(86)80044-4]

CITED BY 2

	Scott Aaronson, Guest Column: NP-complete problems and physical reality, ACM SIGACT News, v.36 n.1, March 2005
	Eyal Kushilevitz , Enav Weinreb, On the complexity of communication complexity, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA