Eric Allender

According to our database1, Eric Allender authored at least 140 papers between 1985 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2006, "For contributions to computational complexity theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Depth-First Search in Directed Graphs, Revisited.
Electronic Colloquium on Computational Complexity (ECCC), 2020

The New Complexity Landscape around Circuit Minimization.
Electronic Colloquium on Computational Complexity (ECCC), 2020

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity.
Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

2019
Better Complexity Bounds for Cost Register Automata.
Theory Comput. Syst., 2019

Complexity of regular functions.
J. Comput. Syst. Sci., 2019

Planarity, Exclusivity, and Unambiguity.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Syntactic Separation of Subset Satisfiability Problems.
Proceedings of the Approximation, 2019

2018
The Non-Hardness of Approximating Circuit Size.
Electronic Colloquium on Computational Complexity (ECCC), 2018

2017
Better Complexity Bounds for Cost Register Machines.
Electronic Colloquium on Computational Complexity (ECCC), 2017

New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Minimum Circuit Size, Graph Isomorphism, and Related Problems.
Electronic Colloquium on Computational Complexity (ECCC), 2017

News from ACM transactions on Computation theory: New Editor-in-Chief.
Bull. EATCS, 2017

The Minimum Oracle Circuit Size Problem.
Comput. Complex., 2017

Dual VP Classes.
Comput. Complex., 2017

The Complexity of Complexity.
Proceedings of the Computability and Complexity, 2017

2016
On the power of algebraic branching programs of width two.
Comput. Complex., 2016

2015
Graph Isomorphism and Circuit Size.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Arithmetic circuit classes over Zm.
Electronic Colloquium on Computational Complexity (ECCC), 2015

2014
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II.
ACM Trans. Comput. Theory, 2014

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.
Theory Comput., 2014

Width-Parametrized SAT: Time--Space Tradeoffs.
Theory Comput., 2014

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

Zero Knowledge and Circuit Minimization.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Complexity Theory.
Proceedings of the Computing Handbook, 2014

2013
Introduction to the special issue on innovations in theoretical computer science 2012.
ACM Trans. Comput. Theory, 2013

Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst., 2013

Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Chicago J. Theor. Comput. Sci., 2013

2012
Avoiding Simplicity is Complex.
Theory Comput. Syst., 2012

Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Reductions to the set of random strings: the resource-bounded case.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Curiouser and Curiouser: The Link between Incompressibility and Complexity.
Proceedings of the How the World Computes, 2012

2011
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.
J. Comput. Syst. Sci., 2011

2010
Amplifying lower bounds by means of self-reducibility.
J. ACM, 2010

Limits on the Computational Power of Random Strings.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Uniform Derandomization from Pathetic Lower Bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Avoiding Simplicity is Complex.
Electronic Colloquium on Computational Complexity (ECCC), 2010

2009
Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007).
SIAM J. Comput., 2009

Planar and Grid Graph Reachability Problems.
Theory Comput. Syst., 2009

The complexity of satisfiability problems: Refining Schaefer's theorem.
J. Comput. Syst. Sci., 2009

A Status Report on the P Versus NP Question.
Adv. Comput., 2009

2008
Computational Complexity Theory.
Proceedings of the Wiley Encyclopedia of Computer Science and Engineering, 2008

Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.
SIAM J. Comput., 2008

Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds.
Proceedings of the 10th International Workshop on Descriptional Complexity of Formal Systems, 2008

Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds.
Proceedings of the Computer Science, 2008

Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds?
Proceedings of the Theory of Computing 2008. Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), 2008

2007
Reachability Problems: An Update.
Proceedings of the Computation and Logic in the Real World, 2007

2006
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005
Grid Graph Reachability Problems
Electronic Colloquium on Computational Complexity (ECCC), 2005

The Directed Planar Reachability Problem
Electronic Colloquium on Computational Complexity (ECCC), 2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electronic Colloquium on Computational Complexity (ECCC), 2005

On the Complexity of Numerical Analysis
Electronic Colloquium on Computational Complexity (ECCC), 2005

Special issue, final part "Conference on Computational Complexity 2004 " Guest Editor's foreword.
Comput. Complex., 2005

Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword.
Comput. Complex., 2005

Topology Inside NC¹.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
The complexity of planarity testing.
Inf. Comput., 2004

Topology inside NC1
Electronic Colloquium on Computational Complexity (ECCC), 2004

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?
Electronic Colloquium on Computational Complexity (ECCC), 2004

What Can be Efficiently Reduced to the K-Random Strings?
Proceedings of the STACS 2004, 2004

2003
NL-printable sets and Nondeterministic Kolmogorov Complexity.
Electron. Notes Theor. Comput. Sci., 2003

Complexity of some arithmetic problems for binary polynomials.
Comput. Complex., 2003

Derandomization and Distinguishing Complexity.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Uniform constant-depth threshold circuits for division and iterated multiplication.
J. Comput. Syst. Sci., 2002

Power from Random Strings
Electronic Colloquium on Computational Complexity (ECCC), 2002

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.
Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

2001
A Lower Bound for Primality.
J. Comput. Syst. Sci., 2001

Time-Space Tradeoffs in the Counting Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 2001

Uniform Circuits for Division: Consequences and Problems
Electronic Colloquium on Computational Complexity (ECCC), 2001

The Division Breakthroughs.
Bull. EATCS, 2001

Reducing the complexity of reductions.
Comput. Complex., 2001

When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity.
Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front.
Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000
Report on the annual summer meeting of the New Zealand mathematics research institute.
SIGACT News, 2000

On TC0, AC0, and Arithmetic Circuits.
J. Comput. Syst. Sci., 2000

Uniform Circuits for Division: Consequences and Problems
Electronic Colloquium on Computational Complexity (ECCC), 2000

Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Chicago J. Theor. Comput. Sci., 2000

1999
Complexity of Finite-Horizon Markov Decision process Problems.
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1999

Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds.
J. Comput. Syst. Sci., 1999

Bounded Depth Arithmetic Circuits: Counting and Closure
Electronic Colloquium on Computational Complexity (ECCC), 1999

Arithmetic Complexity, Kleene Closure, and Formal Power Series
Electronic Colloquium on Computational Complexity (ECCC), 1999

The Permanent Requires Large Uniform Threshold Circuits.
Chicago J. Theor. Comput. Sci., 1999

The Complexity of Matrix Rank and Feasible Systems of Linear Equations.
Comput. Complex., 1999

Other Complexity Classes and Measures.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

Reducibility and Completeness.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

Complexity Classes.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds.
Theor. Comput. Sci., 1998

RUSPACE(log n) $\subseteq$ DSPACE (log2 n / log log n).
Theory Comput. Syst., 1998

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.
J. Comput. Syst. Sci., 1998

Characterizing Small Depth and Small Space Classes by Operators of Higher Types
Electronic Colloquium on Computational Complexity (ECCC), 1998

Uniform Inclusions in Nondeterministic Logspace
Electronic Colloquium on Computational Complexity (ECCC), 1998

Isolation, Matching, and Counting
Electronic Colloquium on Computational Complexity (ECCC), 1998

News from the Isomorphism Front.
Bull. EATCS, 1998

1997
Making computation count: arithmetic circuits in the nineties.
SIGACT News, 1997

A First-Order Isomorphism Theorem.
SIAM J. Comput., 1997

Making Nondeterminism Unambiguous
Electronic Colloquium on Computational Complexity (ECCC), 1997

The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1996
The future of computational complexity theory: part II.
SIGACT News, 1996

Relationships Among PL, #L, and the Determinant.
RAIRO Theor. Informatics Appl., 1996

StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n)
Electronic Colloquium on Computational Complexity (ECCC), 1996

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 1996

An Isomorphism Theorem for Circuit Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

StUSPACE(log n) <= DSPACE(log²n / log log n).
Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Circuit Complexity before the Dawn of the New Millennium.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy (Extended Abstract).
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
Measure on P: Robustness of the Notion
Electronic Colloquium on Computational Complexity (ECCC), 1995

1994
Depth Reduction for Circuits of Unbounded Fan-In
Inf. Comput., August, 1994

A Uniform Circuit Lower Bound for the Permanent.
SIAM J. Comput., 1994

Measure on Small Complexity Classes, with Applications for BPP
Electronic Colloquium on Computational Complexity (ECCC), 1994

1993
Counting Hierarchies: Polynomial Time and Constant Depth Circuits.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.
Theor. Comput. Sci., 1993

The Complexity of Computing Maximal Word Functions.
Comput. Complex., 1993

Depth reduction for noncommutative arithmetic circuits.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput., 1992

Lower Bounds for the Low Hierarchy.
J. ACM, 1992

1991
Limitations of the Upward Separation Technique.
Math. Syst. Theory, 1991

Rudimentary Reductions Revisited.
Inf. Process. Lett., 1991

On Strong Separations from AC0 (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990
Kolmogorov Complexity and Degrees of Tally Sets
Inf. Comput., June, 1990

Downward Translations of Equality.
Theor. Comput. Sci., 1990

Counting Hierarchies: Polynomial Time and Constant.
Bull. EATCS, 1990

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.
Proceedings of the STACS 90, 1990

Oracles versus Proof Techniques that Do Not Relativize.
Proceedings of the Algorithms, 1990

On the Power of Uniform Families of Constant Depth Treshold Circuits.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

On Strong Separations from AC.
Proceedings of the Advances In Computational Complexity Theory, 1990

Width-Bounded Reducibility and Binary Search over Complexity Classes.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Some Consequences of the Existence of Pseudorandom Generators.
J. Comput. Syst. Sci., 1989

P-uniform circuit complexity.
J. ACM, 1989

Lower Bounds for the Low Hierarchy (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Limitations of the Upward Separation Technique (Preliminary Version).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Note on the Power of Threshold Circuits
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

The Generalized Kolmogorov Complexity of Sets.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
P-Printable Sets.
SIAM J. Comput., 1988

Isomorphisms and 1-L Reductions.
J. Comput. Syst. Sci., 1988

On Generating Solved Instances of Computational Problems.
Proceedings of the Advances in Cryptology, 1988

1986
Characterizations on PUNC and Precomputation (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

The Complexity of Sparse Sets in P.
Proceedings of the Structure in Complexity Theory, 1986

1985
Improved Lower Bounds for the Cycle Detection Problem.
Theor. Comput. Sci., 1985

On the number of cycles possible in digraphs with large girth.
Discret. Appl. Math., 1985


  Loading...