Papers on Circuit Complexity


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.

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.

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.

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.

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.

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

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.

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.

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.

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.

Width-parameterized SAT: time-space tradeoffs,
(with Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, and Bangsheng Tang),
Theory of Computing 10(12), 2014, 297-339.

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.

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.

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.

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

New Surprises from Self-Reducibility, in Programs, Proofs, Processes, (ed. F. Ferreira, H. Guerra, E. Mayordomo, and J. Rasga), Abstract and Handout Booklet,
6th Conference on Computability in Europe (CiE 2010), Centre for Applied Mathematics and Information Technology, Dept. of Mathematics, University of Azores, pp. 1--5, 2010.

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.

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

Topology inside NC1,
(with Samir Datta and Sambuddha Roy), Proc. 20th Annual IEEE Conference on Computational Complexity, 2005, pp. 298-307.

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.

Complexity of some Arithmetic Problems for Binary Polynomials,
(with Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks and Igor Shparlinski). Computational Complexity 12 (2003) 23-47.

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

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

Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication,
(with William Hesse and David A. Mix Barrington), Journal of Computer and System Sciences 65 (2002) 695-716. An earlier version appeared in Proc. 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 150-159.

Reducing the complexity of reductions
(with Manindra Agrawal, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich), Computational Complexity 10 (2001) 117-138. A preliminary version appeared in Proc. 29th STOC 1997, pp. 730-738.

A Lower Bound for Primality,
(with Michael Saks and Igor Shparlinski) Journal of Computer and System Sciences 62 (2001) 356-366. Prelininary version appeared in Proc. 14th Annual IEEE Conference on Computational Complexity, 1999, pp. 10-14.

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.

On TC^0, AC^0, and Arithmetic Circuits,
(with Manindra Agrawal and Samir Datta), Journal of Computer and System Sciences 60 (2000) 395-421. An earlier version appeared in the twelfth Annual IEEE Conference on Computational Complexity, 1997.

Bounded Depth Arithmetic Circuits: Counting and Closure,
(with Andris Ambainis, David A. Mix Barrington, Samir Datta, and Huong LêThanh), Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP), 1999, Lecture Notes in Computer Science 1644, pp. 149-158.

The Permanent Requires Large Uniform Threshold Circuits.
Chicago Journal of Theoretical Computer Science, 1999, article 7. An earlier version appeared in the 2nd Annual International Computing and Combinatorics Conference (COCOON 1996), Lecture Notes in Computer Science 1090, pp. 127-135.

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
(with Manindra Agrawal and Steven Rudich), Journal of Computer and System Sciences Vol. 57, 1998, 127-143. An earlier version appeared in the Eleventh Annual IEEE Conference on Computational Complexity (1996).

Non-commutative arithmetic circuits: depth reduction and size lower bounds
(with Jia Jiao, Meena Mahajan, and V. Vinay), Theoretical Computer Science Vol. 209, 1998, 47-86. This is a revision and extension of the paper Depth reduction for noncommutative arithmetic circuits (with Jia Jiao), in Proc. 25th STOC 1993, pp. 515-522.

A uniform circuit lower bound for the permanent
(with Vivek Gore), SIAM Journal on Computing Vol. 23, 1994, pp. 1026-1049.

Depth reduction for circuits of unbounded fan-in
(with Ulrich Hertrampf), Information and Computation Vol. 112 1994, pp. 217-238. (See also FOCS 1989, pp. 580-584, and MFCS 1990, LNCS 452, pp. 158-164.)

On strong separations from AC^0
(with Vivek Gore), in Advances in Computational Complexity Theory, Jin-Yi Cai, ed., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 13, AMS Press, 1993, pp. 21-37. An earlier version appeared in Proc. 8th International Conference on Fundamentals of Computation Theory (FCT '91), Lecture Notes in Computer Science 529, pp. 1-15.

The complexity of computing maximal word functions
(with Danilo Bruschi and Giovanni Pighizzini), Computational Complexity 3, 1993, pp. 368-391.

Rudimentary reductions revisited
(with Vivek Gore), Information Processing Letters Vol. 40, 1991, pp. 89-95.