Papers on Probabilistic Computation and Derandomization
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.
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.
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
Eric Allender
,
Shuichi Hirahara
ACM Transactions on Computation Theory (TOCT), 2019
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.
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. 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.
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.
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 Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
,
(with
Lisa Hellerstein
,
Paul M. McCabe
,
Toniann Pitassi
, and
Michael Saks
),
SIAM J. Comp.
Vol. 38, 2008, 63-84. 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.
Derandomization and Distinguishing Complexity
,
(with
Michal Koucký
,
Detlef Ronneburger
, and
Sambuddha Roy
), Proc. 18th
Annual IEEE Conference on Computational Complexity
, 2003, pp. 209-220.
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.
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.
Almost-everywhere complexity hierarchies for nondeterministic time
(with
Richard Beigel
,
Ulrich Hertrampf
, and
Steven Homer
),
Theoretical Computer Science
Vol. 115, 1993, pp. 225-242. An earlier version appeared in
Proc. 7th Symposium on Theoretical Aspects of Computer Science (STACS 1990),
Lecture Notes in Computer Science
415, pp. 1-11.
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.
On generating solved instances of computational problems
,
(with
Martin Abadi
, Andrei Broder,
Joan Feigenbaum
, and
Lane Hemachandra
), in
Advances in Cryptology, Proc. CRYPTO '88
,
Lecture Notes in Computer Science
403, 1990, pp. 297-310.