Eric Allender

ORCID

Publication Activity (10 Years)

Years Active: 1985-2023
Publications (10 Years): 41

Top Venues

Electron. Colloquium Comput. Complex.

MFCS

ACM Trans. Comput. Theory

Theory Comput. Syst.

Publications

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
Robustness for Space-Bounded Statistical Zero Knowledge. APPROX/RANDOM (2023)
Eric Allender
Guest Column: Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes! SIGACT News 54 (1) (2023)
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
Cryptographic hardness under projections for time-bounded Kolmogorov complexity. Theor. Comput. Sci. 940 (Part) (2023)
Eric Allender, Shuichi Hirahara, Harsha Tirumala
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. ITCS (2023)
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) (2023)
Eric Allender, Shuichi Hirahara, Harsha Tirumala
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. Electron. Colloquium Comput. Complex. (2022)
Eric Allender, Archit Chauhan, Samir Datta
Depth-first search in directed planar graphs, revisited. Acta Informatica 59 (4) (2022)
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. (2022)
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
Robustness for Space-Bounded Statistical Zero Knowledge. Electron. Colloquium Comput. Complex. (2022)
Eric Allender, Archit Chauhan, Samir Datta
Depth-First Search in Directed Planar Graphs, Revisited. MFCS (2021)
Eric Allender, Rahul Ilango, Neekon Vafa
The Non-hardness of Approximating Circuit Size. Theory Comput. Syst. 65 (3) (2021)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
One-way Functions and Partial MCSP. Electron. Colloquium Comput. Complex. 28 (2021)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
One-Way Functions and a Conditional Variant of MKTP. FSTTCS (2021)
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. ISAAC (2021)
Eric Allender
The New Complexity Landscape around Circuit Minimization. Electron. Colloquium Comput. Complex. 27 (2020)
Eric Allender, Archit Chauhan, Samir Datta
Depth-First Search in Directed Graphs, Revisited. Electron. Colloquium Comput. Complex. 27 (2020)
Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla
A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Eric Allender
The New Complexity Landscape Around Circuit Minimization. LATA (2020)
Eric Allender
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity. Complexity and Approximation (2020)
Eric Allender, Ian Mertz
Complexity of regular functions. J. Comput. Syst. Sci. 104 (2019)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata. Theory Comput. Syst. 63 (3) (2019)
Eric Allender, Shuichi Hirahara
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. ACM Trans. Comput. Theory 11 (4) (2019)
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee
Planarity, Exclusivity, and Unambiguity. Electron. Colloquium Comput. Complex. 26 (2019)
Eric Allender, Martin Farach-Colton, Meng-Tsung Tsai
Syntactic Separation of Subset Satisfiability Problems. APPROX-RANDOM (2019)
Eric Allender, Rahul Ilango, Neekon Vafa
The Non-hardness of Approximating Circuit Size. CSR (2019)
Eric Allender, Rahul Ilango, Neekon Vafa
The Non-Hardness of Approximating Circuit Size. Electron. Colloquium Comput. Complex. 25 (2018)
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) (2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. ITCS (2018)
Eric Allender, Dhiraj Holden, Valentine Kabanets
The Minimum Oracle Circuit Size Problem. Comput. Complex. 26 (2) (2017)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata. MFCS (2017)
Eric Allender, Bireswar Das
Zero knowledge and circuit minimization. Inf. Comput. 256 (2017)
Eric Allender, Anna Gál, Ian Mertz
Dual VP Classes. Comput. Complex. 26 (3) (2017)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Machines. Electron. Colloquium Comput. Complex. 24 (2017)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. Electron. Colloquium Comput. Complex. 24 (2017)
Eric Allender
The Complexity of Complexity. Computability and Complexity (2017)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. CoRR (2017)
Eric Allender, Shuichi Hirahara
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. Electron. Colloquium Comput. Complex. 24 (2017)
Eric Allender
News from ACM transactions on Computation theory: New Editor-in-Chief. Bull. EATCS 122 (2017)
Eric Allender, Shuichi Hirahara
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. MFCS (2017)
Eric Allender, Fengming Wang
On the power of algebraic branching programs of width two. Comput. Complex. 25 (1) (2016)
Eric Allender, Ian Mertz
Complexity of Regular Functions. LATA (2015)
Eric Allender, Asa Goodwillie
Arithmetic circuit classes over Zm. Electron. Colloquium Comput. Complex. 22 (2015)
Eric Allender, Anna Gál, Ian Mertz
Dual VP Classes. MFCS (2) (2015)
Eric Allender, Dhiraj Holden, Valentine Kabanets
The Minimum Oracle Circuit Size Problem. STACS (2015)
Eric Allender, Ian Mertz
Complexity of Regular Functions. Electron. Colloquium Comput. Complex. 22 (2015)
Eric Allender, Joshua A. Grochow, Cristopher Moore
Graph Isomorphism and Circuit Size. Electron. Colloquium Comput. Complex. 22 (2015)
Eric Allender, Joshua A. Grochow, Cristopher Moore
Graph Isomorphism and Circuit Size. CoRR (2015)
Eric Allender, Klaus-Jörn Lange
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Theory Comput. 10 (2014)
Eric Allender, Nikhil Balaji, Samir Datta
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. MFCS (2) (2014)
Eric Allender, Bireswar Das
Zero Knowledge and Circuit Minimization. MFCS (2) (2014)
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) (2014)
Eric Allender, Bireswar Das
Zero Knowledge and Circuit Minimization. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Allender, Anna Gál, Ian Mertz
Dual VP Classes. Electron. Colloquium Comput. Complex. 21 (2014)
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)
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang
Width-Parametrized SAT: Time--Space Tradeoffs. Theory Comput. 10 (2014)
Eric Allender, Dhiraj Holden, Valentine Kabanets
The Minimum Oracle Circuit Size Problem. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Allender, Shafi Goldwasser
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II. ACM Trans. Comput. Theory 6 (3) (2014)
Eric Allender, Vikraman Arvind, Meena Mahajan
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series. Theory Comput. Syst. 53 (3) (2013)
Eric Allender, Nikhil Balaji, Samir Datta
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. Electron. Colloquium Comput. Complex. 20 (2013)
Eric Allender, Luke Friedman, William I. Gasarch
Limits on the computational power of random strings. Inf. Comput. 222 (2013)
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)
Eric Allender, Shafi Goldwasser
Introduction to the special issue on innovations in theoretical computer science 2012. ACM Trans. Comput. Theory 5 (3) (2013)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS (2012)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the set of random strings: the resource-bounded case. Electron. Colloquium Comput. Complex. 19 (2012)
Eric Allender, Holger Spakowski
Avoiding Simplicity is Complex. Theory Comput. Syst. 51 (3) (2012)
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. 19 (2012)
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. 19 (2012)
Eric Allender
Curiouser and Curiouser: The Link between Incompressibility and Complexity. CiE (2012)
Eric Allender, Fengming Wang
On the power of algebraic branching programs of width two. Electron. Colloquium Comput. Complex. 18 (2011)
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) (2011)
Eric Allender, Luke Friedman, William I. Gasarch
Limits on the Computational Power of Random Strings. ICALP (1) (2011)
Eric Allender, Fengming Wang
On the Power of Algebraic Branching Programs of Width Two. ICALP (1) (2011)
Eric Allender, Vikraman Arvind, Fengming Wang
Uniform Derandomization from Pathetic Lower Bounds. APPROX-RANDOM (2010)
Eric Allender
Avoiding Simplicity Is Complex. CiE (2010)
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. 17 (2010)
Eric Allender, Klaus-Jörn Lange
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Computational Complexity Conference (2010)
Eric Allender, Michal Koucký
Amplifying lower bounds by means of self-reducibility. J. ACM 57 (3) (2010)
Eric Allender, Klaus-Jörn Lange
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Electron. Colloquium Comput. Complex. 17 (2010)
Eric Allender
Avoiding Simplicity is Complex. Electron. Colloquium Comput. Complex. 17 (2010)
Eric Allender, Luke Friedman, William I. Gasarch
Limits on the Computational Power of Random Strings. Electron. Colloquium Comput. Complex. 17 (2010)
Eric Allender, Vikraman Arvind, Fengming Wang
Uniform Derandomization from Pathetic Lower Bounds. Electron. Colloquium Comput. Complex. 17 (2010)
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) (2009)
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. Electron. Colloquium Comput. Complex. 16 (2009)
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45 (4) (2009)
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) (2009)
Eric Allender
A Status Report on the P Versus NP Question. Adv. Comput. 77 (2009)
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
On the Complexity of Numerical Analysis. SIAM J. Comput. 38 (5) (2009)
Eric Allender
Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds. DCFS (2008)
Eric Allender, Michal Koucký
Amplifying Lower Bounds by Means of Self-Reducibility. Computational Complexity Conference (2008)
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
Circuits Given a Truth Table. SIAM J. Comput. 38 (1) (2008)
Eric Allender
Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds? CATS (2008)
Eric Allender
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds. CSR (2008)
Eric Allender, Michal Koucký
Amplifying Lower Bounds by Means of Self-Reducibility. Electron. Colloquium Comput. Complex. 15 (038) (2008)
Eric Allender
Reachability Problems: An Update. CiE (2007)
Eric Allender
NL-printable sets and nondeterministic Kolmogorov complexity. Theor. Comput. Sci. 355 (2) (2006)
Eric Allender, Harry Buhrman, Michal Koucký
What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Log. 138 (1-3) (2006)
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
Grid Graph Reachability Problems. Computational Complexity Conference (2006)
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
Power from Random Strings. SIAM J. Comput. 35 (6) (2006)
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
On the Complexity of Numerical Analysis. Complexity of Boolean Functions (2006)

Eric Allender.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Eric Allender