Eric Allender

227 papers A* 13A 21B 11C 6Misc 3Journal 139Unranked 27
YearRankTypeTitle / Venue / Authors
2026 J jnl
Comment on "SAT requires exhaustive search".
Frontiers Comput. Sci.
Eric Allender, Ryan Williams
2025 J jnl
Robustness for Space-Bounded Statistical Zero Knowledge.
ACM Trans. Comput. Theory
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
2023 J jnl
Cryptographic hardness under projections for time-bounded Kolmogorov complexity.
Theor. Comput. Sci.
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
2023 J jnl
Guest Column: Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!
SIGACT News
Eric Allender
2023 A conf
Kolmogorov Complexity Characterizes Statistical Zero Knowledge.
ITCS
Eric Allender, Shuichi Hirahara, Harsha Tirumala
2023 J jnl
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs.
Comput.
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
2023 A conf
Robustness for Space-Bounded Statistical Zero Knowledge.
APPROX/RANDOM
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
2022 J jnl
Depth-first search in directed planar graphs, revisited.
Acta Informatica
Eric Allender, Archit Chauhan, Samir Datta
2022 J jnl
Kolmogorov Complexity Characterizes Statistical Zero Knowledge.
Electron. Colloquium Comput. Complex.
Eric Allender, Shuichi Hirahara, Harsha Tirumala
2022 J jnl
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs.
Electron. Colloquium Comput. Complex.
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
2022 J jnl
Robustness for Space-Bounded Statistical Zero Knowledge.
Electron. Colloquium Comput. Complex.
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
2021 B conf
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity.
ISAAC
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
2021 J jnl
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
2021 B conf
Depth-First Search in Directed Planar Graphs, Revisited.
MFCS
Eric Allender, Archit Chauhan, Samir Datta
2021 — conf
One-Way Functions and a Conditional Variant of MKTP.
FSTTCS
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021 J jnl
One-way Functions and Partial MCSP.
Electron. Colloquium Comput. Complex.
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021 J jnl
The Non-hardness of Approximating Circuit Size.
Theory Comput. Syst.
Eric Allender, Rahul Ilango, Neekon Vafa
2020 J jnl
A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Eric Allender, Azucena Garvía Bosshard, Amulya Musipatla
2020 J jnl
Depth-First Search in Directed Graphs, Revisited.
Electron. Colloquium Comput. Complex.
Eric Allender, Archit Chauhan, Samir Datta
2020 — conf
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity.
Complexity and Approximation
Eric Allender
2020 C conf
The New Complexity Landscape Around Circuit Minimization.
LATA
Eric Allender
2020 J jnl
The New Complexity Landscape around Circuit Minimization.
Electron. Colloquium Comput. Complex.
Eric Allender
2019 J jnl
Better Complexity Bounds for Cost Register Automata.
Theory Comput. Syst.
Eric Allender, Andreas Krebs, Pierre McKenzie
2019 J jnl
Complexity of regular functions.
J. Comput. Syst. Sci.
Eric Allender, Ian Mertz
2019 J jnl
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems.
ACM Trans. Comput. Theory
Eric Allender, Shuichi Hirahara
2019 J jnl
Planarity, Exclusivity, and Unambiguity.
Electron. Colloquium Comput. Complex.
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee
2019 — conf
Syntactic Separation of Subset Satisfiability Problems.
APPROX-RANDOM
Eric Allender, Martin Farach-Colton, Meng-Tsung Tsai
2019 Misc conf
The Non-hardness of Approximating Circuit Size.
CSR
Eric Allender, Rahul Ilango, Neekon Vafa
2018 A conf
Minimum Circuit Size, Graph Isomorphism, and Related Problems.
ITCS
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2018 J jnl
Minimum Circuit Size, Graph Isomorphism, and Related Problems.
SIAM J. Comput.
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2018 J jnl
The Non-Hardness of Approximating Circuit Size.
Electron. Colloquium Comput. Complex.
Eric Allender, Rahul Ilango, Neekon Vafa
2017 B conf
Better Complexity Bounds for Cost Register Automata.
MFCS
Eric Allender, Andreas Krebs, Pierre McKenzie
2017 J jnl
Better Complexity Bounds for Cost Register Machines.
Electron. Colloquium Comput. Complex.
Eric Allender, Andreas Krebs, Pierre McKenzie
2017 J jnl
Dual VP Classes.
Comput. Complex.
Eric Allender, Anna Gál, Ian Mertz
2017 J jnl
Minimum Circuit Size, Graph Isomorphism, and Related Problems.
CoRR
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2017 J jnl
Minimum Circuit Size, Graph Isomorphism, and Related Problems.
Electron. Colloquium Comput. Complex.
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2017 J jnl
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems.
Electron. Colloquium Comput. Complex.
Eric Allender, Shuichi Hirahara
2017 B conf
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems.
MFCS
Eric Allender, Shuichi Hirahara
2017 J jnl
News from ACM transactions on Computation theory: New Editor-in-Chief.
Bull. EATCS
Eric Allender
2017 — conf
The Complexity of Complexity.
Computability and Complexity
Eric Allender
2017 J jnl
The Minimum Oracle Circuit Size Problem.
Comput. Complex.
Eric Allender, Dhiraj Holden, Valentine Kabanets
2017 J jnl
Zero knowledge and circuit minimization.
Inf. Comput.
Eric Allender, Bireswar Das
2016 J jnl
On the power of algebraic branching programs of width two.
Comput. Complex.
Eric Allender, Fengming Wang
2015 J jnl
Arithmetic circuit classes over Zm.
Electron. Colloquium Comput. Complex.
Eric Allender, Asa Goodwillie
2015 C conf
Complexity of Regular Functions.
LATA
Eric Allender, Ian Mertz
2015 J jnl
Complexity of Regular Functions.
Electron. Colloquium Comput. Complex.
Eric Allender, Ian Mertz
2015 — conf
Dual VP Classes.
MFCS (2)
Eric Allender, Anna Gál, Ian Mertz
2015 J jnl
Graph Isomorphism and Circuit Size.
CoRR
Eric Allender, Joshua A. Grochow, Cristopher Moore
2015 J jnl
Graph Isomorphism and Circuit Size.
Electron. Colloquium Comput. Complex.
Eric Allender, Joshua A. Grochow, Cristopher Moore
2015 A conf
The Minimum Oracle Circuit Size Problem.
STACS
Eric Allender, Dhiraj Holden, Valentine Kabanets
2014 — ch.
Complexity Theory.
Computing Handbook, 3rd ed. (1)
Eric Allender, Michael C. Loui, Kenneth W. Regan
2014 J jnl
Corrigendum to "Uniform constant-depth threshold circuits for division and iterated multiplication" [J. Comput. System Sci. 65(4) (2002) 695-716].
J. Comput. Syst. Sci.
William Hesse, Eric Allender, David A. Mix Barrington
2014 J jnl
Dual VP Classes.
Electron. Colloquium Comput. Complex.
Eric Allender, Anna Gál, Ian Mertz
2014 J jnl
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II.
ACM Trans. Comput. Theory
Eric Allender, Shafi Goldwasser
2014 — conf
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
MFCS (2)
Eric Allender, Nikhil Balaji, Samir Datta
2014 J jnl
Reductions to the set of random strings: The resource-bounded case.
Log. Methods Comput. Sci.
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2014 J jnl
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.
Theory Comput.
Eric Allender, Klaus-Jörn Lange
2014 J jnl
The Minimum Oracle Circuit Size Problem.
Electron. Colloquium Comput. Complex.
Eric Allender, Dhiraj Holden, Valentine Kabanets
2014 J jnl
Width-Parametrized SAT: Time--Space Tradeoffs.
Theory Comput.
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang
2014 — conf
Zero Knowledge and Circuit Minimization.
MFCS (2)
Eric Allender, Bireswar Das
2014 J jnl
Zero Knowledge and Circuit Minimization.
Electron. Colloquium Comput. Complex.
Eric Allender, Bireswar Das
2013 J jnl
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst.
Eric Allender, Vikraman Arvind, Meena Mahajan
2013 J jnl
Introduction to the special issue on innovations in theoretical computer science 2012.
ACM Trans. Comput. Theory
Eric Allender, Shafi Goldwasser
2013 J jnl
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Chic. J. Theor. Comput. Sci.
Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret
2013 J jnl
Limits on the computational power of random strings.
Inf. Comput.
Eric Allender, Luke Friedman, William I. Gasarch
2013 J jnl
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
Electron. Colloquium Comput. Complex.
Eric Allender, Nikhil Balaji, Samir Datta
2012 J jnl
Avoiding Simplicity is Complex.
Theory Comput. Syst.
Eric Allender, Holger Spakowski
2012 C conf
Curiouser and Curiouser: The Link between Incompressibility and Complexity.
CiE
Eric Allender
2012 J jnl
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Electron. Colloquium Comput. Complex.
Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret
2012 B conf
Reductions to the Set of Random Strings: The Resource-Bounded Case.
MFCS
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2012 J jnl
Reductions to the set of random strings: the resource-bounded case.
Electron. Colloquium Comput. Complex.
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2012 J jnl
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds.
Electron. Colloquium Comput. Complex.
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang
2011 — conf
Limits on the Computational Power of Random Strings.
ICALP (1)
Eric Allender, Luke Friedman, William I. Gasarch
2011 — conf
On the Power of Algebraic Branching Programs of Width Two.
ICALP (1)
Eric Allender, Fengming Wang
2011 J jnl
On the power of algebraic branching programs of width two.
Electron. Colloquium Comput. Complex.
Eric Allender, Fengming Wang
2011 J jnl
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.
J. Comput. Syst. Sci.
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy
2010 J jnl
Amplifying lower bounds by means of self-reducibility.
J. ACM
Eric Allender, Michal Koucký
2010 C conf
Avoiding Simplicity Is Complex.
CiE
Eric Allender
2010 J jnl
Avoiding Simplicity is Complex.
Electron. Colloquium Comput. Complex.
Eric Allender
2010 J jnl
Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions.
Electron. Colloquium Comput. Complex.
Eric Allender, Luke Friedman, William I. Gasarch
2010 J jnl
Limits on the Computational Power of Random Strings.
Electron. Colloquium Comput. Complex.
Eric Allender, Luke Friedman, William I. Gasarch
2010 A conf
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.
CCC
Eric Allender, Klaus-Jörn Lange
2010 J jnl
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.
Electron. Colloquium Comput. Complex.
Eric Allender, Klaus-Jörn Lange
2010 — conf
Uniform Derandomization from Pathetic Lower Bounds.
APPROX-RANDOM
Eric Allender, Vikraman Arvind, Fengming Wang
2010 J jnl
Uniform Derandomization from Pathetic Lower Bounds.
Electron. Colloquium Comput. Complex.
Eric Allender, Vikraman Arvind, Fengming Wang
2009 J jnl
A Status Report on the P Versus NP Question.
Adv. Comput.
Eric Allender
2009 J jnl
On the Complexity of Numerical Analysis.
SIAM J. Comput.
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2009 J jnl
Planar and Grid Graph Reachability Problems.
Theory Comput. Syst.
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2009 J jnl
Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007).
SIAM J. Comput.
Eric Allender, Vladlen Koltun, Maxim Sviridenko
2009 J jnl
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory.
Electron. Colloquium Comput. Complex.
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy
2009 J jnl
The complexity of satisfiability problems: Refining Schaefer's theorem.
J. Comput. Syst. Sci.
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
2008 A conf
Amplifying Lower Bounds by Means of Self-Reducibility.
CCC
Eric Allender, Michal Koucký
2008 J jnl
Amplifying Lower Bounds by Means of Self-Reducibility.
Electron. Colloquium Comput. Complex.
Eric Allender, Michal Koucký
2008 — conf
Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds?
CATS
Eric Allender
2008 — conf
Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds.
DCFS
Eric Allender
2008 — ch.
Computational Complexity Theory.
Wiley Encyclopedia of Computer Science and Engineering
Eric Allender
2008 Misc conf
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds.
CSR
Eric Allender
2008 J jnl
Minimizing Disjunctive Normal Form Formulas and AC
SIAM J. Comput.
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2007 C conf
Reachability Problems: An Update.
CiE
Eric Allender
2006 A conf
Grid Graph Reachability Problems.
CCC
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2006 A conf
Minimizing DNF Formulas and AC
CCC
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2006 J jnl
NL-printable sets and nondeterministic Kolmogorov complexity.
Theor. Comput. Sci.
Eric Allender
2006 A conf
On the Complexity of Numerical Analysis.
CCC
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2006 — conf
On the Complexity of Numerical Analysis.
Complexity of Boolean Functions
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2006 J jnl
Power from Random Strings.
SIAM J. Comput.
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
2006 J jnl
What can be efficiently reduced to the Kolmogorov-random strings?
Ann. Pure Appl. Log.
Eric Allender, Harry Buhrman, Michal Koucký
2005 J jnl
Grid Graph Reachability Problems
Electron. Colloquium Comput. Complex.
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2005 J jnl
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electron. Colloquium Comput. Complex.
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2005 J jnl
On the Complexity of Numerical Analysis
Electron. Colloquium Comput. Complex.
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2005 J jnl
Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword.
Comput. Complex.
Eric Allender
2005 J jnl
Special issue, final part "Conference on
Comput. Complex.
Eric Allender
2005 B conf
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
MFCS
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
2005 J jnl
The Directed Planar Reachability Problem
Electron. Colloquium Comput. Complex.
Eric Allender, Samir Datta, Sambuddha Roy
2005 — conf
The Directed Planar Reachability Problem.
FSTTCS
Eric Allender, Samir Datta, Sambuddha Roy
2005 A conf
Topology Inside NC¹.
CCC
Eric Allender, Samir Datta, Sambuddha Roy
2004 J jnl
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem
Electron. Colloquium Comput. Complex.
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
2004 J jnl
The complexity of planarity testing.
Inf. Comput.
Eric Allender, Meena Mahajan
2004 J jnl
Topology inside NC
Electron. Colloquium Comput. Complex.
Eric Allender, Samir Datta, Sambuddha Roy
2004 A conf
What Can be Efficiently Reduced to the K-Random Strings?
STACS
Eric Allender, Harry Buhrman, Michal Koucký
2004 J jnl
What Can be Efficiently Reduced to the Kolmogorov-Random Strings?
Electron. Colloquium Comput. Complex.
Eric Allender, Harry Buhrman, Michal Koucký
2003 J jnl
Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst.
Eric Allender, Vikraman Arvind, Meena Mahajan
2003 J jnl
Complexity of some arithmetic problems for binary polynomials.
Comput. Complex.
Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor E. Shparlinski
2003 A conf
Derandomization and Distinguishing Complexity.
CCC
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy
2003 C conf
NL-printable sets and Nondeterministic Kolmogorov Complexity.
WoLLIC
Eric Allender
2002 — conf
A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.
NIPS
Eric Allender, Sanjeev Arora, Michael J. Kearns, Cristopher Moore, Alexander Russell
2002 J jnl
Power from Random Strings
Electron. Colloquium Comput. Complex.
Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek
2002 A* conf
Power from Random Strings.
FOCS
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
2002 J jnl
Uniform constant-depth threshold circuits for division and iterated multiplication.
J. Comput. Syst. Sci.
William Hesse, Eric Allender, David A. Mix Barrington
2001 J jnl
A Lower Bound for Primality.
J. Comput. Syst. Sci.
Eric Allender, Michael E. Saks, Igor E. Shparlinski
2001 J jnl
Reducing the complexity of reductions.
Comput. Complex.
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
2001 — ch.
Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front.
Current Trends in Theoretical Computer Science
Eric Allender
2001 J jnl
The Division Breakthroughs.
Bull. EATCS
Eric Allender
2001 J jnl
Time-Space Tradeoffs in the Counting Hierarchy
Electron. Colloquium Comput. Complex.
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay
2001 A conf
Time-Space Tradeoffs in the Counting Hierarchy.
CCC
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay
2001 J jnl
Uniform Circuits for Division: Consequences and Problems
Electron. Colloquium Comput. Complex.
Eric Allender, David A. Mix Barrington, William Hesse
2001 A conf
Uniform Circuits for Division: Consequences and Problems.
CCC
Eric Allender, David A. Mix Barrington, William Hesse
2001 — conf
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity.
FSTTCS
Eric Allender
2000 J jnl
Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Chic. J. Theor. Comput. Sci.
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
2000 J jnl
Complexity of finite-horizon Markov decision process problems.
J. ACM
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
2000 J jnl
Making Nondeterminism Unambiguous.
SIAM J. Comput.
Klaus Reinhardt, Eric Allender
2000 J jnl
On TC
J. Comput. Syst. Sci.
Manindra Agrawal, Eric Allender, Samir Datta
2000 J jnl
Report on the annual summer meeting of the New Zealand mathematics research institute.
SIGACT News
Eric Allender
2000 A conf
The Complexity of Planarity Testing.
STACS
Eric Allender, Meena Mahajan
2000 J jnl
Uniform Circuits for Division: Consequences and Problems
Electron. Colloquium Comput. Complex.
Eric Allender, David A. Mix Barrington
1999 J jnl
A Lower Bound for Primality
Electron. Colloquium Comput. Complex.
Eric Allender, Igor E. Shparlinski, Michael E. Saks
1999 A conf
A Lower Bound for Primality.
CCC
Eric Allender, Michael E. Saks, Igor E. Shparlinski
1999 J jnl
Arithmetic Complexity, Kleene Closure, and Formal Power Series
Electron. Colloquium Comput. Complex.
Eric Allender, Vikraman Arvind, Meena Mahajan
1999 J jnl
Bounded Depth Arithmetic Circuits: Counting and Closure
Electron. Colloquium Comput. Complex.
Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999 A* conf
Bounded Depth Arithmetic Circuits: Counting and Closure.
ICALP
Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999 — ch.
Complexity Classes.
Algorithms and Theory of Computation Handbook
Eric Allender, Michael C. Loui, Kenneth W. Regan
1999 J jnl
Complexity of Finite-Horizon Markov Decision process Problems.
Universität Trier, Mathematik/Informatik, Forschungsbericht
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
1999 J jnl
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds.
J. Comput. Syst. Sci.
Eric Allender, Klaus Reinhardt, Shiyu Zhou
1999 — ch.
Other Complexity Classes and Measures.
Algorithms and Theory of Computation Handbook
Eric Allender, Michael C. Loui, Kenneth W. Regan
1999 — ch.
Reducibility and Completeness.
Algorithms and Theory of Computation Handbook
Eric Allender, Michael C. Loui, Kenneth W. Regan
1999 J jnl
The Complexity of Matrix Rank and Feasible Systems of Linear Equations.
Comput. Complex.
Eric Allender, Robert Beals, Mitsunori Ogihara
1999 J jnl
The Permanent Requires Large Uniform Threshold Circuits.
Chic. J. Theor. Comput. Sci.
Eric Allender
1998 J jnl
Characterizing Small Depth and Small Space Classes by Operators of Higher Types
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
1998 J jnl
Isolation, Matching, and Counting
Electron. Colloquium Comput. Complex.
Eric Allender, Klaus Reinhardt
1998 A conf
Isolation, Matching, and Counting.
CCC
Eric Allender, Klaus Reinhardt
1998 J jnl
News from the Isomorphism Front.
Bull. EATCS
Eric Allender
1998 J jnl
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds.
Theor. Comput. Sci.
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay
1998 J jnl
RUSPACE(log
Theory Comput. Syst.
Eric Allender, Klaus-Jörn Lange
1998 J jnl
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.
J. Comput. Syst. Sci.
Manindra Agrawal, Eric Allender, Steven Rudich
1998 J jnl
Uniform Inclusions in Nondeterministic Logspace
Electron. Colloquium Comput. Complex.
Eric Allender, Shiyu Zhou
1997 J jnl
A First-Order Isomorphism Theorem.
SIAM J. Comput.
Eric Allender, José L. Balcázar, Neil Immerman
1997 J jnl
Making Nondeterminism Unambiguous
Electron. Colloquium Comput. Complex.
Klaus Reinhardt, Eric Allender
1997 A* conf
Making Nondeterminism Unambiguous.
FOCS
Klaus Reinhardt, Eric Allender
1997 J jnl
Making computation count: arithmetic circuits in the nineties.
SIGACT News
Eric Allender
1997 A conf
On TC
CCC
Manindra Agrawal, Eric Allender, Samir Datta
1997 J jnl
On TC
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Eric Allender, Samir Datta
1997 A* conf
Reducing the Complexity of Reductions.
STOC
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
1997 B conf
The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes.
MFCS
Martin Mundhenk, Judy Goldsmith, Eric Allender
1996 J jnl
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy
Electron. Colloquium Comput. Complex.
Eric Allender
1996 Misc conf
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy (Extended Abstract).
COCOON
Eric Allender
1996 J jnl
An Isomorphism Theorem for Circuit Complexity
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Eric Allender
1996 A conf
An Isomorphism Theorem for Circuit Complexity.
CCC
Manindra Agrawal, Eric Allender
1996 — conf
Circuit Complexity before the Dawn of the New Millennium.
FSTTCS
Eric Allender
1996 J jnl
Relationships Among PL, #L, and the Determinant.
RAIRO Theor. Informatics Appl.
Eric Allender, Mitsunori Ogihara
1996 B conf
StUSPACE(log n) <= DSPACE(log²n / log log n).
ISAAC
Eric Allender, Klaus-Jörn Lange
1996 J jnl
StUSPACE(log n) is Contained in DSPACE((log
Electron. Colloquium Comput. Complex.
Eric Allender, Klaus-Jörn Lange
1996 A* conf
The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract).
STOC
Eric Allender, Robert Beals, Mitsunori Ogihara
1996 J jnl
The complexity of matrix rank and feasible systems of linear equations
Electron. Colloquium Comput. Complex.
Eric Allender, Robert Beals, Mitsunori Ogihara
1996 J jnl
The future of computational complexity theory: part II.
SIGACT News
Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich
1995 J jnl
Measure on P: Robustness of the Notion
Electron. Colloquium Comput. Complex.
Eric Allender, Martin Strauss
1995 B conf
Measure on P: Robustness of the Notion.
MFCS
Eric Allender, Martin Strauss
1995 J jnl
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Electron. Colloquium Comput. Complex.
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay
1994 J jnl
A Uniform Circuit Lower Bound for the Permanent.
SIAM J. Comput.
Eric Allender, Vivek Gore
1994 J jnl
Depth Reduction for Circuits of Unbounded Fan-In
Inf. Comput.
Eric Allender, Ulrich Hertrampf
1994 A* conf
Measure on Small Complexity Classes, with Applications for BPP
FOCS
Eric Allender, Martin Strauss
1994 J jnl
Measure on Small Complexity Classes, with Applications for BPP
Electron. Colloquium Comput. Complex.
Eric Allender, Martin Strauss
1994 — conf
Relationships Among PL, #L, and the Determinant.
SCT
Eric Allender, Mitsunori Ogihara
1993 A conf
A First-Order Isomorphism Theorem.
STACS
Eric Allender, José L. Balcázar, Neil Immerman
1993 J jnl
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.
Theor. Comput. Sci.
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
1993 — ch.
Counting Hierarchies: Polynomial Time and Constant Depth Circuits.
Current Trends in Theoretical Computer Science
Eric Allender, Klaus W. Wagner
1993 A* conf
Depth reduction for noncommutative arithmetic circuits.
STOC
Eric Allender, Jia Jiao
1993 J jnl
The Complexity of Computing Maximal Word Functions.
Comput. Complex.
Eric Allender, Danilo Bruschi, Giovanni Pighizzini
1992 J jnl
Lower Bounds for the Low Hierarchy.
J. ACM
Eric Allender, Lane A. Hemachandra
1992 J jnl
Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput.
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1991 J jnl
Limitations of the Upward Separation Technique.
Math. Syst. Theory
Eric Allender
1991 B conf
On Strong Separations from AC
FCT
Eric Allender, Vivek Gore
1991 — conf
Relating Equivalence and Reducibility to Sparse Sets.
SCT
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1991 J jnl
Rudimentary Reductions Revisited.
Inf. Process. Lett.
Eric Allender, Vivek Gore
1990 A conf
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.
STACS
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
1990 J jnl
Counting Hierarchies: Polynomial Time and Constant.
Bull. EATCS
Eric Allender, Klaus W. Wagner
1990 J jnl
Downward Translations of Equality.
Theor. Comput. Sci.
Eric Allender, Christopher B. Wilson
1990 J jnl
Kolmogorov Complexity and Degrees of Tally Sets
Inf. Comput.
Eric Allender, Osamu Watanabe
1990 — conf
On Strong Separations from AC.
Advances In Computational Complexity Theory
Eric Allender, Vivek Gore
1990 B conf
On the Power of Uniform Families of Constant Depth Treshold Circuits.
MFCS
Eric Allender, Ulrich Hertrampf
1990 — conf
Oracles versus Proof Techniques that Do Not Relativize.
SIGAL International Symposium on Algorithms
Eric Allender
1990 — conf
Width-Bounded Reducibility and Binary Search over Complexity Classes.
SCT
Eric Allender, Christopher B. Wilson
1989 A* conf
A Note on the Power of Threshold Circuits
FOCS
Eric Allender
1989 A* conf
Limitations of the Upward Separation Technique (Preliminary Version).
ICALP
Eric Allender
1989 A* conf
Lower Bounds for the Low Hierarchy (Extended Abstract).
ICALP
Eric Allender, Lane A. Hemachandra
1989 J jnl
P-uniform circuit complexity.
J. ACM
Eric Allender
1989 J jnl
Some Consequences of the Existence of Pseudorandom Generators.
J. Comput. Syst. Sci.
Eric Allender
1989 — conf
The Generalized Kolmogorov Complexity of Sets.
SCT
Eric Allender
1988 J jnl
Isomorphisms and 1-L Reductions.
J. Comput. Syst. Sci.
Eric Allender
1988 — conf
Kolmogorov complexity and degrees of tally sets.
SCT
Eric Allender, Osamu Watanabe
1988 A* conf
On Generating Solved Instances of Computational Problems.
CRYPTO
Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra
1988 J jnl
P-Printable Sets.
SIAM J. Comput.
Eric Allender, Roy S. Rubinstein
1987 A* conf
Some Consequences of the Existence of Pseudorandom Generators
STOC
Eric Allender
1987 — conf
Some consequences of the existence of pseudorandom generators.
SCT
Eric Allender
1986 A* conf
Characterizations on PUNC and Precomputation (Extended Abstract).
ICALP
Eric Allender
1986 — conf
Isomorphisms and 1-L Reductions.
SCT
Eric Allender
1986 — conf
The Complexity of Sparse Sets in P.
SCT
Eric Allender
1985 J jnl
Improved Lower Bounds for the Cycle Detection Problem.
Theor. Comput. Sci.
Eric Allender, Maria M. Klawe
1985 J jnl
On the number of cycles possible in digraphs with large girth.
Discret. Appl. Math.
Eric Allender