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) |