**Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!)**,- Guest Piece for the Complexity Theory Column, edited by
Lane Hemaspaandra,
SIGACT NEWS 54
March, 2023, pp. 63--81.
**Robustness for Space-Bounded Statistical Zero Knowledge**,- (with
Jacob Gray,
Saachi Mutreja,
Harsha Tirumala, and
Pengxiang Wang)
ECCC Report
TR22-138, 2022. Submitted for publication.
**Kolmogorov Complexity Characterizes Statistical Zero Knowledge**,- (with
Shuichi Hirahara and
Harsha Tirumala),
Proc. 14th Innovations in
Theoretical Computer Science (ITCS'23) 2023,
Leibniz International Proceedings in Informatics (LIPIcs) 251,
pp. 3:1--3:19.
There is a video of a Princeton Theory Lunch talk on this paper (Sept. 30, 2022).
It's a blackboard talk, and the writing on the blackboard is hard to read in the
video.
**Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization**,-
New Zealand Journal of
Mathematics 52 (2021), pp. 585-604; special issue on
Vaughan Jones. An earlier version appeared as
**The New Complexity Landscape around Circuit Minimization**, Proc. 14th International Conference on Language and Automata Theory and Applications (LATA 2020), Lecture Notes in Computer Science 12038, pp. 3-16. **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.
**Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity**,- (with
John Gouwar,
Shuichi Hirahara,
and Caleb Robelle ),
*Theoretical Computer Science*940(B), 2023, 206-224; special issue for Péter Gács. (An earlier version appeared in preliminary form in Proc. 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs) 212, pp. 54:1--54:17.) See also ECCC Report TR21-010, 2021. **A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity**,- (with
Azucena Garvìa Bosshard and
Amulya Musipatla),
ECCC Report
TR20-158, 2020.
**Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity**,-
in
Complexity and Approximation, in Memory of Ker-I Ko,
edited by Ding-Zhu Du and Jie Wang,
Lecture
Notes in Computer Science 12000, pp. 8-18,
Springer-Verlag, 2020.
**The Non-Hardness of Approximating Circuit Size**,- (with Rahul Ilango, and
Neekon Vafa),
*Theory of Computing Systems*, 65,3 (2021) 559-578. An earlier version appeared x in Proc. 14th International Computer Science Symposium in Russia (CSR 2019), Lecture Notes in Computer Science 11532, pp. 13-24. **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.
**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.