Papers on Probabilistic Computation and Derandomization


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.

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems,
(with Shuichi Hirahara), ACM Transactions on Computation Theory (ToCT), 11,4 (2019) 27:1-27:27. An earlier version appeared in Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS '17), Leibniz International Proceedings in Informatics (LIPIcs) 83, pp. 54:1--54:14.

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.

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.

Uniform Derandomization from Pathetic Lower Bounds,
(with V Arvind, Rahul Santhanam and Fengming Wang), . Philosophical Transactions of the Royal Society, Series A, 370, 2012, 3512-3535. An earlier version appeared in Proc. 14th International Workshop on Randomization and Computation (RANDOM/APPROX 2010), Lecture Notes in Computer Science 6302, pp. 380-393, 2010.

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.

On the Complexity of Numerical Analysis,
(with Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen), SIAM J. Comp. Vol. 38, 2009, 1987-2006. An earlier version appeared in Proc. 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 331--339.

Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table,
(with Lisa Hellerstein, Paul M. McCabe, Toniann Pitassi, and Michael Saks), SIAM J. Comp. Vol. 38, 2008, 63-84. 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.

Derandomization and Distinguishing Complexity,
(with Michal Koucký, Detlef Ronneburger, and Sambuddha Roy), Proc. 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 209-220.

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.

Making nondeterminism unambiguous,
(with Klaus Reinhardt), SIAM J. Comp. Vol. 29, 2000, 1118-1131. An earlier version appeared in FOCS 1997, pp. 244-253.

Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds,
(with Klaus Reinhardt and Shiyu Zhou), Journal of Computer and System Sciences 59 (1999) 164-181. Preliminary versions of this work appeared in in Proc. 13th Annual IEEE Conference on Computational Complexity, 1998, pp. 92-100, and in the workshop on Randomized Algorithms, 1998.

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.

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.

On generating solved instances of computational problems,
(with Martin Abadi, Andrei Broder, Joan Feigenbaum, and Lane Hemachandra), in Advances in Cryptology, Proc. CRYPTO '88, Lecture Notes in Computer Science 403, 1990, pp. 297-310.