default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDEric Allender
Person information
- affiliation: Rutgers University, USA
SPARQL queries 
🛈 Please note that only 67% of the records listed on this page have a DOI. Therefore, DOI-based queries can only provide partial results.
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]