Papers Dealing with Logspace-Bounded Complexity Classes

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.

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs ,
(with Nikhil Balaji, Samir Datta, and Rameshwar Pratap) Computability (The Journal of the Association Computability in Europe) 12 (2023) pp. 145-173. Some of this work appeared in preliminary form as Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs,
(with Nikhil Balaji and Samir Datta), in Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS '14), Lecture Notes in Computer Science 8635, pp. 13-24, 2014.

Depth-First Search in Directed Planar Graphs, Revisited,
(with Archit Chauhan and Samir Datta), Acta Informatica, 59 (2022) 289-319; special issue for Klaus-Jörn Lange. (An earlier version appeared in preliminary form in 46th International Symposium on Mathematical Foundations of Computer Science (MFCS '21), Leibniz International Proceedings in Informatics (LIPIcs) 202, pp. 7:1 -- 7:22. See also ECCC Report TR20-074, 2020.

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.

Better Complexity Bounds for Cost Register Automata,
(with Andreas Krebs and Pierre McKenzie ), Theory of Computing Systems 63(3), 2019, 367-385. 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. 24:1--24:14.

Complexity of Regular Functions,
(with Ian Mertz), Journal of Computer and System Sciences 104, 2019, 5-16. (Special issue on LATA '15.) An earlier version appeared in Proc. 9th International Conference on Language and Automata Theory and Applications (LATA '15), Lecture Notes in Computer Science 8977, pp. 449-460, 2015.

Dual VP Classes,
(with Anna Gál and Ian Mertz), Computational Complexity 26 (2017) 583-625. Springer provides free read-only access to this publication. An earlier version appeared in Proc. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS '15), Lecture Notes in Computer Science 9235, pp. 14-25, 2015. (Presentation available on-line.) (A companion paper is Arithmetic Circuit Classes over Zm (with Asa Goodwillie), ECCC Technical Report TR15-145, 2015.)

On the Power of Algebraic Branching Programs of Width Two,
(with Fengming Wang), Computational Complexity 25 (2016) 217-253. Springer provides free read-only access to this publication. An earlier version appeared in Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), 2011, Lecture Notes in Computer Science 6755, pp. 736-747.

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata,
(with Klaus-Jörn Lange). Theory of Computing 10(8), 2014, 199-215. An earlier version appeared in Proc. 25th Annual IEEE Conference on Computational Complexity, 2010, pp. 172-180.

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. Special issue on the Turing Centenary. See also the Comment on ECCC. 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.

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, 2011, 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.)

Amplifying Lower Bounds by Means of Self-Reducibility,
(with Michal Koucký), Journal of the ACM 57,3 (2010) 14:1 - 14:36. An earlier version appeared in Proc. 23rd Annual IEEE Conference on Computational Complexity, 2008, pp. 31--40.

Planar and Grid Graph Reachability Problems,
(with David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta and Sambuddha Roy), Theory of Computing Systems Vol. 45, 2009, 675-723. (This material appeared in preliminary form in the papers The Directed Planar Reachability Problem, Proc. 25th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2005, Lecture Notes in Computer Science 3821, pp. 238-249, and Grid Graph Reachability Problems, Proc. 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 299--313. See also Reachability Problems: An Update, Proc. Computation and Logic in the Real World, 3rd Conference of Computability in Europe, (CiE 2007), Lecture Notes in Computer Science 4497, 2007, pp. 25-27.)

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem,
(with Michael Bauland, Neil Immerman, Henning Schnoor, and Heribert Vollmer), Journal of Computer and System Sciences 75, 2009, 245-254. An earlier version appeared in Proc. 30th International Symposium on Mathematical Foundations of Computer Science (MFCS '05), 2005, Lecture Notes in Computer Science 3618, pp. 71-82.

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.)

The Complexity of Planarity Testing,
(with Meena Mahajan). Information and Computation 189 (2004) 117-134. An earlier version appeared in in Proc. 17th International Symposium on Theoretical Aspects of Computer Science (STACS), 2000, Lecture Notes in Computer Science 1770, pp. 87-98.

Arithmetic Complexity, Kleene Closure, and Formal Power Series,
(with V Arvind and Meena Mahajan), Theory of Computing Systems 36 (2003) 303-328.

Characterizing Small Depth and Small Space Classes by Operators of Higher Types,
(with Manindra Agrawal, Samir Datta), Heribert Vollmer, and Klaus W. Wagner),
Chicago Journal of Theoretical Computer Science, 2000, article 2.

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.

The complexity of matrix rank and feasible systems of linear equations
(with Robert Beals and Mitsunori Ogihara). Computational Complexity, Vol. 8, 1999, 99-126. A preliminary version appeared in Proc. 28th STOC 1996, pp. 161-167.

RUSPACE(log n) is contained in DSPACE(log^2 n/loglog n),
(with Klaus-Jörn Lange). Theory of Computing Systems, Vol. 31, 1998, pp. 539-550. Special issue devoted to the 7th Annual International Symposium on Algorithms and Computation ( ISAAC '96).

Relationships among PL, #L, and the determinant
(with Mitsunori Ogihara), RAIRO - Theoretical Informatics and Applications Vol. 30, 1996, pp. 1-21. (See also a comment on this paper.) An earlier version appeared in Proc. 9th IEEE Structure in Complexity Theory Conference, 1994, pp. 267-278.