Valentine Kabanets
- 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). Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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). Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 13.C. Lautemann. BPP and the polynomial time hierarchy. Information Processing Letters, 17:215-218, 1983.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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). Google ScholarDigital Library
- 19.N. Nisan and A. Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149-167, 1994. Google ScholarDigital Library
- 20.J. Pollard. Theorems on factorization and primality testing. Proceedings of the Cambridge Philosophical Society, 76:521-528, 1974.Google ScholarCross Ref
- 21.A. Razborov and S. Rudich. Natural proofs. Journal of Computer and System Sciences, 55:24-35, 1997. Google ScholarDigital Library
- 22.C. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28(1):59-98, 1949.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 26.C. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31:169-181, 1985. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Circuit minimization problem
Recommendations
Reversible Logic Synthesis for Minimization of Full-Adder Circuit
DSD '03: Proceedings of the Euromicro Symposium on Digital Systems DesignReversible 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