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.