Papers Proving Complexity-Theoretic Lower Bounds


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.

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.

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.

Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds,
in Proc. 3rd International Computer Science Symposium in Russia (CSR 2008), Lecture Notes in Computer Science 5010, pp. 3-10, 2008.

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.

Time-Space Tradeoffs in the Counting Hierarchy,
(with Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay), in Proc. 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 295-302.

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.

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.

Algebraic methods for proving lower bounds in circuit complexity,
Proc. Workshop on Algebraic Methods in Complexity Theory, December, 1994, Institute of Mathematical Sciences, Madras, India.

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