Eric Allender

According to our database, Eric Allender authored at least 149 papers between 1985 and 2023.

Collaborative distances:

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

2023

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

Eric Allender

SIGACT News, March, 2023

Cryptographic hardness under projections for time-bounded Kolmogorov complexity.

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

Theor. Comput. Sci., 2023

2022

Kolmogorov Complexity Characterizes Statistical Zero Knowledge.

Eric Allender, Shuichi Hirahara, Harsha Tirumala

Electron. Colloquium Comput. Complex., 2022

Robustness for Space-Bounded Statistical Zero Knowledge.

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

Electron. Colloquium Comput. Complex., 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

Depth-first search in directed planar graphs, revisited.

Eric Allender, Archit Chauhan, Samir Datta

Acta Informatica, 2022

2021

One-way Functions and Partial MCSP.

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

Electron. Colloquium Comput. Complex., 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 Garvia Bosshard, Amulya Musipatla

Electron. Colloquium Comput. Complex., 2020

The New Complexity Landscape around Circuit Minimization.

Eric Allender

Electron. Colloquium Comput. Complex., 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

Better Complexity Bounds for Cost Register Automata.

Eric Allender, Andreas Krebs, Pierre McKenzie

Theory Comput. Syst., 2019

Complexity of regular functions.

Eric Allender, Ian Mertz

J. Comput. Syst. Sci., 2019

Planarity, Exclusivity, and Unambiguity.

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

Electron. Colloquium Comput. Complex., 2019

Syntactic Separation of Subset Satisfiability Problems.

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

Proceedings of the Approximation, 2019

2018

The Non-Hardness of Approximating Circuit Size.

Eric Allender, Rahul Ilango, Neekon Vafa

Electron. Colloquium Comput. Complex., 2018

2017

Better Complexity Bounds for Cost Register Machines.

Eric Allender, Andreas Krebs, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2017

New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems.

Eric Allender, Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2017

Minimum Circuit Size, Graph Isomorphism, and Related Problems.

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

Electron. Colloquium Comput. Complex., 2017

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

Eric Allender

Bull. EATCS, 2017

The Minimum Oracle Circuit Size Problem.

Eric Allender, Dhiraj Holden, Valentine Kabanets

Comput. Complex., 2017

Dual VP Classes.

Eric Allender, Anna Gál, Ian Mertz

Comput. Complex., 2017

The Complexity of Complexity.

Eric Allender

Proceedings of the Computability and Complexity, 2017

2016

On the power of algebraic branching programs of width two.

Eric Allender, Fengming Wang

Comput. Complex., 2016

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

2014

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

Eric Allender, Shafi Goldwasser

ACM Trans. Comput. Theory, 2014

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

Eric Allender, Klaus-Jörn Lange

Theory Comput., 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

Electron. Colloquium Comput. Complex., 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

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

Eric Allender, Nikhil Balaji, Samir Datta

Electron. Colloquium Comput. Complex., 2013

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

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

Chic. J. Theor. Comput. Sci., 2013

2012

Avoiding Simplicity is Complex.

Eric Allender, Holger Spakowski

Theory Comput. Syst., 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

Electron. Colloquium Comput. Complex., 2012

Curiouser and Curiouser: The Link between Incompressibility and Complexity.

Eric Allender

Proceedings of the How the World Computes, 2012

2011

The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.

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

J. Comput. Syst. Sci., 2011

2010

Amplifying lower bounds by means of self-reducibility.

Eric Allender, Michal Koucký

J. ACM, 2010

Limits on the Computational Power of Random Strings.

Eric Allender, Luke Friedman, William I. Gasarch

Electron. Colloquium Comput. Complex., 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

Uniform Derandomization from Pathetic Lower Bounds.

Eric Allender, Vikraman Arvind, Fengming Wang

Electron. Colloquium Comput. Complex., 2010

Avoiding Simplicity is Complex.

Eric Allender

Electron. Colloquium Comput. Complex., 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 complexity of satisfiability problems: Refining Schaefer's theorem.

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

J. Comput. Syst. Sci., 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

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

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

2005

Grid Graph Reachability Problems

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

Electron. Colloquium Comput. Complex., 2005

The Directed Planar Reachability Problem

Eric Allender, Samir Datta, Sambuddha Roy

Electron. Colloquium Comput. Complex., 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

On the Complexity of Numerical Analysis

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

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

Topology Inside NC¹.

Eric Allender, Samir Datta, Sambuddha Roy

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

2004

The complexity of planarity testing.

Eric Allender, Meena Mahajan

Inf. Comput., 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

NL-printable sets and Nondeterministic Kolmogorov Complexity.

Eric Allender

Proceedings of the 10th Workshop on Logic, Language, Information and Computation, 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

Power from Random Strings

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

Electron. Colloquium Comput. Complex., 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

2001

A Lower Bound for Primality.

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

J. Comput. Syst. Sci., 2001

Time-Space Tradeoffs in the Counting Hierarchy

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

Electron. Colloquium Comput. Complex., 2001

Uniform Circuits for Division: Consequences and Problems

Eric Allender, David A. Mix Barrington, William Hesse

Electron. Colloquium Comput. Complex., 2001

The Division Breakthroughs.

Eric Allender

Bull. EATCS, 2001

Reducing the complexity of reductions.

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

Comput. Complex., 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

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

On TC⁰, AC⁰, and Arithmetic Circuits.

Manindra Agrawal, Eric Allender, Samir Datta

J. Comput. Syst. Sci., 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

1999

Complexity of Finite-Horizon Markov Decision process Problems.

Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1999

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

Eric Allender, Klaus Reinhardt, Shiyu Zhou

J. Comput. Syst. Sci., 1999

Bounded Depth Arithmetic Circuits: Counting and Closure

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

Electron. Colloquium Comput. Complex., 1999

Arithmetic Complexity, Kleene Closure, and Formal Power Series

Eric Allender, Vikraman Arvind, Meena Mahajan

Electron. Colloquium Comput. Complex., 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

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

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

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

Theor. Comput. Sci., 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

Isolation, Matching, and Counting

Eric Allender, Klaus Reinhardt

Electron. Colloquium Comput. Complex., 1998

News from the Isomorphism Front.

Eric Allender

Bull. EATCS, 1998

1997

Making computation count: arithmetic circuits in the nineties.

Eric Allender

SIGACT News, 1997

A First-Order Isomorphism Theorem.

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

SIAM J. Comput., 1997

Making Nondeterminism Unambiguous

Klaus Reinhardt, Eric Allender

Electron. Colloquium Comput. Complex., 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

1996

The future of computational complexity theory: part II.

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

SIGACT News, 1996

Relationships Among PL, #L, and the Determinant.

Eric Allender, Mitsunori Ogihara

RAIRO Theor. Informatics Appl., 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

An Isomorphism Theorem for Circuit Complexity

Manindra Agrawal, 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

1995

Measure on P: Robustness of the Notion

Eric Allender, Martin Strauss

Electron. Colloquium Comput. Complex., 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

Electron. Colloquium Comput. Complex., 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

1992

Relating Equivalence and Reducibility to Sparse Sets.

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

SIAM J. Comput., 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

1990

Kolmogorov Complexity and Degrees of Tally Sets

Eric Allender, Osamu Watanabe

Inf. Comput., June, 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

Some Consequences of the Existence of Pseudorandom Generators.

Eric Allender

J. Comput. Syst. Sci., 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

Isomorphisms and 1-L Reductions.

Eric Allender

J. Comput. Syst. Sci., 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

1986

Characterizations on PUNC and Precomputation (Extended Abstract).

Eric Allender

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 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