What Can be Eciently Reduced to the (2004)
Eric Allender, Harry Buhrman, Michal Koucky
We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of e#cient reducibility to the set of Kolmogorovrandom strings RC . We show that this...
NL-printable sets and Nondeterministic Kolmogorov Complexity (2004)
P-printable sets were defined by Hartmanis and Yesha and have been investigated by several researchers. The analogous notion of Lprintable sets was defined by Fortnow et al; both P-printability and...
Arithmetic Circuits and Counting Complexity (2004)
This paper provides a detailed survey of one small part of the field of arithmetic circuit complexity: the relationship of counting classes to arithmetic circuits. The direction of this body of work...
Algebraic Methods for Proving Lower Bounds in Circuit (2004)
In the limited time available, it will not be possible to give a broad survey of the variety of algebraic techniques that have been used in proving circuit lower bounds. Instead, I will focus...
The Computational Complexity Column (2004)
Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, Evan Golub, Clyde Kruskal, ...
Alice wants to query a database but she does not want the database to learn what she is querying. She can ask for the entire database. Can she get her query answered with less communication? One...
Chicago Journal of Theoretical (2003)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
The Complexity of Planarity Testing (2003)
We clarify the computational complexity of planarity testing, by showing that planarity testing is hard for L, and lies in SL. This nearly settles the question, since it is widely conjectured that L...
Eric Allender, Michael C. Loui, Kenneth W. Regan
Introduction The purposes of complexity theory are to ascertain the amount of computational resources required to solve important computational problems, and to classify problems according to their...
NL-printable sets and Nondeterministic Kolmogorov Complexity (2003)
This paper introduces nondeterministic space-bounded Kolmogorov complexity, and we show that it has some nice properties not shared by some other resource-bounded notions of K-complexity.
Derandomization and Distinguishing Complexity (2003)
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy
We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [2, 3].
Arithmetic Complexity, Kleene Closure, and Formal (2003)
Eric Allender, V Arvind, Meena Mahajan
The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC and GapL. More precisely, we apply the formal power series...
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication (2002)
this paper. 2.1. Circuit Classes We begin by formally defining the three circuit complexity classes that will concern us here. These are given by combinatorial restrictions on the circuits of the...
A Note on the Representational Incompatibility (2002)
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
Power from Random Strings (2002)
Eric Allender, Harry Buhrman, Michal Koucky, Dieter Melkebeek, Detlef Ronneburger
We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These...
Limitations of the Upward Separation Technique (2002)
this paper was presented at the 16th International Colloquium on Automata, Languages, and Programming [3]
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
Algebraic Methods for Proving Lower Bounds in Circuit Complexity (2002)
In the limited time available, it will not be possible to give a broad survey of the variety of algebraic techniques that have been used in proving circuit lower bounds. Instead, I will focus...
Lower Bounds for the Low Hierarchy (2002)
this paper. The low hierarchy, as defined in [Sc-83], can only be used to classify the complexity of sets in NP. In order to talk about related sets that are not in NP, the extended low hierarchy was...
Oracles versus Proof Techniques that Do Not Relativize (2002)
Oracle constructions have long been used to provide evidence that certain questions in complexity theory cannot be resolved using the usual techniques of simulation and diagonalization. However, the...
Power from Random Strings (2002)
Eric Allender, Harry Buhrman, Michal Koucky, Dieter Melkebeek, Detlef Ronneburger
We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These...
Uniform Constant-Depth Threshold Circuits for (2002)
this paper. 2.1. Circuit Classes We begin by formally defining the three circuit complexity classes that will concern us here. These are given by combinatorial restrictions on the circuits of the...
Power from Random Strings (2002)
Eric Allender, Harry Buhrman, Michal Koucky, Dieter Melkebeek, Detlef Ronneburger
We consider sets of strings with high Kolmogorov complexity, mainly in resource-bounded settings but also in the traditional recursion-theoretic sense. We present e#cient reductions, showing that...
Power from Random Strings (2002)
Eric Allender, Michal Koucky, Detlef Ronneburger
Kabanets and Cai considered the problem MCSP of determining the size of the smallest circuit computing a Boolean function [KC00]. They argued that it was unlikely that MCSP is in P or is NP-complete....
Comput. Complex. 10 (2001), 117 -- 138 (2001)
Manindra Agrawal, Eric Allender, Toniann Pitassi, Steven Rudich
We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC...
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity (2001)
. This paper has the following goals: -- To survey some of the recent developments in the field of derandomization. -- To introduce a new notion of time-bounded Kolmogorov complexity (KT), and show...
On the Complexity of Some Arithmetic Problems over F2[T] (2001)
Eric Allender, Anna Bernasconi, Carsten Damm, Michael Saks, Igor Shparlinski
In this paper, we study various combinatorial complexity characteristics of Boolean functions related to some natural arithmetic problems about polynomials over IF 2 . In particular, we consider the...
Eric Allender, Catherine Mccartin
. This paper summarizes a series of three lectures the first author was invited to present at the NZMRI summer 2000 workshop, held in Kaikoura, New Zealand. Lecture 1 presents the goals of...
Time-Space Tradeoffs in the Counting Hierarchy (2001)
Eric Allender, Michal Kouck, Detlef Ronneburger
We extend the lower bound techniques of [14], to the unbounded-error
this article, we now know that such problems are all isomorphic to the standard complete set for the complexity class, under depth-three AC
Other Complexity Classes and Measures (2001)
Eric Allender, Michael C. Loui, Kenneth W. Regan
Introduction In the previous twochapters, wehave introduced the basic complexity classes, summarized the known relationships between these classes, and seen how reducibility and completeness can be...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2001)
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators...
Measure on Small Complexity Classes, with Applications for BPP (2001)
We present a notion of resource-boundedmeasure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause Lutz's...
A Clarication Concerning the L Hierarchy (2001)
In #AO96#, it is stated #without proof# that if NC ##L# = AC ##L#, then the #L hierarchy collapses to some level. This note provides a proof of that claim. The reader is referredto#AO96# for all...
Reductions in Circuit Complexity: (2001)
Manindra Agrawal, Eric Allender, Steven Rudich
We show that all sets that arecomplete for NP under non-uniform AC are isomorphic under non-uniform AC -computable isomorphisms. Furthermore, these sets remain NP-complete even under non-uniform NC...
Bounded Depth Arithmetic Circuits: Counting and Closure (2001)
Eric Allender, Andris Ambainis, Samir Datta, Huong Lethanh
Constant-depth arithmetic circuits have been defined and studied in [AAD97, ABL98]; these circuits yield the function classes #AC . These function classes in turn provide new characterizations of the...
RUSPACElog(n) is contained in DSPACE(log n/loglog^2 n) (2001)
Eric Allender, Klaus-jorn Lange
We present a deterministic algorithm running in space O , log n= log log n # solving the connectivity problem on strongly unambiguous graphs. In addition, we presentanO#log n# time-bounded algorithm...
A Uniform Circuit Lower Bound For The Permanent (2001)
We show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP. This is one of the very few...
On TC^0, AC^0, and Arithmetic Circuits (2001)
Manindra Agrawal, Eric Allender, Samir Datta
Continuing a line of investigation that has studied the function classes #P [Val79b], #SAC [Val79a, Vin91, AJMV], #L [AJ93b, Vin91, AO94], and #NC [CMTV96], we study the class of functions . One way...
The Complexity of Matrix Rank and Feasible Systems of Linear (2001)
Eric Allender, Robert Beals, Mitsunori Ogihara
Wecharacterize the complexity of some natural and important problems in linear algebra. In particular, we identify natural complexity classes for which the problems of #a# determining if a system of...
Measure on P: Robustness of the Notion (2001)
In #AS#, we de#ned a notion of measure on the complexity class P #in the spirit of the work of Lutz #L92# that provides a notion of measure on complexity classes at least as large as E, and the work...
Complexity of Finite-Horizon Markov Decision Process Problems (2001)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Eric Allender
This paper considers the computational complexity of the basic tasks facing such a controller
The Permanent Requires Large Uniform Threshold Circuits (2001)
We show that the permanent cannot be computed by uniform constantdepth threshold circuits of size #n#, for any function such that for all k, T #k# #. More generally,we show that any problem that is...
Almost-Everywhere Complexity Hierarchies for (2001)
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
this paper, if is time-constructible, then #n# # for all n
Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory (2001)
This paper presents one method of using time-bounded Kolmogorov complexity as a measure of the complexity of sets, and outlines anumber of applications of this approach to di#erent questions in...
Making Nondeterminism Unambiguous (2001)
Klaus Reinhardt, Eric Allender
We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to...
Relationships Among PL, L, and the Determinant (2001)
Eric Allender, Mitsunori Ogihara
Recent results byToda, Vinay, Damm, and Valianthave shown that the complexity of the determinantischaracterized by the complexity of counting the number of accepting computations of a...
A Lower Bound for Primality (2001)
Eric Allender, Michael Saks, Igor Shparlinski
Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC , and raised as an open question whether similar (or stronger) lower bounds could be proved for...
Rudimentary Reductions Revisited (2001)
We show that log-bounded rudimentary reductions #de#ned and studied by Jones in 1975# characterize Dlogtime-uniform AC .
A First-Order Isomorphism Theorem (2001)
Eric Allender, Jose Balcazar, Neil Immerman
We show that for most complexity classes of interest, all sets complete under #rstorder projections #fops# are isomorphic under #rst-order isomorphisms. That is, a very restricted version of the...
Non-Commutative Arithmetic Circuits: (2001)
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay
Weinvestigate the phenomenon of depth-reduction in commutativeand non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...
Relating Equivalence And Reducibility To Sparse Sets (2001)
Eric Allender, Lane A. Hemachandra
For various polynomial-time reducibilities r, this paper asks whether being r-reducible to a sparse set is a broader notion than being r-equivalent to a sparse set. Although distinguishing...
Isolation, Matching, and Counting: Uniform And Nonuniform (2001)
Eric Allender, Klaus Reinhardt, Shiyu Zhou
We show that the perfect matching problem is in the complexity class SPL #in the nonuniform setting#. This provides a better upper bound on the complexity of the matching problem, as well as...
The Complexity Of Computing (2001)
Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were #rst investigated in relation to data compression #21#. By the #maximal word...
Reducibility and Completeness (2001)
Eric Allender, Michael C. Loui, Kenneth W. Regan
Introduction There is little doubt that the notion of reducibility is the most useful tool that complexity theory has delivered to the rest of the computer science community. For most computational...
Circuit Complexity before the Dawn of the New Millennium (2001)
The 1980's saw rapid and exciting development of techniques for proving lower bounds in circuit complexity. This pace has slowed recently, and there has even been work indicating that quite di#erent...
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem (2001)
Manindra Agrawal, Eric Allender, Steven Rudich
We show that all sets that are complete for NP under non-uniform AC 0 reductions are isomorphic under non-uniform AC 0 -computable isomorphisms. Furthermore, these sets remain NP-complete even under...
The Division Breakthroughs (2001)
this article. I am not aware of any recent breakthrough on this question; any good textbook on design and analysis of algorithms will tell you about the current state of the art on that front.
Time-Space Tradeoffs in the Counting Hierarchy (2001)
Eric Allender, Michal Kouck, Detlef Ronneburger
We extend the lower bound techniques of [14], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjasci's theorem from the Boolean setting to the...
Uniform Circuits for Division: Consequences and Problems (2001)
Eric Allender, David Barrington, William Hesse
Integer division has been known to lie in P-uniform TC 0 since the mid-1980's, and recently this was improved to L- uniform TC 0 . At the time that the results in this paper were proved and submitted...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2000)
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators...
Bounded Depth Arithmetic Circuits: Counting and Closure (2000)
Eric Allender, Andris Ambainis, Samir Datta
. Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC 0 and GapAC 0 . These function classes in turn provide new...
Some Pointed Questions Concerning Asymptotic Lower Bounds (2000)
OmegaGamma n) to compute, and also requires circuit size 2 OmegaGamma n) . This still doesn't tell me that I won't be able to compute f for my application. I'm never going to need 1 Supported in part...
Recent Advances Towards Proving (2000)
Two independent techniques have been developed recently that yield sufficient conditions for P = BPP in terms of worst-case circuit complexity of functions computable in exponential time. Andreev,...
News from the Isomorphism Front (2000)
this article. First, however, we will need to make a digression, while we discuss some recent progress on the isomorphism conjecture.
Computational Tractability: The View From Mars (2000)
Eric Allender, Rodney G. Downey, Michael R. Fellows, Ulrike Stege
Introduction There are two di#erent ways that one can view the theory of parameterized complexity. The easiest is as a kind of "first aid" that can sometimes be applied to problems that are NP-hard,...
The Computational Complexity Column (2000)
: Hemaspaandra, Hempel, and Wechsung [HHW95] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the...
Complexity of Finite-Horizon Markov Decision Process Problems (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specic permission...
Relating Equivalence And Reducibility To Sparse Sets (2000)
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara
. For various polynomial-time reducibilities r, this paper asks whether being r-reducible to a sparse set is a broader notion than being r-equivalent to a sparse set. Although distinguishing...
Twelve Problems in Resource-Bounded Measure (2000)
Introduction Investigation of the measure-theoretic structure of complexity classes began with the development of resource-bounded measure in 1991 [56]. Since that time, a growing body of research by...
Low-Discrepancy Sets for High-Dimensional Rectangles: A Survey (1999)
Eric Allender, Aravind Srinivasan
A sub-area of discrepancy theory that has received much attention in computer science recently, is that of explicit constructions of low-discrepancy point sets for various types of rectangle families...
The Complexity of Planarity Testing (1999)
. We clarify the computational complexity of planarity testing, by showing that planarity testing is hard for L, and lies in SL. This nearly settles the question, since it is widely conjectured that...
The Complexity of Planarity Testing (1999)
. We clarify the computational complexity of planarity testing, by showing that planarity testing is hard for L, and lies in SL. This nearly settles the question, since it is widely conjectured that...
Complexity of Finite-Horizon Markov Decision Process Problems (1999)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
This paper considers the computational complexity of the basic tasks facing such a controller.
Arithmetic Complexity, Kleene Closure, and Formal Power Series (1999)
Eric Allender, V Arvind, Meena Mahajan
The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC 1 and GapL. More precisely, we apply the Kleene closure of...
A Lower Bound for Primality (1999)
Eric Allender, Michael Saks, Igor Shparlinski
Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC 0 , and raised as an open question if similar (or stronger) lower bounds could be proved for...
The Computational Complexity Column (1999)
Eric Allender, Rodney G. Downey, Michael R. Fellows, Ulrike Stege
Introduction There are two di#erent ways that one can view the theory of parameterized complexity. The easiest is as a kind of "first aid" that can sometimes be applied to problems that are NP-hard,...
The Computational Complexity Column (1999)
Introduction Investigation of the measure-theoretic structure of complexity classes began with the development of resource-bounded measure in 1991 [56]. Since that time, a growing body of research by...
Bounded Depth Arithmetic Circuits: Counting and Closure (1999)
Eric Allender, Andris Ambainis, Samir Datta, Huong Lethanh
Constant-depth arithmetic circuits have been defined and studied in [AAD97, ABL98]; these circuits yield the function classes #AC 0 and GapAC 0 . These function classes in turn provide new...
A Lower Bound for Primality (1999)
Eric Allender, Michael Saks, Igor Shparlinski
Recent work by Bernasconi, Damm and Shparlinski proved lower bounds on the circuit complexity of the square-free numbers, and raised as an open question if similar (or stronger) lower bounds could be...
Arithmetic Complexity, Kleene Closure, and Formal Power Series (1999)
Eric Allender, V Arvind, Meena Mahajan
The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC 1 and GapL. More precisely, we apply the Kleene closure of...
The Computational Complexity Column (1999)
Introduction In the beginning, there were two measures of computational complexity: time and space. From an engineering standpoint, these were very natural measures, quantifying the amount of...
Towards a Measure for P (1999)
We investigate the issues and obstacles involved in extending Lutz's notion of measure to provide a measure for P. We provide one natural definition that, under a plausible but unproven assumption,...