| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret |
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.  |
Electronic Colloquium on Computational Complexity (ECCC)  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang |
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Fengming Wang |
On the power of algebraic branching programs of width two. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy |
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. |
J. Comput. Syst. Sci. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Luke Friedman, William I. Gasarch |
Limits on the Computational Power of Random Strings. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Fengming Wang |
On the Power of Algebraic Branching Programs of Width Two. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Klaus-Jörn Lange |
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Luke Friedman, William I. Gasarch |
Limits on the Computational Power of Random Strings. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender |
Avoiding Simplicity is Complex. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Vikraman Arvind, Fengming Wang |
Uniform Derandomization from Pathetic Lower Bounds. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký |
Amplifying lower bounds by means of self-reducibility. |
J. ACM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Vikraman Arvind, Fengming Wang |
Uniform Derandomization from Pathetic Lower Bounds. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Klaus-Jörn Lange |
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Symmetric Computation, Auxiliary Pushdown Automata, LogCFL, Reversible Computation |
| 1 | Eric Allender |
Avoiding Simplicity Is Complex. |
CiE |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy |
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy |
Planar and Grid Graph Reachability Problems. |
Theory Comput. Syst. |
2009 |
DBLP DOI BibTeX RDF |
Logspace, Algorithms, Planar graphs, Reachability, Complexity theory, Circuit complexity, Grid graphs |
| 1 | Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer |
The complexity of satisfiability problems: Refining Schaefer's theorem. |
J. Comput. Syst. Sci. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Vladlen Koltun, Maxim Sviridenko |
Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007). |
SIAM J. Comput. |
2009 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
On the Complexity of Numerical Analysis. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
A Status Report on the P Versus NP Question. |
Advances in Computers |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký |
Amplifying Lower Bounds by Means of Self-Reducibility. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
Computational Complexity Theory. |
Wiley Encyclopedia of Computer Science and Engineering |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds. |
CSR |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds? |
CATS |
2008 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender |
Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds. |
DCFS |
2008 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký |
Amplifying Lower Bounds by Means of Self-Reducibility. |
IEEE Conference on Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
self-reducibility, lower bounds, circuit complexity |
| 1 | Eric Allender |
Reachability Problems: An Update. |
CiE |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
NL-printable sets and nondeterministic Kolmogorov complexity. |
Theor. Comput. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Harry Buhrman, Michal Koucký |
What can be efficiently reduced to the Kolmogorov-random strings? |
Ann. Pure Appl. Logic |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger |
Power from Random Strings. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
On the Complexity of Numerical Analysis. |
Complexity of Boolean Functions |
2006 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks |
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. |
IEEE Conference on Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
On the Complexity of Numerical Analysis. |
IEEE Conference on Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy |
Grid Graph Reachability Problems. |
IEEE Conference on Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy |
Grid Graph Reachability Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
On the Complexity of Numerical Analysis |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Samir Datta, Sambuddha Roy |
The Directed Planar Reachability Problem |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks |
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender |
Special issue, final part "Conference on Computational Complexity 2004 " Guest Editor's foreword. |
Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword. |
Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer |
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. |
MFCS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Samir Datta, Sambuddha Roy |
Topology Inside NC¹. |
IEEE Conference on Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Samir Datta, Sambuddha Roy |
The Directed Planar Reachability Problem. |
FSTTCS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Samir Datta, Sambuddha Roy |
Topology inside NC1 |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Harry Buhrman, Michal Koucký |
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer |
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Meena Mahajan |
The complexity of planarity testing. |
Inf. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Harry Buhrman, Michal Koucký |
What Can be Efficiently Reduced to the K-Random Strings? |
STACS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
NL-printable sets and Nondeterministic Kolmogorov Complexity. |
Electr. Notes Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor Shparlinski |
Complexity of some arithmetic problems for binary polynomials. |
Computational Complexity |
2003 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000). ((no classification)) |
| 1 | Eric Allender, Vikraman Arvind, Meena Mahajan |
Arithmetic Complexity, Kleene Closure, and Formal Power Series. |
Theory Comput. Syst. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy |
Derandomization and Distinguishing Complexity. |
IEEE Conference on Computational Complexity |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek |
Power from Random Strings |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | William Hesse, Eric Allender, David A. Mix Barrington |
Uniform constant-depth threshold circuits for division and iterated multiplication. |
J. Comput. Syst. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger |
Power from Random Strings. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell |
A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics. |
NIPS |
2002 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay |
Time-Space Tradeoffs in the Counting Hierarchy |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington, William Hesse |
Uniform Circuits for Division: Consequences and Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich |
Reducing the complexity of reductions. |
Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
The Division Breakthroughs. |
Bulletin of the EATCS |
2001 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michael E. Saks, Igor Shparlinski |
A Lower Bound for Primality. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front. |
Current Trends in Theoretical Computer Science |
2001 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay |
Time-Space Tradeoffs in the Counting Hierarchy. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington, William Hesse |
Uniform Circuits for Division: Consequences and Problems. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity. |
FSTTCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington |
Uniform Circuits for Division: Consequences and Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
2000 |
DBLP BibTeX RDF |
|
| 1 | Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner |
Characterizing Small Depth and Small Space Classes by Operators of Higher Type. |
Chicago J. Theor. Comput. Sci. |
2000 |
DBLP BibTeX RDF |
|
| 1 | Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender |
Complexity of finite-horizon Markov decision process problems. |
J. ACM |
2000 |
DBLP DOI BibTeX RDF |
NPPP, computational complexity, Markov decision processes, NP, PL, partially observable Markov decision processes, PSPACE, succinct representations |
| 1 | Eric Allender |
Report on the annual summer meeting of the New Zealand mathematics research institute. |
SIGACT News |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Eric Allender, Samir Datta |
On TC0, AC0, and Arithmetic Circuits. |
J. Comput. Syst. Sci. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Reinhardt, Eric Allender |
Making Nondeterminism Unambiguous. |
SIAM J. Comput. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Meena Mahajan |
The Complexity of Planarity Testing. |
STACS |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender |
Complexity of Finite-Horizon Markov Decision process Problems. |
Universität Trier, Mathematik/Informatik, Forschungsbericht |
1999 |
RDF |
|
| 1 | Eric Allender, Vikraman Arvind, Meena Mahajan |
Arithmetic Complexity, Kleene Closure, and Formal Power Series |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh |
Bounded Depth Arithmetic Circuits: Counting and Closure |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Igor Shparlinski, Michael E. Saks |
A Lower Bound for Primality |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender |
The Permanent Requires Large Uniform Threshold Circuits. |
Chicago J. Theor. Comput. Sci. |
1999 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Robert Beals, Mitsunori Ogihara |
The Complexity of Matrix Rank and Feasible Systems of Linear Equations. |
Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Klaus Reinhardt, Shiyu Zhou |
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds. |
J. Comput. Syst. Sci. |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh |
Bounded Depth Arithmetic Circuits: Counting and Closure. |
ICALP |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Michael E. Saks, Igor Shparlinski |
A Lower Bound for Primality. (PDF / PS) |
IEEE Conference on Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
Circuit Complexity Lower Bounds, Primality, Square-Free Numbers, GCD |
| 1 | Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner |
Characterizing Small Depth and Small Space Classes by Operators of Higher Types |
Electronic Colloquium on Computational Complexity (ECCC) |
1998 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Shiyu Zhou |
Uniform Inclusions in Nondeterministic Logspace |
Electronic Colloquium on Computational Complexity (ECCC) |
1998 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Klaus Reinhardt |
Isolation, Matching, and Counting |
Electronic Colloquium on Computational Complexity (ECCC) |
1998 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay |
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. |
Theor. Comput. Sci. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender |
News from the Isomorphism Front. |
Bulletin of the EATCS |
1998 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Klaus-Jörn Lange |
RUSPACE(log n) $\subseteq$ DSPACE (log2 n / log log n). |
Theory Comput. Syst. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Eric Allender, Steven Rudich |
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. |
J. Comput. Syst. Sci. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Klaus Reinhardt |
Isolation, Matching, and Counting. (PDF / PS) |
IEEE Conference on Computational Complexity |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Reinhardt, Eric Allender |
Making Nondeterminism Unambiguous |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Manindra Agrawal, Eric Allender, Samir Datta |
On TC0, AC0, and Arithmetic Circuits |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender |
Making computation count: arithmetic circuits in the nineties. |
SIGACT News |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, José L. Balcázar, Neil Immerman |
A First-Order Isomorphism Theorem. |
SIAM J. Comput. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Mundhenk, Judy Goldsmith, Eric Allender |
The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. |
MFCS |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Reinhardt, Eric Allender |
Making Nondeterminism Unambiguous. |
FOCS |
1997 |
DBLP DOI BibTeX RDF |
nonuniform complexity, nondeterministic logarithmic space bounded computation, computational complexity, nondeterminism, complexity classes, context-free languages |
| 1 | Manindra Agrawal, Eric Allender, Samir Datta |
On TC0, AC0, and Arithmetic Circuits. (PDF / PS) |
IEEE Conference on Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
TC/sup 0/, AC/sup 0/, function classes, constant-depth polynomial-size arithmetic circuits, unbounded fanin addition, multiplication gates, constant-depth arithmetic circuits, computational complexity, normal forms, arithmetic circuits, closure properties |
| 1 | Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich |
Reducing the Complexity of Reductions. |
STOC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Klaus-Jörn Lange |
StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n) |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")