**The Complexity of Complexity**,- To appear in Computability and Complexity, a Festschrift in honor
of Rod Downey,
Lecture
Notes in Computer Science, Festschrift series, 2017.
**Graph Isomorphism and Circuit Size**,- (with Joshua A. Grochow and
Cristopher Moore),
*ECCC Technical Report TR15-162*, 2015. (See the Presentation at the Simons Institute.) **The Minimum Oracle Circuit Size Problem**,- (with Dhiraj Holden and
Valentine Kabanets),
*Computational Complexity*, to appear. An earlier version appeared in*Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS)*, 2015, pp. 21-33. **Zero Knowledge and Circuit Minimization**,- (with
Bireswar Das),
*Information and Computation*, to appear. (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.) **Reductions to the set of random strings: The resource-bounded case**,- (with Harry Buhrman,
Luke Friedman,
Bruno Loff),
*Logical Methods in Computer Science*10 (3:5) 2014, pp. 1-18. (Special issue on The Turing Centenary Conference: CiE 2012). An earlier version appeared in Proc. 37th International Symposium on Mathematical Foundations of Computer Science (MFCS '12), 2012, Lecture Notes in Computer Science 7464, pp. 88-99, 2012. **Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic**,- (with George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret),
- Chicago Journal of
Theoretical Computer Science, 2013, article 5.
**Limits on the Computational Power of Random Strings**,- (with Luke Friedman
and William Gasarch),
*Information and Computation*, 222, 2013, 80-92. (Special issue on ICALP 2011). An earlier version appeared in*Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP)*, 2011, Lecture Notes in Computer Science 6755, pp. 293-304. (A companion paper is Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions (with Luke Friedman and William Gasarch), ECCC Technical Report TR10-138, 2010. **Curiouser and Curiouser: The Link between Incompressibility and Complexity**,- in Proc.
Computability in Europe: (CiE 2012),
Lecture
Notes in Computer Science 7318, pp. 11-16, 2012.
**Avoiding Simplicity is Complex**, (with Holger Spakowski),-
*Theory of Computing Systems*51, 2012, 282-296. An earlier version appeared in Proc. Computability in Europe: Programs, Proofs, Processes (CiE 2010), Lecture Notes in Computer Science 6158, pp. 1-10, 2010. **Randomness as Circuit Complexity (and the Connection to Pseudorandomness)**,-
in
**Randomness through Computation: Some answers, more questions**, edited by Hector Zenil, World Scientific Press, 2011, pp. 267-274. -
**The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory**,- (with Michal
Koucký,
Detlef Ronneburger,
and Sambuddha Roy),
*Journal of Computer and System Sciences*77, 2010, 14-40. (Some of this material appeared in preliminary form in the paper**Derandomization and Distinguishing Complexity**, Proc. 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 209-220.) **Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds**,- in
Proc. 10th International Workshop on Descriptional Complexity of
Formal Systems (DCFS 2008), 2008, pp. 7-13.
**Minimizing DNF Formulas and AC^0 Circuits Given a Truth Table**,- (with Lisa Hellerstein,
Paul M. McCabe,
Toniann Pitassi, and
Michael Saks),
To appear in
*SIAM J. Comp.*An earlier version appeared in Proc. 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 237--251. **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. **NL-printable sets and Nondeterministic Kolmogorov Complexity**,-
*Theoretical Computer Science*Vol. 355, 2006 127-138. (An earlier version appeared as an invited paper in Proc. 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003) , 2003, pp. 6-20.) **Derandomization and Distinguishing Complexity**,- (with Michal
Koucký,
Detlef Ronneburger,
and Sambuddha Roy),
Proc.
18th Annual
IEEE Conference on Computational Complexity, 2003, 209-220.
**What Can be Efficiently Reduced to the Kolmogorov-Random Strings?**,- (with Harry Buhrman
and Michal
Koucký),
*Annals of Pure and Applied Logic*138 (2006) 2-19. An earlier version appeared in*Proc. 21st International Symposium on Theoretical Aspects of Computer Science (STACS)*, 2004, Lecture Notes in Computer Science 2996, pp. 584-595. **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. **Applications of time-bounded Kolmogorov complexity in complexity theory**,- in
**Kolmogorov Complexity and Computational Complexity**, Osamu Watanabe, editor, EATCS Monograph Series, Springer-Verlag, 1992, pp. 4-22. Earlier versions of this work appeared in Proc. AAAI Spring Symposium on the Theory and Application of Minimal-Length Encoding, and in Proc. 4th IEEE Structure in Complexity Theory Conference, 1989. **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. **Some consequences of the existence of pseudorandom generators**-
*Journal of Computer and System Sciences*Vol. 39, 1989, 101-124. An earlier version appeared in Proc. 19th STOC, 1987, pp. 151-159. **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.