Papers on Kolmogorov Complexity


Reductions to the set of random strings: The resource-bounded case,
(with Harry Buhrman, Luke Friedman, Bruno Loff), to appear in Proc. 37th International Symposium on Mathematical Foundations of Computer Science (MFCS '12), 2012, Lecture Notes in Computer Science.

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.

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic,
(with George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret), submitted.

Limits on the Computational Power of Random Strings,
(with Luke Friedman and William Gasarch), Information and Computation, to appear (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.

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.