Eric Allender

Rutgers, The State University of New Jersey — United States

Computer Science · Physical Sciences

29h-index3.3kcitations224works0.32yr avg
OpenAlex↗ORCID↗Google Scholar↗Lab page↗

Accepting Students?

No reports yet. Know if this professor is taking students?

Research Topics

Complexity and Algorithms in Graphs(120), Computability, Logic, AI Algorithms(91), semigroups and automata theory(57), Advanced Graph Theory Research(43), Cryptography and Data Security(25)

Publications224 total

Kolmogorov Complexity Characterizes Statistical Zero Knowledge
ACM Transactions on Computation Theory·2026Open Access
Comment on “SAT requires exhaustive search”
Frontiers of Computer Science·2025Open Access
Robustness for Space-Bounded Statistical Zero Knowledge
ACM Transactions on Computation Theory·2024· 1 citedOpen Access
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs
Computability·2023· 2 cited
Guest Column
ACM SIGACT News·2023· 2 cited
Cryptographic hardness under projections for time-bounded Kolmogorov complexity
Theoretical Computer Science·2022· 4 cited
Depth-first search in directed planar graphs, revisited
Acta Informatica·2022· 6 cited
The new complexity landscape around circuit minimization
View·2022Open Access
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
New Zealand journal of mathematics·2021· 8 citedOpen Access
One-Way Functions and a Conditional Variant of MKTP
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2021· 6 citedOpen Access
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity
View·2021Open Access
One-way Functions and Partial MCSP.
Electron. Colloquium Comput. Complex.·2021· 2 cited
Depth-First Search in Directed Planar Graphs, Revisited
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2021· 2 citedOpen Access
The Non-hardness of Approximating Circuit Size
Theory of Computing Systems·2020· 5 cited
A note on hardness under projections for graph isomorphism and time-bounded Kolmogorov complexity
View·2020· 1 citedOpen Access
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
Lecture notes in computer science·2020· 2 cited
Depth-First Search in Directed Graphs, Revisited.
Electron. Colloquium Comput. Complex.·2020
The New Complexity Landscape Around Circuit Minimization
Lecture notes in computer science·2020· 11 citedOpen Access
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
ACM Transactions on Computation Theory·2019· 4 citedOpen Access
Syntactic Separation of Subset Satisfiability Problems
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2019Open Access
page 1 of 12Next →

Frequent Co-authors

Michal Koucký(3), Vivek Gore(3), Samir Datta(3), Lane A. Hemachandra(3), Toniann Pitassi(3), Michael Saks(3), David A. Mix Barrington(2), Klaus Reinhardt(2), Mitsunori Ogihara(2), Harry Buhrman(2), Dieter van Melkebeek(2), Detlef Ronneburger(2), Manindra Agrawal(2), Lisa Hellerstein(2), Paul McCabe(2), Steven Rudich(2), Sambuddha Roy(2), Ulrich Hertrampf(2), Michael C. Loui(2), Kenneth W. Regan(2)