☰

Eric Allender - Publications

Affiliations: 
Rutgers University, New Brunswick, New Brunswick, NJ, United States 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

74 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Allender E, Ilango R, Vafa N. The Non-hardness of Approximating Circuit Size Theory of Computing Systems \/ Mathematical Systems Theory. 1-20. DOI: 10.1007/S00224-020-10004-X  0.484
2020 Allender E. Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity Lecture Notes in Computer Science. 12000: 8-18. DOI: 10.1007/978-3-030-41672-0_2  0.491
2019 Allender E, Hirahara S. New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems Acm Transactions On Computation Theory. 11: 1-27. DOI: 10.1145/3349616  0.373
2018 Allender E, Grochow JA, van Melkebeek D, Moore C, Morgan A. Minimum Circuit Size, Graph Isomorphism, and Related Problems Siam Journal On Computing. 47: 1339-1372. DOI: 10.1137/17M1157970  0.44
2018 Allender E, Krebs A, McKenzie P. Better Complexity Bounds for Cost Register Automata Theory of Computing Systems. 63: 367-385. DOI: 10.1007/S00224-018-9871-4  0.532
2016 Allender E, Holden D, Kabanets V. The Minimum Oracle Circuit Size Problem Computational Complexity. 1-28. DOI: 10.1007/S00037-016-0124-0  0.55
2016 Allender E, Wang F. On the power of algebraic branching programs of width two Computational Complexity. 25: 217-253. DOI: 10.1007/S00037-015-0114-7  0.625
2015 Allender E, Mertz I. Complexity of regular functions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8977: 449-460. DOI: 10.1016/J.Jcss.2016.10.005  0.464
2015 Allender E, Gál A, Mertz I. Dual VP classes Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9235: 14-25. DOI: 10.1007/S00037-016-0146-7  0.465
2014 Allender E, Chen S, Lou T, Papakonstantinou PA, Tang B. Width-Parameterized SAT: Time-Space Tradeoffs Theory of Computing. 10: 297-339. DOI: 10.7282/T3N87Cm1  0.361
2014 Hesse W, Allender E, Barrington DAM. Corrigendum to “Uniform constant-depth threshold circuits for division and iterated multiplication” [J. Comput. System Sci. 65 (4) (2002) 695–716] Journal of Computer and System Sciences. 80: 496-497. DOI: 10.1016/J.Jcss.2013.09.002  0.401
2014 Allender E, Das B. Zero knowledge and circuit minimization Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8635: 25-32. DOI: 10.1016/J.Ic.2017.04.004  0.447
2013 Allender E, Friedman L, Gasarch W. Limits on the computational power of random strings Information & Computation. 222: 80-92. DOI: 10.1016/J.Ic.2011.09.008  0.594
2013 Allender E, Arvind V, Mahajan M. Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series Theory of Computing Systems. 53: 503-506. DOI: 10.1007/S00224-013-9471-2  0.401
2012 Allender E, Arvind V, Santhanam R, Wang F. Uniform derandomization from pathetic lower bounds. Philosophical Transactions. Series a, Mathematical, Physical, and Engineering Sciences. 370: 3512-35. PMID 22711871 DOI: 10.1098/Rsta.2011.0318  0.638
2012 Allender E, Buhrman H, Friedman L, Loff B. Reductions to the set of random strings: The resource-bounded case Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7464: 88-99. DOI: 10.2168/Lmcs-10(3:5)2014  0.694
2012 Allender E. Curiouser and curiouser: The link between incompressibility and complexity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7318: 11-16. DOI: 10.1007/978-3-642-30870-3_2  0.354
2011 Allender E, Koucký M, Ronneburger D, Roy S. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory Journal of Computer and System Sciences. 77: 14-40. DOI: 10.1016/J.Jcss.2010.06.004  0.74
2010 Allender E, Lange KJ. Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata Proceedings of the Annual Ieee Conference On Computational Complexity. 172-180. DOI: 10.4086/Toc.2014.V010A008  0.332
2010 Allender E. Avoiding simplicity is complex Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6158: 1-10. DOI: 10.1007/S00224-011-9334-7  0.552
2009 Allender E, Koltun V, Sviridenko M. Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007) Siam Journal On Computing. 39: 978-978. DOI: 10.1137/Smjcat000039000003000978000001  0.319
2009 Allender E, Barrington DAM, Chakraborty T, Datta S, Roy S. Planar and grid graph reachability problems Theory of Computing Systems. 45: 675-723. DOI: 10.1007/S00224-009-9172-Z  0.613
2008 Allender E, Koucký M. Amplifying lower bounds by means of self-reducibility Proceedings of the Annual Ieee Conference On Computational Complexity. 31-40. DOI: 10.1145/1706591.1706594  0.487
2008 Allender E, Hellerstein L, Mccabe P, Pitassi T, Saks M. Minimizing disjunctive normal form formulas and AC0 circuits given a truth table Siam Journal On Computing. 38: 63-84. DOI: 10.1137/060664537  0.514
2008 Allender E. Circuit complexity, kolmogorov complexity, and prospects for lower bounds Descriptional Complexity of Formal Systems - 10th International Workshop, Dcfs 2008. 7-13.  0.53
2006 Allender E, Kjeldgaard-Pedersen J, Bürgisser P, Miltersen PB. On the complexity of numerical analysis Proceedings of the Annual Ieee Conference On Computational Complexity. 2006: 331-339. DOI: 10.1137/070697926  0.499
2006 Allender E, Hellerstein L, McCabe P, Pitassi T, Saks M. Inimizing DNF formulas and ACd0 circuits given a truth table Proceedings of the Annual Ieee Conference On Computational Complexity. 2006: 237-251. DOI: 10.1109/CCC.2006.27  0.396
2006 Allender E, Buhrman H, Koucký M. What can be efficiently reduced to the Kolmogorov-random strings? Annals of Pure and Applied Logic. 138: 2-19. DOI: 10.1016/J.Apal.2005.06.003  0.505
2005 Allender E, Datta S, Roy S. Topology inside NC1 Proceedings of the Annual Ieee Conference On Computational Complexity. 298-307. DOI: 10.1109/CCC.2005.31  0.339
2005 Allender E, Bauland M, Immerman N, Schnoor H, Vollmer H. The complexity of satisfiability problems: Refining Schaefer's theorem Lecture Notes in Computer Science. 3618: 71-82. DOI: 10.1016/J.Jcss.2008.11.001  0.427
2005 Allender E. Special issue, final part "conference on computational complexity 2004" Guest Editor's foreword Computational Complexity. 14: 185. DOI: 10.1007/S00037-005-0196-8  0.422
2005 Allender E. Special issue “Conference on Computational Complexity 2004” Guest Editor’s foreword Computational Complexity. 14: 89-89. DOI: 10.1007/S00037-005-0192-Z  0.429
2004 Allender E, Bernasconi A, Damm C, Gathen JvZ, Saks M, Shparlinski I. Complexity of some arithmetic problems for binary polynomials Computational Complexity. 12: 23-47. DOI: 10.1007/S00037-003-0176-9  0.45
2004 Allender E, Buhrman H, Koucký M. What can be efficiently reduced to the K-Random strings? Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2996: 584-595.  0.497
2003 Allender E. NL-printable sets and nondeterministic Kolmogorov complexity Electronic Notes in Theoretical Computer Science. 84: 5-19. DOI: 10.1016/S1571-0661(04)80838-7  0.56
2003 Hesse W, Allender E, Barrington DAM. Uniform constant-depth threshold circuits for division and iterated multiplication Journal of Computer and System Sciences. 65: 695-716. DOI: 10.1016/S0022-0000(02)00025-9  0.504
2003 Allender E, Arvind V, Mahajan M. Arithmetic complexity, Kleene closure, and formal power series Theory of Computing Systems. 36: 303-328. DOI: 10.1007/S00224-003-1077-7  0.455
2003 Allender E, Koucký M, Roy S, Ronneburger D. Derandomization and distinguishing complexity Proceedings of the Annual Ieee Conference On Computational Complexity. 209-220.  0.765
2003 Allender E, Bernasconi A, Damm C, Von Zur Gathen J, Saks M, Shparlinski I. Complexity of some arithmetic problems for binary polynomials Computational Complexity. 12: 23-47.  0.345
2002 Allender E, Buhrman H, Koucký M, Van Melkebeek D, Ronneburger D. Power from random strings Annual Symposium On Foundations of Computer Science - Proceedings. 669-678. DOI: 10.1137/050628994  0.754
2002 Allender E, Buhrman H, Koucký M, Van Melkebeek D, Ronneburger D. Power from random strings Annual Symposium On Foundations of Computer Science - Proceedings. 669-678. DOI: 10.1137/050628994  0.625
2001 Agrawal M, Allender E, Impagliazzo R, Pitassi T, Rudich S. Reducing the complexity of reductions Computational Complexity. 10: 117-138. DOI: 10.1007/S00037-001-8191-1  0.477
2001 Allender E, Saks M, Shparlinski I. A lower bound for primality Journal of Computer and System Sciences. 62: 356-366. DOI: 10.1006/jcss.2000.1725  0.348
2001 Allender E, Koucký M, Ronneburger D, Roy S, Vinay V. Time-space tradeoffs in the counting hierarchy Proceedings of the Annual Ieee Conference On Computational Complexity. 295-302.  0.732
2000 Mundhenk M, Goldsmith J, Lusena C, Allender E. Complexity of finite-horizon Markov decision process problems Journal of the Acm. 47: 681-720. DOI: 10.1145/347476.347480  0.422
2000 Reinhardt K, Allender E. Making nondeterminism unambiguous Siam Journal On Computing. 29: 1118-1131. DOI: 10.1137/S0097539798339041  0.495
2000 Allender E, Mahajan M. The complexity of planarity testing Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1770: 87-98. DOI: 10.1016/J.Ic.2003.09.002  0.482
2000 Agrawal M, Allender E, Datta S. On TC0, AC0, and arithmetic circuits Journal of Computer and System Sciences. 60: 395-421. DOI: 10.1006/jcss.1999.1675  0.331
1999 Allender E, Beals R, Ogihara M. The complexity of matrix rank and feasible systems of linear equations Computational Complexity. 8: 99-126. DOI: 10.1007/S000370050023  0.46
1999 Allender E, Reinhardt K, Zhou S. Isolation, matching, and counting uniform and nonuniform upper bounds Journal of Computer and System Sciences. 59: 164-181. DOI: 10.1006/Jcss.1999.1646  0.592
1999 Allender E, Ambainis A, Barrington DAM, Datta S, Lêthanh H. Bounded depth arithmetic circuits: Counting and closure Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1644: 149-158.  0.339
1998 Allender E. Book Review: Complexity Theory Retrospective II. Edited by: Lane A. Hemaspaandra and Alan L. Selman (Springer Verlag) Acm Sigact News. 29: 2-5. DOI: 10.1145/281068.1040351  0.336
1998 Allender E, Jiao J, Mahajan M, Vinay V. Non-commutative arithmetic circuits: Depth reduction and size lower bounds Theoretical Computer Science. 209: 47-86. DOI: 10.1016/S0304-3975(97)00227-2  0.514
1998 Allender E. RUSPACE(log n ) $\subseteq$ DSPACE(log 2 n /log log n ) Theory of Computing Systems. 31: 539-550. DOI: 10.1007/S002240000102  0.34
1998 Agrawal M, Allender E, Rudich S. Reductions in Circuit Complexity Journal of Computer and System Sciences. 57: 127-143. DOI: 10.1006/Jcss.1998.1583  0.489
1998 Agrawal M, Allender E, Rudich S. Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem Journal of Computer and System Sciences. 57: 127-143.  0.38
1997 Allender E. Making computation count Acm Sigact News. 28: 2-15. DOI: 10.1145/270563.270564  0.4
1997 Allender E, Balcázar J, Immerman N. A first-order isomorphism theorem Siam Journal On Computing. 26: 557-567. DOI: 10.1137/S0097539794270236  0.454
1996 Allender E, Feigenbaum J, Goldsmith J, Pitassi T, Rudich S. The future of computational complexity theory: part II Acm Sigact News. 27: 3-7. DOI: 10.1145/242581.242582  0.346
1996 Allender E, Ogihara M. Relationships among $PL$, $\#L$, and the determinant Theoretical Informatics and Applications. 30: 1-21. DOI: 10.1051/Ita/1996300100011  0.463
1996 Allender E, Ogihara M. Relationships among PL, #L, and the determinant Theoretical Informatics and Applications. 30: 1-21.  0.363
1996 Allender E. A note on uniform circuit lower bounds for the counting hierarchy Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1090: 127-135.  0.393
1996 Allender E. Circuit complexity before the dawn of the new millennium Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1180: 1-18.  0.392
1995 Allender E, Strauss M. Measure on P: Robustness of the notion Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 969: 129-138.  0.306
1994 Allender E, Gore V. A Uniform Circuit Lower Bound for the Permanent Siam Journal On Computing. 23: 1026-1049. DOI: 10.1137/S0097539792233907  0.523
1994 Allender E, Hertrampf U. Depth Reduction for Circuits of Unbounded Fan-in Information and Computation. 112: 217-238. DOI: 10.1006/Inco.1994.1057  0.452
1993 Allender E, Beigel R, Hertrampf U, Homer S. Almost-everywhere complexity hierarchies for nondeterministic time Theoretical Computer Science. 115: 225-241. DOI: 10.1016/0304-3975(93)90117-C  0.506
1993 Allender E, Bruschi D, Pighizzini G. The complexity of computing maximal word functions Computational Complexity. 3: 368-391. DOI: 10.1007/Bf01275489  0.346
1992 Allender E, Hemachandra LA. Lower Bounds for the Low Hierarchy Journal of the Acm (Jacm). 39: 234-251. DOI: 10.1145/147508.147546  0.444
1992 Allender E, Hemachandra LA, Ogiwara M, Watanabe O. Relating Equivalence and Reducibility to Sparse Sets Siam Journal On Computing. 21: 521-539. DOI: 10.1137/0221034  0.46
1991 Allender E, Gore V. Rudimentary reductions revisited Information Processing Letters. 40: 89-95. DOI: 10.1016/0020-0190(91)90015-A  0.374
1991 Allender E. Limitations of the upward separation technique Mathematical Systems Theory. 24: 53-67. DOI: 10.1007/Bf02090390  0.383
1990 Allender E, Watanabe O. Kolmogorov complexity and degrees of tally sets Information and Computation. 86: 160-178. DOI: 10.1016/0890-5401(90)90052-J  0.584
1989 Allender EW. P-Uniform Circuit Complexity Journal of the Acm (Jacm). 36: 912-928. DOI: 10.1145/76359.76370  0.437
Show low-probability matches.