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.