Eric Allender

According to our database1, Eric Allender authored at least 159 papers between 1985 and 2019.

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

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

The Non-hardness of Approximating Circuit Size.
Proceedings of the Computer Science - Theory and Applications, 2019

2018
Minimum Circuit Size, Graph Isomorphism, and Related Problems.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 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

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

Better Complexity Bounds for Cost Register Automata.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

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

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

The Minimum Oracle Circuit Size Problem.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Dual VP Classes.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Complexity of Regular Functions.
Proceedings of the Language and Automata Theory and Applications, 2015

2014
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II.
TOCT, 2014

Width-Parametrized SAT: Time--Space Tradeoffs.
Theory of Computing, 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.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Complexity Theory.
Proceedings of the Computing Handbook, 2014

2013
Introduction to the special issue on innovations in theoretical computer science 2012.
TOCT, 2013

Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst., 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

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Proceedings of the Mathematical Foundations of Computer Science 2012, 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

On the Power of Algebraic Branching Programs of Width Two.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Limits on the Computational Power of Random Strings.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

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

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

Avoiding Simplicity Is Complex.
Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

Uniform Derandomization from Pathetic Lower Bounds.
Proceedings of the Approximation, 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 Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory.
Electronic Colloquium on Computational Complexity (ECCC), 2009

A Status Report on the P Versus NP Question.
Advances in Computers, 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

Amplifying Lower Bounds by Means of Self-Reducibility.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 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
NL-printable sets and nondeterministic Kolmogorov complexity.
Theor. Comput. Sci., 2006

What can be efficiently reduced to the Kolmogorov-random strings?
Ann. Pure Appl. Logic, 2006

On the Complexity of Numerical Analysis.
Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

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

On the Complexity of Numerical Analysis.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Grid Graph Reachability Problems.
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.
Computational Complexity, 2005

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

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

The Directed Planar Reachability Problem.
Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

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

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

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem
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
Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst., 2003

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

Complexity of some arithmetic problems for binary polynomials.
Computational Complexity, 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

Power from Random Strings.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

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.
Bulletin of the EATCS, 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

Time-Space Tradeoffs in the Counting Hierarchy.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Uniform Circuits for Division: Consequences and Problems.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 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

Complexity of finite-horizon Markov decision process problems.
J. ACM, 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

The Complexity of Planarity Testing.
Proceedings of the STACS 2000, 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

A Lower Bound for Primality
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.
Computational Complexity, 1999

Bounded Depth Arithmetic Circuits: Counting and Closure.
Proceedings of the Automata, 1999

A Lower Bound for Primality.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 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.
Bulletin of the EATCS, 1998

Isolation, Matching, and Counting.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

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

On TC0, AC0, and Arithmetic Circuits
Electronic Colloquium on Computational Complexity (ECCC), 1997

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

Reducing the Complexity of Reductions.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

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

Making Nondeterminism Unambiguous.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

On TC0, AC0, and Arithmetic Circuits.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

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

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

The complexity of matrix rank and feasible systems of linear equations
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

An Isomorphism Theorem for Circuit Complexity.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Electronic Colloquium on Computational Complexity (ECCC), 1995

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

Measure on P: Robustness of the Notion.
Proceedings of the Mathematical Foundations of Computer Science 1995, 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
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Relationships Among PL, #L, and the Determinant.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 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.
Computational Complexity, 1993

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

A First-Order Isomorphism Theorem.
Proceedings of the STACS 93, 1993

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

1991
Limitations of the Upward Separation Technique.
Mathematical Systems 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

Relating Equivalence and Reducibility to Sparse Sets.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 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.
Bulletin of the 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
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

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

Kolmogorov complexity and degrees of tally sets.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Some Consequences of the Existence of Pseudorandom Generators
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Some consequences of the existence of pseudorandom generators.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

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

Isomorphisms and 1-L Reductions.
Proceedings of the Structure in Complexity Theory, 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.
Discrete Applied Mathematics, 1985


  Loading...