Eric Allender

According to our database, Eric Allender authored at least 150 papers between 1985 and 2026.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2026

Comment on "SAT requires exhaustive search".

Eric Allender, Ryan Williams

Frontiers Comput. Sci., January, 2026

2023

Guest Column: Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!

Eric Allender

SIGACT News, March, 2023

Kolmogorov Complexity Characterizes Statistical Zero Knowledge.

Eric Allender, Shuichi Hirahara, Harsha Tirumala

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Robustness for Space-Bounded Statistical Zero Knowledge.

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang

Proceedings of the Approximation, 2023

2022

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs.

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

Electron. Colloquium Comput. Complex., 2022

2021

One-way Functions and Partial MCSP.

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2021

Depth-First Search in Directed Planar Graphs, Revisited.

Eric Allender, Archit Chauhan, Samir Datta

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity.

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

One-Way Functions and a Conditional Variant of MKTP.

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

Depth-First Search in Directed Graphs, Revisited.

Eric Allender, Archit Chauhan, Samir Datta

Electron. Colloquium Comput. Complex., 2020

A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity.

Eric Allender, Azucena Garvía Bosshard, Amulya Musipatla

Electron. Colloquium Comput. Complex., 2020

The New Complexity Landscape Around Circuit Minimization.

Eric Allender

Proceedings of the Language and Automata Theory and Applications, 2020

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity.

Eric Allender

Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

2019

Planarity, Exclusivity, and Unambiguity.

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

Electron. Colloquium Comput. Complex., 2019

The Non-hardness of Approximating Circuit Size.

Eric Allender, Rahul Ilango, Neekon Vafa

Proceedings of the Computer Science - Theory and Applications, 2019

Syntactic Separation of Subset Satisfiability Problems.

Eric Allender, Martin Farach-Colton, Meng-Tsung Tsai

Proceedings of the Approximation, 2019

2018

Minimum Circuit Size, Graph Isomorphism, and Related Problems.

Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Better Complexity Bounds for Cost Register Machines.

Eric Allender, Andreas Krebs, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2017

News from ACM transactions on Computation theory: New Editor-in-Chief.

Eric Allender

Bull. EATCS, 2017

Better Complexity Bounds for Cost Register Automata.

Eric Allender, Andreas Krebs, Pierre McKenzie

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.

Eric Allender, Shuichi Hirahara

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

The Complexity of Complexity.

Eric Allender

Proceedings of the Computability and Complexity, 2017

2015

Graph Isomorphism and Circuit Size.

Eric Allender, Joshua A. Grochow, Cristopher Moore

Electron. Colloquium Comput. Complex., 2015

Arithmetic circuit classes over Zm.

Eric Allender, Asa Goodwillie

Electron. Colloquium Comput. Complex., 2015

The Minimum Oracle Circuit Size Problem.

Eric Allender, Dhiraj Holden, Valentine Kabanets

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Dual VP Classes.

Eric Allender, Anna Gál, Ian Mertz

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Complexity of Regular Functions.

Eric Allender, Ian Mertz

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.

Eric Allender, Shafi Goldwasser

ACM Trans. Comput. Theory, 2014

Width-Parametrized SAT: Time--Space Tradeoffs.

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang

Theory Comput., 2014

Corrigendum to "Uniform constant-depth threshold circuits for division and iterated multiplication" [J. Comput. System Sci. 65(4) (2002) 695-716].

William Hesse, Eric Allender, David A. Mix Barrington

J. Comput. Syst. Sci., 2014

Zero Knowledge and Circuit Minimization.

Eric Allender, Bireswar Das

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.

Eric Allender, Nikhil Balaji, Samir Datta

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Complexity Theory.

Eric Allender, Michael C. Loui, Kenneth W. Regan

Proceedings of the Computing Handbook, 2014

2013

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

Eric Allender, Shafi Goldwasser

ACM Trans. Comput. Theory, 2013

Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.

Eric Allender, Vikraman Arvind, Meena Mahajan

Theory Comput. Syst., 2013

2012

Avoiding Simplicity is Complex.

Eric Allender, Holger Spakowski

Theory Comput. Syst., 2012

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.

Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2012

Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds.

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang

Electron. Colloquium Comput. Complex., 2012

Reductions to the Set of Random Strings: The Resource-Bounded Case.

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Curiouser and Curiouser: The Link between Incompressibility and Complexity.

Eric Allender

Proceedings of the How the World Computes, 2012

2011

On the Power of Algebraic Branching Programs of Width Two.

Eric Allender, Fengming Wang

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Limits on the Computational Power of Random Strings.

Eric Allender, Luke Friedman, William I. Gasarch

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.

Eric Allender, Luke Friedman, William I. Gasarch

Electron. Colloquium Comput. Complex., 2010

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.

Eric Allender, Klaus-Jörn Lange

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

Avoiding Simplicity Is Complex.

Eric Allender

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

Uniform Derandomization from Pathetic Lower Bounds.

Eric Allender, Vikraman Arvind, Fengming Wang

Proceedings of the Approximation, 2010

2009

Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007).

Eric Allender, Vladlen Koltun, Maxim Sviridenko

SIAM J. Comput., 2009

Planar and Grid Graph Reachability Problems.

Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Theory Comput. Syst., 2009

The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory.

Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy

Electron. Colloquium Comput. Complex., 2009

A Status Report on the P Versus NP Question.

Eric Allender

Adv. Comput., 2009

2008

Computational Complexity Theory.

Eric Allender

Proceedings of the Wiley Encyclopedia of Computer Science and Engineering, 2008

Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table.

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks

SIAM J. Comput., 2008

Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds.

Eric Allender

Proceedings of the 10th International Workshop on Descriptional Complexity of Formal Systems, 2008

Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds.

Eric Allender

Proceedings of the Computer Science, 2008

Amplifying Lower Bounds by Means of Self-Reducibility.

Eric Allender, Michal Koucký

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?

Eric Allender

Proceedings of the Theory of Computing 2008. Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), 2008

2007

Reachability Problems: An Update.

Eric Allender

Proceedings of the Computation and Logic in the Real World, 2007

2006

NL-printable sets and nondeterministic Kolmogorov complexity.

Eric Allender

Theor. Comput. Sci., 2006

Minimizing DNF Formulas and AC⁰_d Circuits Given a Truth Table.

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks

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

On the Complexity of Numerical Analysis.

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

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

Grid Graph Reachability Problems.

Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

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

2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks

Electron. Colloquium Comput. Complex., 2005

Special issue, final part "Conference on <i>Computational Complexity</i> 2004 " Guest Editor's foreword.

Eric Allender

Comput. Complex., 2005

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

Eric Allender

Comput. Complex., 2005

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

The Directed Planar Reachability Problem.

Eric Allender, Samir Datta, Sambuddha Roy

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

Topology Inside NC¹.

Eric Allender, Samir Datta, Sambuddha Roy

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Topology inside NC¹

Eric Allender, Samir Datta, Sambuddha Roy

Electron. Colloquium Comput. Complex., 2004

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

Eric Allender, Harry Buhrman, Michal Koucký

Electron. Colloquium Comput. Complex., 2004

What Can be Efficiently Reduced to the K-Random Strings?

Eric Allender, Harry Buhrman, Michal Koucký

Proceedings of the STACS 2004, 2004

2003

Arithmetic Complexity, Kleene Closure, and Formal Power Series.

Eric Allender, Vikraman Arvind, Meena Mahajan

Theory Comput. Syst., 2003

Complexity of some arithmetic problems for binary polynomials.

Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor E. Shparlinski

Comput. Complex., 2003

Derandomization and Distinguishing Complexity.

Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Uniform constant-depth threshold circuits for division and iterated multiplication.

William Hesse, Eric Allender, David A. Mix Barrington

J. Comput. Syst. Sci., 2002

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.

Eric Allender, Sanjeev Arora, Michael J. Kearns, Cristopher Moore, Alexander Russell

Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

Power from Random Strings.

Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

The Division Breakthroughs.

Eric Allender

Bull. EATCS, 2001

When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity.

Eric Allender

Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Time-Space Tradeoffs in the Counting Hierarchy.

Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Uniform Circuits for Division: Consequences and Problems.

Eric Allender, David A. Mix Barrington, William Hesse

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front.

Eric Allender

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

Report on the annual summer meeting of the New Zealand mathematics research institute.

Eric Allender

SIGACT News, 2000

Complexity of finite-horizon Markov decision process problems.

Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender

J. ACM, 2000

Uniform Circuits for Division: Consequences and Problems

Eric Allender, David A. Mix Barrington

Electron. Colloquium Comput. Complex., 2000

Characterizing Small Depth and Small Space Classes by Operators of Higher Type.

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Chic. J. Theor. Comput. Sci., 2000

The Complexity of Planarity Testing.

Eric Allender, Meena Mahajan

Proceedings of the STACS 2000, 2000

1999

Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds.

Eric Allender, Klaus Reinhardt, Shiyu Zhou

J. Comput. Syst. Sci., 1999

The Permanent Requires Large Uniform Threshold Circuits.

Eric Allender

Chic. J. Theor. Comput. Sci., 1999

The Complexity of Matrix Rank and Feasible Systems of Linear Equations.

Eric Allender, Robert Beals, Mitsunori Ogihara

Comput. Complex., 1999

Bounded Depth Arithmetic Circuits: Counting and Closure.

Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh

Proceedings of the Automata, 1999

A Lower Bound for Primality.

Eric Allender, Michael E. Saks, Igor E. Shparlinski

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Other Complexity Classes and Measures.

Eric Allender, Michael C. Loui, Kenneth W. Regan

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

Reducibility and Completeness.

Eric Allender, Michael C. Loui, Kenneth W. Regan

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

Complexity Classes.

Eric Allender, Michael C. Loui, Kenneth W. Regan

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

1998

RUSPACE(log <i>n</i>) $\subseteq$ DSPACE (log² <i>n</i> / log log <i>n</i>).

Eric Allender, Klaus-Jörn Lange

Theory Comput. Syst., 1998

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.

Manindra Agrawal, Eric Allender, Steven Rudich

J. Comput. Syst. Sci., 1998

Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Electron. Colloquium Comput. Complex., 1998

Uniform Inclusions in Nondeterministic Logspace

Eric Allender, Shiyu Zhou

Electron. Colloquium Comput. Complex., 1998

News from the Isomorphism Front.

Eric Allender

Bull. EATCS, 1998

Isolation, Matching, and Counting.

Eric Allender, Klaus Reinhardt

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Making computation count: arithmetic circuits in the nineties.

Eric Allender

SIGACT News, 1997

Reducing the Complexity of Reductions.

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

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.

Martin Mundhenk, Judy Goldsmith, Eric Allender

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Making Nondeterminism Unambiguous.

Klaus Reinhardt, Eric Allender

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

On TC⁰, AC⁰, and Arithmetic Circuits.

Manindra Agrawal, Eric Allender, Samir Datta

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

The future of computational complexity theory: part II.

Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich

SIGACT News, 1996

StUSPACE(log n) is Contained in DSPACE((log²n)/loglog n)

Eric Allender, Klaus-Jörn Lange

Electron. Colloquium Comput. Complex., 1996

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Eric Allender

Electron. Colloquium Comput. Complex., 1996

The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract).

Eric Allender, Robert Beals, Mitsunori Ogihara

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

StUSPACE(log n) <= DSPACE(log²n / log log n).

Eric Allender, Klaus-Jörn Lange

Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Circuit Complexity before the Dawn of the New Millennium.

Eric Allender

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).

Eric Allender

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

An Isomorphism Theorem for Circuit Complexity.

Manindra Agrawal, Eric Allender

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay

Electron. Colloquium Comput. Complex., 1995

Measure on P: Robustness of the Notion.

Eric Allender, Martin Strauss

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994

Depth Reduction for Circuits of Unbounded Fan-In

Eric Allender, Ulrich Hertrampf

Inf. Comput., August, 1994

A Uniform Circuit Lower Bound for the Permanent.

Eric Allender, Vivek Gore

SIAM J. Comput., 1994

Measure on Small Complexity Classes, with Applications for BPP

Eric Allender, Martin Strauss

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Relationships Among PL, #L, and the Determinant.

Eric Allender, Mitsunori Ogihara

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.

Eric Allender, Klaus W. Wagner

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Almost-Everywhere Complexity Hierarchies for Nondeterministic Time.

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Theor. Comput. Sci., 1993

The Complexity of Computing Maximal Word Functions.

Eric Allender, Danilo Bruschi, Giovanni Pighizzini

Comput. Complex., 1993

Depth reduction for noncommutative arithmetic circuits.

Eric Allender, Jia Jiao

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

A First-Order Isomorphism Theorem.

Eric Allender, José L. Balcázar, Neil Immerman

Proceedings of the STACS 93, 1993

1992

Lower Bounds for the Low Hierarchy.

Eric Allender, Lane A. Hemachandra

J. ACM, 1992

1991

Limitations of the Upward Separation Technique.

Eric Allender

Math. Syst. Theory, 1991

Rudimentary Reductions Revisited.

Eric Allender, Vivek Gore

Inf. Process. Lett., 1991

On Strong Separations from AC⁰ (Extended Abstract).

Eric Allender, Vivek Gore

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

Relating Equivalence and Reducibility to Sparse Sets.

Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Downward Translations of Equality.

Eric Allender, Christopher B. Wilson

Theor. Comput. Sci., 1990

Counting Hierarchies: Polynomial Time and Constant.

Eric Allender, Klaus W. Wagner

Bull. EATCS, 1990

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time.

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Proceedings of the STACS 90, 1990

Oracles versus Proof Techniques that Do Not Relativize.

Eric Allender

Proceedings of the Algorithms, 1990

On the Power of Uniform Families of Constant Depth Treshold Circuits.

Eric Allender, Ulrich Hertrampf

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

On Strong Separations from AC.

Eric Allender, Vivek Gore

Proceedings of the Advances In Computational Complexity Theory, 1990

Width-Bounded Reducibility and Binary Search over Complexity Classes.

Eric Allender, Christopher B. Wilson

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

P-uniform circuit complexity.

Eric Allender

J. ACM, 1989

Lower Bounds for the Low Hierarchy (Extended Abstract).

Eric Allender, Lane A. Hemachandra

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Limitations of the Upward Separation Technique (Preliminary Version).

Eric Allender

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Note on the Power of Threshold Circuits

Eric Allender

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.

Eric Allender

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

P-Printable Sets.

Eric Allender, Roy S. Rubinstein

SIAM J. Comput., 1988

On Generating Solved Instances of Computational Problems.

Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra

Proceedings of the Advances in Cryptology, 1988

Kolmogorov complexity and degrees of tally sets.

Eric Allender, Osamu Watanabe

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Some consequences of the existence of pseudorandom generators.

Eric Allender

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

Characterizations on PUNC and Precomputation (Extended Abstract).

Eric Allender

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

Isomorphisms and 1-L Reductions.

Eric Allender

Proceedings of the Structure in Complexity Theory, 1986

The Complexity of Sparse Sets in P.

Eric Allender

Proceedings of the Structure in Complexity Theory, 1986

1985

Improved Lower Bounds for the Cycle Detection Problem.

Eric Allender, Maria M. Klawe

Theor. Comput. Sci., 1985

On the number of cycles possible in digraphs with large girth.

Eric Allender

Discret. Appl. Math., 1985