Papers on the Structure of Complexity Classes and Reducibilities


One-way Functions and a Conditional Variant of MKTP ,
(with Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich ), Proc. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs) 213, pp. 7:1--7:19. See also ECCC Report TR21-009, 2021.

Minimum Circuit Size, Graph Isomorphism and Related Problems,
(with Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan), SIAM J. Comp., Vol. 47(4), 2018, 1339-1372. An earlier version appeared in Proc. 9th Innovations in Theoretical Computer Science (ITCS '18), Leibniz International Proceedings in Informatics (LIPIcs) 94, pp. 20:1--20:20. (See the Presentation at the Simons Institute.)

Zero Knowledge and Circuit Minimization,
(with Bireswar Das), Information and Computation, 256 (2017) 2-8. (Special issue on MFCS 2014.) An earlier version appeared in Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS '14), Lecture Notes in Computer Science 8635, pp. 25-32, 2014. (Presentation available on-line.)

The Complexity of Complexity,
in Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Springer-Verlag, 2017, Lecture Notes in Computer Science 10010, pp. 79--94, 2017.

The Minimum Oracle Circuit Size Problem,
(with Dhiraj Holden and Valentine Kabanets), Computational Complexity 26 (2017) 469-496. Springer provides free read-only access to this publication. An earlier version appeared in Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), 2015, pp. 21-33.

Investigations Concerning the Structure of Complete Sets,
in Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Progress in Computer Science and Applied Logic vol. 26, 2014, pp. 23-35.

Power from Random Strings,
(with Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger), SIAM J. Comp. Vol. 35, 2006, 1467-1493. An earlier version appeared in FOCS 2002, pp. 669-678.

When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity.,
Invited Paper, Proc. 21st annual .Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2001, Lecture Notes in Computer Science 2245, pp. 1-15.

Reducing the complexity of reductions
(with Manindra Agrawal, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich), Computational Complexity 10 (2001) 117-138. A preliminary version appeared in Proc. 29th STOC 1997, pp. 730-738.

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
(with Manindra Agrawal and Steven Rudich), Journal of Computer and System Sciences Vol. 57, 1998, 127-143. An earlier version appeared in the Eleventh Annual IEEE Conference on Computational Complexity (1996).

A first-order isomorphism theorem
(with José Balcázar and Neil Immerman), SIAM J. Comp. Vol. 26, 1997, pp. 557-567. An earlier version appeared in Proc. 10th International Symposium on Theoretical Aspects of Computer Science (STACS), 1993, Lecture Notes in Computer Science 665, pp. 163-174.

Almost-everywhere complexity hierarchies for nondeterministic time
(with Richard Beigel, Ulrich Hertrampf, and Steven Homer), Theoretical Computer Science Vol. 115, 1993, pp. 225-242. An earlier version appeared in Proc. 7th Symposium on Theoretical Aspects of Computer Science (STACS 1990), Lecture Notes in Computer Science 415, pp. 1-11.

Relating equivalence and reducibility to sparse sets
(with Lane Hemachandra, Mitsunori Ogihara, and Osamu Watanabe), SIAM Journal on Computing Vol. 21, 1992, pp. 521-539. An earlier version appeared in Proc. 6th IEEE Structure in Complexity Theory Conference, 1991.

Lower bounds for the low hierarchy
(with Lane Hemachandra), Journal of the ACM 39 (1992) 234 - 251. An earlier version appeared in Proc. 16th International Colloquium on Automata, Languages, and Programming (ICALP 1989), Lecture Notes in Computer Science 372, pp. 31-45.

Rudimentary reductions revisited
(with Vivek Gore), Information Processing Letters Vol. 40, 1991, pp. 89-95.

Limitations of the Upward Separation Technique,
Mathematical Systems Theory 24 (1991) 53-67. An earlier version appeared in Proc. 16th International Colloquium on Automata, Languages, and Programming (ICALP 1989), Lecture Notes in Computer Science 372, pp. 18-30.

Oracles vs Proof techniques that do not relativize,
in Proc. SIGAL International Symposium on Algorithms, 1990, Lecture Notes in Computer Science 450, pp. 39-52.

Width-bounded reducibility and binary search over complexity classes, (with Chris Wilson)
in Proc. 5th Annual IEEE Structure in Complexity Theory Conference, 1990, pp. 122-129.

Kolmogorov complexity and degrees of tally sets
(with Osamu Watanabe), Information and Computation Vol. 86 1990, pp. 160-178. An earlier version appeared in Proc. 3rd IEEE Structure in Complexity Theory Conference, 1988.

P-printable sets
(with Roy Rubinstein), SIAM Journal on Computing Vol. 17, 1988, pp. 1193-1202. An earlier version appeared in Proc. 1st Structure in Complexity Theory Conference, 1986, Lecture Notes in Computer Science 223, pp. 1-11.

Isomorphisms and 1-L reductions
Journal of Computer and System Sciences Vol. 36, 1988, 336-350. An earlier version appeared in Proc. 1st Structure in Complexity Theory Conference, 1986, Lecture Notes in Computer Science 223, pp. 12-22.