Eric Allender | Academic Influence

Eric Allender's AcademicInfluence.com Rankings

Eric Allender

Computer Science

#4574

World Rank

#4826

Historical Rank

#1470

USA Rank

Database

#7800

World Rank

#8113

Historical Rank

#985

USA Rank

computer-science Degrees

Download Badge

Computer Science

Eric Allender's Degrees

PhD Computer Science University of California, Berkeley
Masters Computer Science University of California, Berkeley
Bachelors Computer Science University of California, Berkeley

Similar Degrees You Can Earn

Why Is Eric Allender Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Eric Warren Allender is an American computer scientist active in the field of computational complexity theory. In 2006 he was inducted as a Fellow of the Association for Computing Machinery. He is currently a professor at Rutgers University where he chaired the Department of Computer Science from 2006 until 2009.

(See a Problem?)

Eric Allender's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Complexity Theory (1997) (250)
Uniform constant-depth threshold circuits for division and iterated multiplication (2002) (194)
On the complexity of numerical analysis (2006) (173)
Complexity of finite-horizon Markov decision process problems (2000) (171)
A note on the power of threshold circuits (1989) (158)
Power from random strings (2002) (143)
Relationships among PL, #L, and the determinant (1994) (135)
Making nondeterminism unambiguous (1997) (131)
P-Printable Sets (1988) (109)
The complexity of matrix rank and feasible systems of linear equations (1996) (95)
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds (1996) (94)
The complexity of satisfiability problems: Refining Schaefer's theorem (2005) (90)
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds (1999) (87)
The Complexity of Sparse Sets in P (1986) (87)
Amplifying Lower Bounds by Means of Self-Reducibility (2008) (85)
Measure on small complexity classes, with applications for BPP (1994) (68)
On TC0, AC0, and Arithmetic Circuits (2000) (63)
A First-Order Isomorphism Theorem (1993) (62)
The Permanent Requires Large Uniform Threshold Circuits (1999) (62)
The complexity of planarity testing (2000) (61)
Zero knowledge and circuit minimization (2014) (55)
P-uniform circuit complexity (1989) (54)
A Uniform Circuit Lower Bound for the Permanent (1994) (54)
Planar and Grid Graph Reachability Problems (2009) (53)
Arithmetic Circuits and Counting Complexity Classes (2004) (53)
Lower bounds for the low hierarchy (1992) (53)
Reducing the complexity of reductions (1997) (53)
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table (2008) (53)
Circuit Complexity before the Dawn of the New Millennium (1996) (52)
On the Power of Uniform Families of Constant Depth Treshold Circuits (1990) (50)
Contributions to the Study of Resource-bounded Measure (1994) (49)
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems (2019) (47)
Depth Reduction for Circuits of Unbounded Fan-In (1994) (46)
What can be efficiently reduced to the Kolmogorov-random strings? (2006) (46)
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity (2001) (45)
Some consequences of the existence of pseudorandom generators (1987) (45)
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem (1998) (43)
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (2009) (43)
Kolmogorov complexity and degrees of tally sets (1988) (43)
Relating equivalence and reducibility to sparse sets (1991) (42)
The Complexity of Complexity (2017) (41)
Isomorphisms and 1-L Reductions (1986) (36)
The Minimum Oracle Circuit Size Problem (2016) (36)
Counting Hierarchies: Polynomial Time and Constant Depth Circuits (1993) (35)
Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory (1992) (33)
Limits on the computational power of random strings (2011) (33)
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time (1993) (32)
The Directed Planar Reachability Problem (2005) (30)
Time-space tradeoffs in the counting hierarchy (2001) (29)
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table (2005) (28)
Minimum Circuit Size, Graph Isomorphism, and Related Problems (2017) (28)
Rudimentary Reductions Revisited (1991) (28)
Grid graph reachability problems (2006) (28)
On Generating Solved Instances of Computational Problems (1988) (27)
Bounded Depth Arithmetic Circuits: Counting and Closure (1999) (27)
Arithmetic Complexity, Kleene Closure, and Formal Power Series (1997) (27)
Complexity Classes (2010) (26)
On the power of algebraic branching programs of width two (2011) (24)
Making computation count: arithmetic circuits in the nineties (1997) (22)
Oracles versus Proof Techniques that Do Not Relativize (1990) (22)
Width-Parametrized SAT: Time--Space Tradeoffs (2011) (22)
A lower bound for primality (1999) (22)
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997) (22)
Depth reduction for noncommutative arithmetic circuits (1993) (21)
Uniform circuits for division: consequences and problems (2001) (20)
The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes (1997) (20)
Minimizing DNF formulas and AC/sup 0//sub d/ circuits given a truth table (2006) (19)
Measure on P: Robustness of the Notion (1995) (19)
The Division Breakthroughs (2001) (17)
Reachability Problems: An Update (2007) (17)
On strong separations from ACo (1991) (17)
Reductions to the Set of Random Strings: The Resource-Bounded Case (2014) (16)
Isolation, matching, and counting (1998) (16)
The New Complexity Landscape Around Circuit Minimization (2020) (16)
A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics (2002) (16)
On Strong Separations from AC (1993) (16)
Curiouser and Curiouser: The Link between Incompressibility and Complexity (2012) (16)
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs (2014) (15)
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic (2012) (15)
Downward Translations of Equality (1990) (15)
Derandomization and distinguishing complexity (2003) (15)
Graph Isomorphism and Circuit Size (2015) (15)
RUSPACE(log n) $\subseteq$ DSPACE(log2n/log log n) (1998) (15)
Reducibility and Completeness (2010) (14)
Width-bounded reducibility and binary search over complexity classes (1990) (14)
Complexity of Regular Functions (2015) (12)
StUSPACE(log n) <= DSPACE(log²n / log log n) (1996) (11)
On traversal sequences, exploration sequences and completeness of kolmogorov random strings (2003) (11)
NL-printable sets and Nondeterministic Kolmogorov Complexity (2003) (11)
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time (1990) (10)
An isomorphism theorem for circuit complexity (1996) (10)
Uniform derandomization from pathetic lower bounds (2010) (10)
Counting Hierarchies: Polynomial Time and Constant (1990) (10)
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds (2008) (9)
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy (Extended Abstract) (1996) (9)
On TC/sup 0/, AC/sup 0/, and arithmetic circuits (1997) (9)
The Non-hardness of Approximating Circuit Size (2019) (9)
Ruspacelog N Dspacelog 2 N= Log Log N (1997) (9)
Topology inside NC1 (2004) (8)
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity (2022) (8)
On the number of cycles possible in digraphs with large girth (1985) (8)
One-Way Functions and a Conditional Variant of MKTP (2021) (8)
Kolmogorov complexity and derandomization (2004) (8)
A Status Report on the P Versus NP Question (2009) (7)
Improved Lower Bounds for the Cycle Detection Problem (1985) (7)
What Can be Efficiently Reduced to the K-Random Strings? (2004) (6)
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization (2021) (6)
Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front (2001) (6)
The complexity of computing maximal word functions (1991) (6)
Limitations of the upward separation technique (1991) (6)
Dual VP Classes (2015) (5)
Corrigendum to "Uniform constant-depth threshold circuits for division and iterated multiplication" [J. Comput. System Sci. 65(4) (2002) 695-716] (2014) (5)
Lower Bounds for the Low Hierarchy (Extended Abstract) (1989) (5)
Complexity of some arithmetic problems for binary polynomials (2004) (5)
Topology inside NC/sup 1/ (2005) (5)
News from the Isomorphism Front (1998) (5)
Better Complexity Bounds for Cost Register Automata (2017) (5)
The future of computational complexity theory: part II (1996) (5)
Characterizing Small Depth and Small Space Classes by Operators of Higher Type (2000) (4)
Reductions to the set of random strings: the resource-bounded case (2012) (4)
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata (2010) (4)
Topology inside NC 1 (2004) (4)
StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n) (1996) (4)
Investigations Concerning the Structure of Complete Sets (2014) (4)
Characterizations of PUNC and precomputation (1986) (4)
Uniform Inclusions in Nondeterministic Logspace (1998) (3)
The Computational Complexity Column Recent Advances towards Proving P = Bpp (1998) (3)
The generalized Kolmogorov complexity of sets (1989) (3)
One-way Functions and Partial MCSP (2021) (3)
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds (2012) (3)
New Surprises from Self-Reducibility (3)
Avoiding Simplicity is Complex (2010) (3)
Depth-First Search in Directed Graphs, Revisited (2020) (3)
A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity (2020) (2)
Better Complexity Bounds for Cost Register Automata (2018) (2)
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs (2023) (2)
RUSPACE(log n) is contained in DSPACE(log^2 n / loglog n) (1997) (2)
\structure and Complexity" (1996) (2)
Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions (2010) (2)
On Strong Separations from AC0 (Extended Abstract) (1991) (2)
Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds (2008) (2)
Book Review: Complexity Theory Retrospective II. Edited by: Lane A. Hemaspaandra and Alan L. Selman (Springer Verlag) (1998) (2)
The Complexity of Unobservable Nite-horizon Markov Decision Processes (1996) (2)
Limitations of the Upward Separation Technique (Preliminary Version) (1989) (2)
The Minimum Oracle Circuit Size Problem (2016) (1)
The Complexity of Satisabilit y Problems: Rening Schaefer's Theorem (2004) (1)
Arithmetic circuit classes over Zm (2015) (1)
Kolmogorov Complexity Characterizes Statistical Zero Knowledge (2022) (1)
Avoiding Simplicity is Complex (2011) (1)
Better Complexity Bounds for Cost Register Machines (2017) (1)
StUSPA CE(log n) ⊆ DSPA CE(log 2 n / log log n) (1996) (1)
Relating Equivalence and Reducibility to Sparse Sets (Extended Abstract) (1991) (1)
Planarity, Exclusivity, and Unambiguity (2019) (1)
Complexity theoretic aspects of planar restrictions and obliviousness (2006) (1)
23 : 2 The Non-Hardness of Approximating Circuit Size (2019) (1)
Depth Reduction for Noncommutative Arithmetic Circuits (extended Abstract) (1993) (1)
On circuit complexity classes and iterated matrix multiplication (2012) (1)
Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds? (2008) (1)
Review: Jose Luis Balcazar, Joseph Diaz, Joaquim Gabarro, Structural Complexity I; Jose Luis Balcazar, Josep Diaz, Joaquim Gabarro, Structural Complexity II (1994) (1)
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity (2020) (1)
1 Lower Bounds for the Low Hierarchy ! (2008) (1)
Other Complexity Classes and Measures Chapter 29 of the forthcoming CRC Handbook on Algorithms and Theory of Computation (2007) (1)
Dual VP Classes (2016) (1)
Report on the annual summer meeting of the New Zealand mathematics research institute (2000) (0)
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II (2014) (0)
Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007) (2009) (0)
Special issue, final part “Conference on Computational Complexity 2004 ” Guest Editor’s foreword (2005) (0)
Computational Complexity Theory (2009) (0)
University of Azores, Ponta Delgada, Azores, Portugal June 30–July 4, 2010 (2011) (0)
The Computational Complexity Column Progress in Descriptive Complexity (1998) (0)
Reductions to the set of random strings Allender (2014) (0)
Bounded depth arithmetic circuits (2004) (0)
Weakly Growing Context-sensitive Grammars Chicago Journal of Theoretical Computer Science (1996) (0)
C C ] 2 6 O ct 2 01 7 Minimum Circuit Size , Graph Isomorphism , and Related Problems ∗ (2018) (0)
On the power of algebraic branching programs of width two (2015) (0)
Pseudorandom Sources and Oracles for BPP (2008) (0)
Conference Committee (1987) (0)
Algebraic methods for proving lower bounds in circuit complexity (0)
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series (2013) (0)
Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (1995) (0)
The Permanent Requires Large Uniform Threshold Circuits 1 (1997) (0)
Kolmogorov Complexity Characterizes Statistical 1 Zero Knowledge 2 (2022) (0)
Randomness as Circuit Complexity (and the Connection to Pseudorandomness) (2011) (0)
XX : 2 Better Complexity Bounds for Cost Register Machines (2017) (0)
News from ACM transactions on Computation theory: New Editor-in-Chief (2017) (0)
Characterizations on PUNC and Precomputation (Extended Abstract) (1986) (0)
Reducibility and Completeness Chapter 28 of the forthcoming CRC Handbook on Algorithms and Theory of Computation (2006) (0)
Complexity Classes Chapter 27 of the forthcoming CRC Handbook on Algorithms and Theory of Computation (2007) (0)
Other Complexity Classes and Measures (2010) (0)
Syntactic Separation of Subset Satisfiability Problems (2019) (0)
Editor's ForewordEDITOR'S FOREWORD (1997) (0)
On the Complexity of Some Arithmetic Problems over IF 2 [ T ] (0)
Pspace-hard Functions Checkable Debate Systems and Approximation Algorithms for Pspace (2007) (0)
Algorithm Design and Analysis Techniques (2009) (0)
The Non-hardness of Approximating Circuit Size (2020) (0)
16 : 2 Syntactic Separation of Subset Satisfiability Problems (2019) (0)
Special issue “Conference on Computational Complexity 2004” Guest Editor’s foreword (2005) (0)
Widt h-Bounded Reducibility and Binary Search over Complexity Classes (Extended Abstract) (1990) (0)
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series (2013) (0)
Robustness for Space-Bounded Statistical Zero Knowledge (2022) (0)
Depth-first search in directed planar graphs, revisited (2022) (0)
Session details: Session 6B (2007) (0)
Introduction to the special issue on innovations in theoretical computer science 2012 (2013) (0)
A note on Graph Automorphism and Smart Reductions (2018) (0)

This paper list is powered by the following services:

Other Resources About Eric Allender

en.wikipedia.org

What Schools Are Affiliated With Eric Allender?

Eric Allender is affiliated with the following schools:

Image Attributions

Image Source for Eric Allender