2009 | ||
---|---|---|
126 | EE | 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) |
125 | EE | 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) |
2008 | ||
124 | EE | Eric Allender: Chipping Away at P vs NP: How Far Are We from Proving Circuit Size Lower Bounds? CATS 2008: 3 |
123 | EE | Eric Allender: Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds. CSR 2008: 3-10 |
122 | EE | Eric Allender, Michal Koucký: Amplifying Lower Bounds by Means of Self-Reducibility. IEEE Conference on Computational Complexity 2008: 31-40 |
121 | EE | Eric Allender: Computational Complexity Theory. Wiley Encyclopedia of Computer Science and Engineering 2008 |
120 | EE | Eric Allender, Michal Koucký: Amplifying Lower Bounds by Means of Self-Reducibility. Electronic Colloquium on Computational Complexity (ECCC) 15(038): (2008) |
119 | EE | 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) |
2007 | ||
118 | EE | Eric Allender: Reachability Problems: An Update. CiE 2007: 25-27 |
2006 | ||
117 | EE | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. Complexity of Boolean Functions 2006 |
116 | EE | 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: 237-251 |
115 | EE | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems. IEEE Conference on Computational Complexity 2006: 299-313 |
114 | EE | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. IEEE Conference on Computational Complexity 2006: 331-339 |
113 | EE | Eric Allender, Harry Buhrman, Michal Koucký: What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Logic 138(1-3): 2-19 (2006) |
112 | EE | Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006) |
111 | EE | Eric Allender: NL-printable sets and nondeterministic Kolmogorov complexity. Theor. Comput. Sci. 355(2): 127-138 (2006) |
2005 | ||
110 | EE | Eric Allender, Samir Datta, Sambuddha Roy: The Directed Planar Reachability Problem. FSTTCS 2005: 238-249 |
109 | EE | Eric Allender, Samir Datta, Sambuddha Roy: Topology Inside NC¹. IEEE Conference on Computational Complexity 2005: 298-307 |
108 | EE | Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer: The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. MFCS 2005: 71-82 |
107 | EE | Eric Allender: Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword. Computational Complexity 14(2): 89 (2005) |
106 | EE | Eric Allender: Special issue, final part "Conference on Computational Complexity 2004 " Guest Editor's foreword. Computational Complexity 14(3): 185 (2005) |
105 | EE | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis Electronic Colloquium on Computational Complexity (ECCC)(037): (2005) |
104 | EE | 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)(126): (2005) |
103 | EE | Eric Allender, Samir Datta, Sambuddha Roy: The Directed Planar Reachability Problem Electronic Colloquium on Computational Complexity (ECCC)(148): (2005) |
102 | EE | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems Electronic Colloquium on Computational Complexity (ECCC)(149): (2005) |
2004 | ||
101 | EE | Eric Allender, Harry Buhrman, Michal Koucký: What Can be Efficiently Reduced to the K-Random Strings? STACS 2004: 584-595 |
100 | EE | Eric Allender, Harry Buhrman, Michal Koucký: What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electronic Colloquium on Computational Complexity (ECCC)(044): (2004) |
99 | EE | 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)(100): (2004) |
98 | EE | Eric Allender, Samir Datta, Sambuddha Roy: Topology inside NC1 Electronic Colloquium on Computational Complexity (ECCC)(108): (2004) |
97 | EE | Eric Allender, Meena Mahajan: The complexity of planarity testing. Inf. Comput. 189(1): 117-134 (2004) |
2003 | ||
96 | EE | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy: Derandomization and Distinguishing Complexity. IEEE Conference on Computational Complexity 2003: 209-220 |
95 | EE | 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 12(1-2): 23-47 (2003) |
94 | EE | Eric Allender: NL-printable sets and Nondeterministic Kolmogorov Complexity. Electr. Notes Theor. Comput. Sci. 84: (2003) |
93 | EE | Eric Allender, Vikraman Arvind, Meena Mahajan: Arithmetic Complexity, Kleene Closure, and Formal Power Series. Theory Comput. Syst. 36(4): 303-328 (2003) |
2002 | ||
92 | EE | Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. FOCS 2002: 669-678 |
91 | EE | Eric Allender, Sanjeev Arora, Michael S. Kearns, Cristopher Moore, Alexander Russell: A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics. NIPS 2002: 431-437 |
90 | EE | Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek: Power from Random Strings Electronic Colloquium on Computational Complexity (ECCC)(028): (2002) |
89 | EE | William Hesse, Eric Allender, David A. Mix Barrington: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4): 695-716 (2002) |
2001 | ||
88 | EE | Eric Allender: When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity. FSTTCS 2001: 1-15 |
87 | EE | Eric Allender, David A. Mix Barrington, William Hesse: Uniform Circuits for Division: Consequences and Problems. IEEE Conference on Computational Complexity 2001: 150-159 |
86 | EE | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay: Time-Space Tradeoffs in the Counting Hierarchy. IEEE Conference on Computational Complexity 2001: 295-302 |
85 | Eric Allender: Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front. Current Trends in Theoretical Computer Science 2001: 25-41 | |
84 | Eric Allender: The Division Breakthroughs. Bulletin of the EATCS 74: 61-77 (2001) | |
83 | EE | Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the complexity of reductions. Computational Complexity 10(2): 117-138 (2001) |
82 | EE | Eric Allender, David A. Mix Barrington, William Hesse: Uniform Circuits for Division: Consequences and Problems Electronic Colloquium on Computational Complexity (ECCC) 8(33): (2001) |
81 | EE | Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay: Time-Space Tradeoffs in the Counting Hierarchy Electronic Colloquium on Computational Complexity (ECCC) 8(41): (2001) |
80 | Eric Allender, Michael E. Saks, Igor Shparlinski: A Lower Bound for Primality. J. Comput. Syst. Sci. 62(2): 356-366 (2001) | |
2000 | ||
79 | EE | Eric Allender, Meena Mahajan: The Complexity of Planarity Testing. STACS 2000: 87-98 |
78 | EE | 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: (2000) |
77 | EE | Eric Allender, David A. Mix Barrington: Uniform Circuits for Division: Consequences and Problems Electronic Colloquium on Computational Complexity (ECCC) 7(65): (2000) |
76 | EE | Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender: Complexity of finite-horizon Markov decision process problems. J. ACM 47(4): 681-720 (2000) |
75 | Manindra Agrawal, Eric Allender, Samir Datta: On TC0, AC0, and Arithmetic Circuits. J. Comput. Syst. Sci. 60(2): 395-421 (2000) | |
74 | Klaus Reinhardt, Eric Allender: Making Nondeterminism Unambiguous. SIAM J. Comput. 29(4): 1118-1131 (2000) | |
1999 | ||
73 | EE | Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158 |
72 | EE | Eric Allender, Michael E. Saks, Igor Shparlinski: A Lower Bound for Primality. IEEE Conference on Computational Complexity 1999: 10-14 |
71 | EE | Eric Allender: The Permanent Requires Large Uniform Threshold Circuits. Chicago J. Theor. Comput. Sci. 1999: (1999) |
70 | Eric Allender, Robert Beals, Mitsunori Ogihara: The Complexity of Matrix Rank and Feasible Systems of Linear Equations. Computational Complexity 8(2): 99-126 (1999) | |
69 | EE | Eric Allender, Igor Shparlinski, Michael E. Saks: A Lower Bound for Primality Electronic Colloquium on Computational Complexity (ECCC) 6(10): (1999) |
68 | EE | 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) 6(12): (1999) |
67 | EE | Eric Allender, Vikraman Arvind, Meena Mahajan: Arithmetic Complexity, Kleene Closure, and Formal Power Series Electronic Colloquium on Computational Complexity (ECCC) 6(8): (1999) |
66 | Eric Allender, Klaus Reinhardt, Shiyu Zhou: Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds. J. Comput. Syst. Sci. 59(2): 164-181 (1999) | |
65 | Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender: Complexity of Finite-Horizon Markov Decision process Problems. Universität Trier, Mathematik/Informatik, Forschungsbericht 99-25: (1999) | |
1998 | ||
64 | EE | Eric Allender, Klaus Reinhardt: Isolation, Matching, and Counting. IEEE Conference on Computational Complexity 1998: 92-100 |
63 | Eric Allender: News from the Isomorphism Front. Bulletin of the EATCS 66: 73 (1998) | |
62 | EE | Eric Allender, Klaus Reinhardt: Isolation, Matching, and Counting Electronic Colloquium on Computational Complexity (ECCC) 5(19): (1998) |
61 | EE | Eric Allender, Shiyu Zhou: Uniform Inclusions in Nondeterministic Logspace Electronic Colloquium on Computational Complexity (ECCC) 5(23): (1998) |
60 | EE | 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) 5(57): (1998) |
59 | Manindra Agrawal, Eric Allender, Steven Rudich: Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. J. Comput. Syst. Sci. 57(2): 127-143 (1998) | |
58 | EE | Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay: Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theor. Comput. Sci. 209(1-2): 47-86 (1998) |
57 | EE | Eric Allender, Klaus-Jörn Lange: RUSPACE(log n) $\subseteq$ DSPACE (log2 n / log log n). Theory Comput. Syst. 31(5): 539-550 (1998) |
1997 | ||
56 | EE | Klaus Reinhardt, Eric Allender: Making Nondeterminism Unambiguous. FOCS 1997: 244-253 |
55 | EE | Manindra Agrawal, Eric Allender, Samir Datta: On TC0, AC0, and Arithmetic Circuits. IEEE Conference on Computational Complexity 1997: 134-148 |
54 | Martin Mundhenk, Judy Goldsmith, Eric Allender: The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. MFCS 1997: 129-138 | |
53 | EE | Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the Complexity of Reductions. STOC 1997: 730-738 |
52 | EE | Klaus Reinhardt, Eric Allender: Making Nondeterminism Unambiguous Electronic Colloquium on Computational Complexity (ECCC) 4(14): (1997) |
51 | EE | Manindra Agrawal, Eric Allender, Samir Datta: On TC0, AC0, and Arithmetic Circuits Electronic Colloquium on Computational Complexity (ECCC) 4(16): (1997) |
50 | Eric Allender, José L. Balcázar, Neil Immerman: A First-Order Isomorphism Theorem. SIAM J. Comput. 26(2): 557-567 (1997) | |
1996 | ||
49 | Eric Allender: A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy (Extended Abstract). COCOON 1996: 127-135 | |
48 | Eric Allender: Circuit Complexity before the Dawn of the New Millennium. FSTTCS 1996: 1-18 | |
47 | EE | Manindra Agrawal, Eric Allender: An Isomorphism Theorem for Circuit Complexity. IEEE Conference on Computational Complexity 1996: 2-11 |
46 | Eric Allender, Klaus-Jörn Lange: StUSPACE(log n) <= DSPACE(log²n / log log n). ISAAC 1996: 193-202 | |
45 | EE | Eric Allender, Robert Beals, Mitsunori Ogihara: The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract). STOC 1996: 161-167 |
44 | EE | Manindra Agrawal, Eric Allender: An Isomorphism Theorem for Circuit Complexity Electronic Colloquium on Computational Complexity (ECCC) 3(2): (1996) |
43 | EE | Eric Allender: A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy Electronic Colloquium on Computational Complexity (ECCC) 3(23): (1996) |
42 | EE | Eric Allender, Robert Beals, Mitsunori Ogihara: The complexity of matrix rank and feasible systems of linear equations Electronic Colloquium on Computational Complexity (ECCC) 3(24): (1996) |
41 | EE | Eric Allender, Klaus-Jörn Lange: StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n) Electronic Colloquium on Computational Complexity (ECCC) 3(48): (1996) |
40 | Eric Allender, Mitsunori Ogihara: Relationships Among PL, #L, and the Determinant. ITA 30(1): 1-21 (1996) | |
1995 | ||
39 | Eric Allender, Martin Strauss: Measure on P: Robustness of the Notion. MFCS 1995: 129-138 | |
38 | EE | Eric Allender, Martin Strauss: Measure on P: Robustness of the Notion Electronic Colloquium on Computational Complexity (ECCC) 2(28): (1995) |
37 | EE | Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay: Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds Electronic Colloquium on Computational Complexity (ECCC) 2(43): (1995) |
1994 | ||
36 | Eric Allender, Martin Strauss: Measure on Small Complexity Classes, with Applications for BPP FOCS 1994: 807-818 | |
35 | Eric Allender, Mitsunori Ogihara: Relationships Among PL, #L, and the Determinant. Structure in Complexity Theory Conference 1994: 267-278 | |
34 | EE | Eric Allender, Martin Strauss: Measure on Small Complexity Classes, with Applications for BPP Electronic Colloquium on Computational Complexity (ECCC) 1(4): (1994) |
33 | Eric Allender, Ulrich Hertrampf: Depth Reduction for Circuits of Unbounded Fan-In Inf. Comput. 112(2): 217-238 (1994) | |
32 | Eric Allender, Vivek Gore: A Uniform Circuit Lower Bound for the Permanent. SIAM J. Comput. 23(5): 1026-1049 (1994) | |
1993 | ||
31 | Eric Allender, José L. Balcázar, Neil Immerman: A First-Order Isomorphism Theorem. STACS 1993: 163-174 | |
30 | EE | Eric Allender, Jia Jiao: Depth reduction for noncommutative arithmetic circuits. STOC 1993: 515-522 |
29 | Eric Allender, Danilo Bruschi, Giovanni Pighizzini: The Complexity of Computing Maximal Word Functions. Computational Complexity 3: 368-391 (1993) | |
28 | Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993) | |
1992 | ||
27 | EE | Eric Allender, Lane A. Hemachandra: Lower Bounds for the Low Hierarchy. J. ACM 39(1): 234-251 (1992) |
26 | Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. SIAM J. Comput. 21(3): 521-539 (1992) | |
1991 | ||
25 | Eric Allender, Vivek Gore: On Strong Separations from AC0 (Extended Abstract). FCT 1991: 1-15 | |
24 | Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. Structure in Complexity Theory Conference 1991: 220-229 | |
23 | Eric Allender, Vivek Gore: Rudimentary Reductions Revisited. Inf. Process. Lett. 40(2): 89-95 (1991) | |
22 | Eric Allender: Limitations of the Upward Separation Technique. Mathematical Systems Theory 24(1): 53-67 (1991) | |
1990 | ||
21 | Eric Allender, Ulrich Hertrampf: On the Power of Uniform Families of Constant Depth Treshold Circuits. MFCS 1990: 158-164 | |
20 | Eric Allender: Oracles versus Proof Techniques that Do Not Relativize. SIGAL International Symposium on Algorithms 1990: 39-52 | |
19 | Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11 | |
18 | Eric Allender, Christopher B. Wilson: Width-Bounded Reducibility and Binary Search over Complexity Classes. Structure in Complexity Theory Conference 1990: 122-129 | |
17 | Eric Allender, Klaus W. Wagner: Counting Hierarchies: Polynomial Time and Constant. Bulletin of the EATCS 40: 182-194 (1990) | |
16 | Eric Allender, Osamu Watanabe: Kolmogorov Complexity and Degrees of Tally Sets Inf. Comput. 86(2): 160-178 (1990) | |
15 | Eric Allender, Christopher B. Wilson: Downward Translations of Equality. Theor. Comput. Sci. 75(3): 335-346 (1990) | |
1989 | ||
14 | Eric Allender: A Note on the Power of Threshold Circuits FOCS 1989: 580-584 | |
13 | Eric Allender: Limitations of the Upward Separation Technique (Preliminary Version). ICALP 1989: 18-30 | |
12 | Eric Allender, Lane A. Hemachandra: Lower Bounds for the Low Hierarchy (Extended Abstract). ICALP 1989: 31-45 | |
11 | Eric Allender: The Generalized Kolmogorov Complexity of Sets. Structure in Complexity Theory Conference 1989: 186-194 | |
10 | EE | Eric Allender: P-uniform circuit complexity. J. ACM 36(4): 912-928 (1989) |
9 | Eric Allender: Some Consequences of the Existence of Pseudorandom Generators. J. Comput. Syst. Sci. 39(1): 101-124 (1989) | |
1988 | ||
8 | EE | Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra: On Generating Solved Instances of Computational Problems. CRYPTO 1988: 297-310 |
7 | Eric Allender: Isomorphisms and 1-L Reductions. J. Comput. Syst. Sci. 36(3): 336-350 (1988) | |
6 | Eric Allender, Roy S. Rubinstein: P-Printable Sets. SIAM J. Comput. 17(6): 1193-1202 (1988) | |
1987 | ||
5 | Eric Allender: Some Consequences of the Existence of Pseudorandom Generators STOC 1987: 151-159 | |
1986 | ||
4 | Eric Allender: Characterizations on PUNC and Precomputation (Extended Abstract). ICALP 1986: 1-10 | |
3 | Eric Allender: The Complexity of Sparse Sets in P. Structure in Complexity Theory Conference 1986: 1-11 | |
2 | Eric Allender: Isomorphisms and 1-L Reductions. Structure in Complexity Theory Conference 1986: 12-22 | |
1985 | ||
1 | Eric Allender, Maria M. Klawe: Improved Lower Bounds for the Cycle Detection Problem. Theor. Comput. Sci. 36: 231-237 (1985) |