default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDEric Allender
Person information
- affiliation: Rutgers University, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j77]Eric Allender, Nikhil Balaji
, Samir Datta, Rameshwar Pratap:
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs. Comput. 12(2): 145-173 (2023)- [j76]Eric Allender:
Guest Column: Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes! SIGACT News 54(1): 63-81 (2023) - [j75]Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic hardness under projections for time-bounded Kolmogorov complexity. Theor. Comput. Sci. 940(Part): 206-224 (2023) - [c80]Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang:
Robustness for Space-Bounded Statistical Zero Knowledge. APPROX/RANDOM 2023: 56:1-56:21 - [c79]Eric Allender, Shuichi Hirahara, Harsha Tirumala:
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. ITCS 2023: 3:1-3:19 - 2022
- [j74]Eric Allender, Archit Chauhan, Samir Datta:
Depth-first search in directed planar graphs, revisited. Acta Informatica 59(4): 289-319 (2022) - [i61]Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap:
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs. Electron. Colloquium Comput. Complex. TR22 (2022) - [i60]Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang:
Robustness for Space-Bounded Statistical Zero Knowledge. Electron. Colloquium Comput. Complex. TR22 (2022) - [i59]Eric Allender, Shuichi Hirahara, Harsha Tirumala:
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j73]Eric Allender, Rahul Ilango, Neekon Vafa:
The Non-hardness of Approximating Circuit Size. Theory Comput. Syst. 65(3): 559-578 (2021) - [c78]Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich:
One-Way Functions and a Conditional Variant of MKTP. FSTTCS 2021: 7:1-7:19 - [c77]Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. ISAAC 2021: 54:1-54:17 - [c76]Eric Allender, Archit Chauhan, Samir Datta:
Depth-First Search in Directed Planar Graphs, Revisited. MFCS 2021: 7:1-7:22 - [i58]Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich:
One-way Functions and Partial MCSP. Electron. Colloquium Comput. Complex. TR21 (2021) - [i57]Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c75]Eric Allender:
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity. Complexity and Approximation 2020: 8-18 - [c74]Eric Allender:
The New Complexity Landscape Around Circuit Minimization. LATA 2020: 3-16 - [i56]Eric Allender:
The New Complexity Landscape around Circuit Minimization. Electron. Colloquium Comput. Complex. TR20 (2020) - [i55]Eric Allender, Azucena Garvía Bosshard, Amulya Musipatla:
A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR20 (2020) - [i54]Eric Allender, Archit Chauhan, Samir Datta:
Depth-First Search in Directed Graphs, Revisited. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j72]Eric Allender, Ian Mertz:
Complexity of regular functions. J. Comput. Syst. Sci. 104: 5-16 (2019) - [j71]Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Automata. Theory Comput. Syst. 63(3): 367-385 (2019) - [j70]Eric Allender, Shuichi Hirahara:
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. ACM Trans. Comput. Theory 11(4): 27:1-27:27 (2019) - [c73]Eric Allender, Martin Farach-Colton, Meng-Tsung Tsai:
Syntactic Separation of Subset Satisfiability Problems. APPROX-RANDOM 2019: 16:1-16:23 - [c72]Eric Allender, Rahul Ilango, Neekon Vafa:
The Non-hardness of Approximating Circuit Size. CSR 2019: 13-24 - [i53]Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee:
Planarity, Exclusivity, and Unambiguity. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j69]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. SIAM J. Comput. 47(4): 1339-1372 (2018) - [c71]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. ITCS 2018: 20:1-20:20 - [i52]Eric Allender, Rahul Ilango, Neekon Vafa:
The Non-Hardness of Approximating Circuit Size. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j68]Eric Allender, Dhiraj Holden, Valentine Kabanets:
The Minimum Oracle Circuit Size Problem. Comput. Complex. 26(2): 469-496 (2017) - [j67]Eric Allender, Anna Gál, Ian Mertz:
Dual VP Classes. Comput. Complex. 26(3): 583-625 (2017) - [j66]Eric Allender:
News from ACM transactions on Computation theory: New Editor-in-Chief. Bull. EATCS 122 (2017) - [j65]Eric Allender, Bireswar Das:
Zero knowledge and circuit minimization. Inf. Comput. 256: 2-8 (2017) - [c70]Eric Allender:
The Complexity of Complexity. Computability and Complexity 2017: 79-94 - [c69]Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Automata. MFCS 2017: 24:1-24:14 - [c68]Eric Allender, Shuichi Hirahara:
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. MFCS 2017: 54:1-54:14 - [i51]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. CoRR abs/1710.09806 (2017) - [i50]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i49]Eric Allender, Shuichi Hirahara:
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i48]Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Machines. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j64]Eric Allender, Fengming Wang:
On the power of algebraic branching programs of width two. Comput. Complex. 25(1): 217-253 (2016) - 2015
- [c67]Eric Allender, Ian Mertz:
Complexity of Regular Functions. LATA 2015: 449-460 - [c66]Eric Allender, Anna Gál, Ian Mertz:
Dual VP Classes. MFCS (2) 2015: 14-25 - [c65]Eric Allender, Dhiraj Holden, Valentine Kabanets:
The Minimum Oracle Circuit Size Problem. STACS 2015: 21-33 - [i47]Eric Allender, Joshua A. Grochow, Cristopher Moore:
Graph Isomorphism and Circuit Size. CoRR abs/1511.08189 (2015) - [i46]Eric Allender, Asa Goodwillie:
Arithmetic circuit classes over Zm. Electron. Colloquium Comput. Complex. TR15 (2015) - [i45]Eric Allender, Joshua A. Grochow, Cristopher Moore:
Graph Isomorphism and Circuit Size. Electron. Colloquium Comput. Complex. TR15 (2015) - [i44]Eric Allender, Ian Mertz:
Complexity of Regular Functions. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j63]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: The resource-bounded case. Log. Methods Comput. Sci. 10(3) (2014) - [j62]William Hesse, Eric Allender, David A. Mix Barrington:
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. 80(2): 496-497 (2014) - [j61]Eric Allender, Klaus-Jörn Lange:
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Theory Comput. 10: 199-215 (2014) - [j60]Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang:
Width-Parametrized SAT: Time--Space Tradeoffs. Theory Comput. 10: 297-339 (2014) - [j59]Eric Allender, Shafi Goldwasser:
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II. ACM Trans. Comput. Theory 6(3): 10:1 (2014) - [c64]Eric Allender, Nikhil Balaji, Samir Datta:
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. MFCS (2) 2014: 13-24 - [c63]Eric Allender, Bireswar Das:
Zero Knowledge and Circuit Minimization. MFCS (2) 2014: 25-32 - [p7]Eric Allender, Michael C. Loui, Kenneth W. Regan:
Complexity Theory. Computing Handbook, 3rd ed. (1) 2014: 7: 1-33 - [i43]Eric Allender, Bireswar Das:
Zero Knowledge and Circuit Minimization. Electron. Colloquium Comput. Complex. TR14 (2014) - [i42]Eric Allender, Anna Gál, Ian Mertz:
Dual VP Classes. Electron. Colloquium Comput. Complex. TR14 (2014) - [i41]Eric Allender, Dhiraj Holden, Valentine Kabanets:
The Minimum Oracle Circuit Size Problem. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j58]Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret:
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. Chic. J. Theor. Comput. Sci. 2013 (2013) - [j57]Eric Allender, Luke Friedman, William I. Gasarch:
Limits on the computational power of random strings. Inf. Comput. 222: 80-92 (2013) - [j56]Eric Allender, Vikraman Arvind, Meena Mahajan:
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series. Theory Comput. Syst. 53(3): 503-506 (2013) - [j55]Eric Allender, Shafi Goldwasser:
Introduction to the special issue on innovations in theoretical computer science 2012. ACM Trans. Comput. Theory 5(3): 8:1 (2013) - [i40]Eric Allender, Nikhil Balaji, Samir Datta:
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j54]Eric Allender, Holger Spakowski:
Avoiding Simplicity is Complex. Theory Comput. Syst. 51(3): 282-296 (2012) - [c62]Eric Allender:
Curiouser and Curiouser: The Link between Incompressibility and Complexity. CiE 2012: 11-16 - [c61]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS 2012: 88-99 - [i39]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: the resource-bounded case. Electron. Colloquium Comput. Complex. TR12 (2012) - [i38]Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang:
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. Electron. Colloquium Comput. Complex. TR12 (2012) - [i37]Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret:
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j53]Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77(1): 14-40 (2011) - [c60]Eric Allender, Luke Friedman, William I. Gasarch:
Limits on the Computational Power of Random Strings. ICALP (1) 2011: 293-304 - [c59]Eric Allender, Fengming Wang:
On the Power of Algebraic Branching Programs of Width Two. ICALP (1) 2011: 736-747 - [i36]Eric Allender, Fengming Wang:
On the power of algebraic branching programs of width two. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j52]Eric Allender, Michal Koucký:
Amplifying lower bounds by means of self-reducibility. J. ACM 57(3): 14:1-14:36 (2010) - [c58]Eric Allender, Vikraman Arvind, Fengming Wang:
Uniform Derandomization from Pathetic Lower Bounds. APPROX-RANDOM 2010: 380-393 - [c57]Eric Allender:
Avoiding Simplicity Is Complex. CiE 2010: 1-10 - [c56]Eric Allender, Klaus-Jörn Lange:
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. CCC 2010: 172-180 - [i35]Eric Allender:
Avoiding Simplicity is Complex. Electron. Colloquium Comput. Complex. TR10 (2010) - [i34]Eric Allender, Vikraman Arvind, Fengming Wang:
Uniform Derandomization from Pathetic Lower Bounds. Electron. Colloquium Comput. Complex. TR10 (2010) - [i33]Eric Allender, Luke Friedman, William I. Gasarch:
Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions. Electron. Colloquium Comput. Complex. TR10 (2010) - [i32]Eric Allender, Luke Friedman, William I. Gasarch:
Limits on the Computational Power of Random Strings. Electron. Colloquium Comput. Complex. TR10 (2010) - [i31]Eric Allender, Klaus-Jörn Lange:
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j51]Eric Allender:
A Status Report on the P Versus NP Question. Adv. Comput. 77: 117-147 (2009) - [j50]Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
The complexity of satisfiability problems: Refining Schaefer's theorem. J. Comput. Syst. Sci. 75(4): 245-254 (2009) - [j49]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009) - [j48]Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. SIAM J. Comput. 38(5): 1987-2006 (2009) - [j47]Eric Allender, Vladlen Koltun, Maxim Sviridenko:
Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007). SIAM J. Comput. 39(3): 978 (2009) - [i30]Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j46]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput. 38(1): 63-84 (2008) - [c55]Eric Allender:
Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds? CATS 2008: 3 - [c54]Eric Allender, Michal Koucký:
Amplifying Lower Bounds by Means of Self-Reducibility. CCC 2008: 31-40 - [c53]Eric Allender:
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds. CSR 2008: 3-10 - [c52]Eric Allender:
Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds. DCFS 2008: 7-13 - [p6]Eric Allender:
Computational Complexity Theory. Wiley Encyclopedia of Computer Science and Engineering 2008 - [i29]Eric Allender, Michal Koucký:
Amplifying Lower Bounds by Means of Self-Reducibility. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c51]Eric Allender:
Reachability Problems: An Update. CiE 2007: 25-27 - 2006
- [j45]Eric Allender, Harry Buhrman, Michal Koucký:
What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Log. 138(1-3): 2-19 (2006) - [j44]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006) - [j43]Eric Allender:
NL-printable sets and nondeterministic Kolmogorov complexity. Theor. Comput. Sci. 355(2): 127-138 (2006) - [c50]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. CCC 2006: 237-251 - [c49]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. CCC 2006: 299-313 - [c48]Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. CCC 2006: 331-339 - [i28]Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. Complexity of Boolean Functions 2006 - 2005
- [j42]Eric Allender:
Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword. Comput. Complex. 14(2): 89 (2005) - [j41]Eric Allender:
Special issue, final part "Conference on Computational Complexity 2004 " Guest Editor's foreword. Comput. Complex. 14(3): 185 (2005) - [c47]Eric Allender, Samir Datta, Sambuddha Roy:
Topology Inside NC¹. CCC 2005: 298-307 - [c46]Eric Allender, Samir Datta, Sambuddha Roy:
The Directed Planar Reachability Problem. FSTTCS 2005: 238-249 - [c45]Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. MFCS 2005: 71-82 - [i27]Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. Electron. Colloquium Comput. Complex. TR05 (2005) - [i26]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electron. Colloquium Comput. Complex. TR05 (2005) - [i25]Eric Allender, Samir Datta, Sambuddha Roy:
The Directed Planar Reachability Problem. Electron. Colloquium Comput. Complex. TR05 (2005) - [i24]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j40]Eric Allender, Meena Mahajan:
The complexity of planarity testing. Inf. Comput. 189(1): 117-134 (2004) - [c44]Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the K-Random Strings? STACS 2004: 584-595 - [i23]Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electron. Colloquium Comput. Complex. TR04 (2004) - [i22]Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. Electron. Colloquium Comput. Complex. TR04 (2004) - [i21]Eric Allender, Samir Datta, Sambuddha Roy:
Topology inside NC1. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j39]Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor E. Shparlinski:
Complexity of some arithmetic problems for binary polynomials. Comput. Complex. 12(1-2): 23-47 (2003) - [j38]Eric Allender, Vikraman Arvind, Meena Mahajan:
Arithmetic Complexity, Kleene Closure, and Formal Power Series. Theory Comput. Syst. 36(4): 303-328 (2003) - [c43]Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
Derandomization and Distinguishing Complexity. CCC 2003: 209-220 - [c42]Eric Allender:
NL-printable sets and Nondeterministic Kolmogorov Complexity. WoLLIC 2003: 1-15 - 2002
- [j37]William Hesse, Eric Allender, David A. Mix Barrington:
Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4): 695-716 (2002) - [c41]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings. FOCS 2002: 669-678 - [c40]Eric Allender, Sanjeev Arora, Michael J. Kearns, Cristopher Moore, Alexander Russell:
A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics. NIPS 2002: 431-437 - [i20]Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek:
Power from Random Strings. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j36]Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the complexity of reductions. Comput. Complex. 10(2): 117-138 (2001) - [j35]Eric Allender:
The Division Breakthroughs. Bull. EATCS 74: 61-77 (2001) - [j34]Eric Allender, Michael E. Saks, Igor E. Shparlinski:
A Lower Bound for Primality. J. Comput. Syst. Sci. 62(2): 356-366 (2001) - [c39]Eric Allender, David A. Mix Barrington, William Hesse:
Uniform Circuits for Division: Consequences and Problems. CCC 2001: 150-159 - [c38]Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay:
Time-Space Tradeoffs in the Counting Hierarchy. CCC 2001: 295-302 - [c37]Eric Allender:
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity. FSTTCS 2001: 1-15 - [p5]Eric Allender:
Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front. Current Trends in Theoretical Computer Science 2001: 25-41 - [i19]Eric Allender, David A. Mix Barrington, William Hesse:
Uniform Circuits for Division: Consequences and Problems. Electron. Colloquium Comput. Complex. TR01 (2001) - [i18]Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay:
Time-Space Tradeoffs in the Counting Hierarchy. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j33]Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Type. Chic. J. Theor. Comput. Sci. 2000 (2000) - [j32]Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender:
Complexity of finite-horizon Markov decision process problems. J. ACM 47(4): 681-720 (2000) - [j31]Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits. J. Comput. Syst. Sci. 60(2): 395-421 (2000) - [j30]Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous. SIAM J. Comput. 29(4): 1118-1131 (2000) - [j29]Eric Allender:
Report on the annual summer meeting of the New Zealand mathematics research institute. SIGACT News 31(2): 60-61 (2000) - [c36]Eric Allender, Meena Mahajan:
The Complexity of Planarity Testing. STACS 2000: 87-98 - [i17]Eric Allender, David A. Mix Barrington:
Uniform Circuits for Division: Consequences and Problems. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j28]Eric Allender, Robert Beals, Mitsunori Ogihara:
The Complexity of Matrix Rank and Feasible Systems of Linear Equations. Comput. Complex. 8(2): 99-126 (1999) - [j27]Eric Allender:
The Permanent Requires Large Uniform Threshold Circuits. Chic. J. Theor. Comput. Sci. 1999 (1999) - [j26]Eric Allender, Klaus Reinhardt, Shiyu Zhou:
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds. J. Comput. Syst. Sci. 59(2): 164-181 (1999) - [c35]Eric Allender, Michael E. Saks, Igor E. Shparlinski:
A Lower Bound for Primality. CCC 1999: 10-14 - [c34]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158 - [p4]Eric Allender, Michael C. Loui, Kenneth W. Regan:
Complexity Classes. Algorithms and Theory of Computation Handbook 1999 - [p3]Eric Allender, Michael C. Loui, Kenneth W. Regan:
Reducibility and Completeness. Algorithms and Theory of Computation Handbook 1999 - [p2]Eric Allender, Michael C. Loui, Kenneth W. Regan:
Other Complexity Classes and Measures. Algorithms and Theory of Computation Handbook 1999 - [i16]Eric Allender, Vikraman Arvind, Meena Mahajan:
Arithmetic Complexity, Kleene Closure, and Formal Power Series. Electron. Colloquium Comput. Complex. TR99 (1999) - [i15]Eric Allender, Igor E. Shparlinski, Michael E. Saks:
A Lower Bound for Primality. Electron. Colloquium Comput. Complex. TR99 (1999) - [i14]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure. Electron. Colloquium Comput. Complex. TR99 (1999) - [i13]Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender:
Complexity of Finite-Horizon Markov Decision process Problems. Universität Trier, Mathematik/Informatik, Forschungsbericht 99-25 (1999) - 1998
- [j25]Eric Allender:
News from the Isomorphism Front. Bull. EATCS 66: 73 (1998) - [j24]Manindra Agrawal, Eric Allender, Steven Rudich:
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. J. Comput. Syst. Sci. 57(2): 127-143 (1998) - [j23]Eric Allender, Klaus-Jörn Lange:
RUSPACE(log n) $\subseteq$ DSPACE (log2 n / log log n). Theory Comput. Syst. 31(5): 539-550 (1998) - [j22]Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay:
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theor. Comput. Sci. 209(1-2): 47-86 (1998) - [c33]Eric Allender, Klaus Reinhardt:
Isolation, Matching, and Counting. CCC 1998: 92-100 - [i12]Eric Allender, Klaus Reinhardt:
Isolation, Matching, and Counting. Electron. Colloquium Comput. Complex. TR98 (1998) - [i11]Eric Allender, Shiyu Zhou:
Uniform Inclusions in Nondeterministic Logspace. Electron. Colloquium Comput. Complex. TR98 (1998) - [i10]Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Types. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j21]Eric Allender, José L. Balcázar, Neil Immerman:
A First-Order Isomorphism Theorem. SIAM J. Comput. 26(2): 557-567 (1997) - [j20]Eric Allender:
Making computation count: arithmetic circuits in the nineties. SIGACT News 28(4): 2-15 (1997) - [c32]Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits. CCC 1997: 134-148 - [c31]Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous. FOCS 1997: 244-253 - [c30]Martin Mundhenk, Judy Goldsmith, Eric Allender:
The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. MFCS 1997: 129-138 - [c29]Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the Complexity of Reductions. STOC 1997: 730-738 - [i9]Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous. Electron. Colloquium Comput. Complex. TR97 (1997) - [i8]Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j19]Eric Allender, Mitsunori Ogihara:
Relationships Among PL, #L, and the Determinant. RAIRO Theor. Informatics Appl. 30(1): 1-21 (1996) - [j18]Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich:
The future of computational complexity theory: part II. SIGACT News 27(4): 3-7 (1996) - [c28]Manindra Agrawal, Eric Allender:
An Isomorphism Theorem for Circuit Complexity. CCC 1996: 2-11 - [c27]Eric Allender:
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy (Extended Abstract). COCOON 1996: 127-135 - [c26]Eric Allender:
Circuit Complexity before the Dawn of the New Millennium. FSTTCS 1996: 1-18 - [c25]Eric Allender, Klaus-Jörn Lange:
StUSPACE(log n) <= DSPACE(log²n / log log n). ISAAC 1996: 193-202 - [c24]Eric Allender, Robert Beals, Mitsunori Ogihara:
The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract). STOC 1996: 161-167 - [i7]Manindra Agrawal, Eric Allender:
An Isomorphism Theorem for Circuit Complexity. Electron. Colloquium Comput. Complex. TR96 (1996) - [i6]Eric Allender:
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy. Electron. Colloquium Comput. Complex. TR96 (1996) - [i5]Eric Allender, Robert Beals, Mitsunori Ogihara:
The complexity of matrix rank and feasible systems of linear equations. Electron. Colloquium Comput. Complex. TR96 (1996) - [i4]Eric Allender, Klaus-Jörn Lange:
StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n). Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [c23]Eric Allender, Martin Strauss:
Measure on P: Robustness of the Notion. MFCS 1995: 129-138 - [i3]Eric Allender, Martin Strauss:
Measure on P: Robustness of the Notion. Electron. Colloquium Comput. Complex. TR95 (1995) - [i2]Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay:
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [j17]Eric Allender, Ulrich Hertrampf:
Depth Reduction for Circuits of Unbounded Fan-In. Inf. Comput. 112(2): 217-238 (1994) - [j16]Eric Allender, Vivek Gore:
A Uniform Circuit Lower Bound for the Permanent. SIAM J. Comput. 23(5): 1026-1049 (1994) - [c22]Eric Allender, Mitsunori Ogihara:
Relationships Among PL, #L, and the Determinant. SCT 1994: 267-278 - [c21]Eric Allender, Martin Strauss:
Measure on Small Complexity Classes, with Applications for BPP. FOCS 1994: 807-818 - [i1]Eric Allender, Martin Strauss:
Measure on Small Complexity Classes, with Applications for BPP. Electron. Colloquium Comput. Complex. TR94 (1994) - 1993
- [j15]Eric Allender, Danilo Bruschi, Giovanni Pighizzini:
The Complexity of Computing Maximal Word Functions. Comput. Complex. 3: 368-391 (1993) - [j14]Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer:
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993) - [c20]Eric Allender, José L. Balcázar, Neil Immerman:
A First-Order Isomorphism Theorem. STACS 1993: 163-174 - [c19]Eric Allender, Jia Jiao:
Depth reduction for noncommutative arithmetic circuits. STOC 1993: 515-522 - [p1]Eric Allender, Klaus W. Wagner:
Counting Hierarchies: Polynomial Time and Constant Depth Circuits. Current Trends in Theoretical Computer Science 1993: 469-483 - 1992
- [j13]Eric Allender, Lane A. Hemachandra:
Lower Bounds for the Low Hierarchy. J. ACM 39(1): 234-251 (1992) - [j12]Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets. SIAM J. Comput. 21(3): 521-539 (1992) - 1991
- [j11]Eric Allender, Vivek Gore:
Rudimentary Reductions Revisited. Inf. Process. Lett. 40(2): 89-95 (1991) - [j10]Eric Allender:
Limitations of the Upward Separation Technique. Math. Syst. Theory 24(1): 53-67 (1991) - [c18]Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets. SCT 1991: 220-229 - [c17]Eric Allender, Vivek Gore:
On Strong Separations from AC0 (Extended Abstract). FCT 1991: 1-15 - 1990
- [j9]Eric Allender, Klaus W. Wagner:
Counting Hierarchies: Polynomial Time and Constant. Bull. EATCS 40: 182-194 (1990) - [j8]Eric Allender, Osamu Watanabe:
Kolmogorov Complexity and Degrees of Tally Sets. Inf. Comput. 86(2): 160-178 (1990) - [j7]Eric Allender, Christopher B. Wilson:
Downward Translations of Equality. Theor. Comput. Sci. 75(3): 335-346 (1990) - [c16]Eric Allender, Christopher B. Wilson:
Width-Bounded Reducibility and Binary Search over Complexity Classes. SCT 1990: 122-129 - [c15]Eric Allender, Vivek Gore:
On Strong Separations from AC. Advances In Computational Complexity Theory 1990: 21-37 - [c14]Eric Allender, Ulrich Hertrampf:
On the Power of Uniform Families of Constant Depth Treshold Circuits. MFCS 1990: 158-164 - [c13]Eric Allender:
Oracles versus Proof Techniques that Do Not Relativize. SIGAL International Symposium on Algorithms 1990: 39-52 - [c12]Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer:
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11
1980 – 1989
- 1989
- [j6]Eric Allender:
P-uniform circuit complexity. J. ACM 36(4): 912-928 (1989) - [j5]Eric Allender:
Some Consequences of the Existence of Pseudorandom Generators. J. Comput. Syst. Sci. 39(1): 101-124 (1989) - [c11]Eric Allender:
The Generalized Kolmogorov Complexity of Sets. SCT 1989: 186-194 - [c10]Eric Allender:
A Note on the Power of Threshold Circuits. FOCS 1989: 580-584 - [c9]Eric Allender:
Limitations of the Upward Separation Technique (Preliminary Version). ICALP 1989: 18-30 - [c8]Eric Allender, Lane A. Hemachandra:
Lower Bounds for the Low Hierarchy (Extended Abstract). ICALP 1989: 31-45 - 1988
- [j4]Eric Allender:
Isomorphisms and 1-L Reductions. J. Comput. Syst. Sci. 36(3): 336-350 (1988) - [j3]Eric Allender, Roy S. Rubinstein:
P-Printable Sets. SIAM J. Comput. 17(6): 1193-1202 (1988) - [c7]Eric Allender, Osamu Watanabe:
Kolmogorov complexity and degrees of tally sets. SCT 1988: 102-111 - [c6]Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra:
On Generating Solved Instances of Computational Problems. CRYPTO 1988: 297-310 - 1987
- [c5]Eric Allender:
Some consequences of the existence of pseudorandom generators. SCT 1987: 157 - [c4]Eric Allender:
Some Consequences of the Existence of Pseudorandom Generators. STOC 1987: 151-159 - 1986
- [c3]Eric Allender:
The Complexity of Sparse Sets in P. SCT 1986: 1-11 - [c2]Eric Allender:
Isomorphisms and 1-L Reductions. SCT 1986: 12-22 - [c1]Eric Allender:
Characterizations on PUNC and Precomputation (Extended Abstract). ICALP 1986: 1-10 - 1985
- [j2]Eric Allender:
On the number of cycles possible in digraphs with large girth. Discret. Appl. Math. 10(3): 211-225 (1985) - [j1]Eric Allender, Maria M. Klawe:
Improved Lower Bounds for the Cycle Detection Problem. Theor. Comput. Sci. 36: 231-237 (1985)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-21 00:00 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
