Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, William Gasarch, Evan Golub, ...
In the June issue Jacobo Torán will take over as editor of this column and I look forward to many exciting columns under his direction. I would like to thank Grzegorz Rozenberg who served as BEATCS...
On the complexity of numerical analysis (2009)
Eric Allender, Peter B Ürgisser, Johan Kjeldgaard-pedersen, Peter Bro Miltersen
Abstract. We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A...
We show that ACC is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar...
Reachability Problems: An Update (2008)
Abstract. There has been a great deal of progress in the fifteen years that have elapsed since Wigderson published his survey on the complexity of the graph connectivity problem [Wig92]. Most...
Cracks in the Defenses: Scouting Out Approaches on Circuit (2008)
Abstract. Razborov and Rudich identified an imposing barrier that stands in the way of progress toward the goal of proving superpolynomial lower bounds on circuit size. Their work on “natural...
Other Complexity Classes and Measures (2008)
Eric Allender, Michael C. Loui
In the previous two chapters, we have
Eric Allender, Igor Shparlinski, Michael Saks
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...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
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...
The Computational Complexity Column (2008)
With this issue of the Bulletin, my tenure as editor of the Computational Complexity Column comes to an end. Lance Fortnow will edit this column beginning with the June issue, and we can look forward...
Universidad de Buenos Aires (2008)
Facultad Ciencias, Exactas Naturales, Verónica Becher, Santiago Figueira, Daniel Gorín, Sergio Mera, ...
www.dc.uba.ar/logic2007 Sponsors Conference Address Fundación YPF
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
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...
Eric Allender, Johan Kjeldgaard-pedersen, Peter Bürgisser, Peter Bro Miltersen
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A problem we...
1 Introduction The Division Breakthroughs (2008)
All of us learn to do arithmetic in grade school. The algorithms for addition and subtraction take some time to master, and the multiplication algorithm is even more
Planar and Grid Graph Reachability Problems (2008)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. In particular, we focus on different classes of planar graphs, of which grid graphs...
We show that ACC 0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar...
Eric Allender, Johan Kjeldgaard-pedersen, Peter Bürgisser, Peter Bro Miltersen
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A problem we...
Amplifying lower bounds by means of self-reducibility (2008)
We observe that many important computational problems in NC 1 share a simple selfreducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial...
Amplifying lower bounds by means of self-reducibility (2008)
We observe that many important computational problems in NC 1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial...
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
As part of a study of almost-everywhere complex sets, we investigate sets that are immune to AC 0; that is, sets with no infinite subset in AC 0. We show that such sets exist in P PP
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)
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...
Low-Discrepancy Sets for High-Dimensional Rectangles: A Survey (2007)
Eric Allender, Aravind Srinivas
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...
News from the Isomorphism Front (2007)
The Interview Begins, Eric Allender, Ffl Graph Automorphism
this article. First, however, we will need to make a digression, while we discuss some recent progress on the isomorphism conjecture.
Recent Advances Towards Proving (2007)
Andrea Clementi Jos'e, Eric Allender, Luca Trevisan
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,...
RUSPACE(log n) \subseteq DSPACE(log² n/log log n) (2007)
Eric Allender, Klaus-Jörn Lange
We present a deterministic algorithm running in space O \Gamma log 2 n= log log n \Delta solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(log n)...
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...
StUSPACE(log n) \subseteq DSPACE(log² n/ log log n) (2007)
Eric Allender, Klaus-Jörn Lange
We present a deterministic algorithm running in space O \Gamma log 2 n= log log n \Delta solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(logn)...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)
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...
A Clari cation Concerning the #L Hierarchy (2007)
In [AO96], it is stated (without proof) that if NC 1 (#L) = AC 0 (#L), then the #L hierarchy collapses to some level. This note provides a proof of that claim. The reader is referred to[AO96] for all...
The upward separation technique was developed by Hartmanis, who used it to show that E=NE iff there is no sparse set in NP−P [15]. This paper shows some inherent limitations of the technique. The...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
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...
The low hierarchy in NP [Sc-83] and the extended low hierarchy [BBS-86] have been useful in characterizing the complexity of certain interesting classes of sets. However, until now, there have been...
Eric Allender, Distinguishing Complexity, Sambuddha Roy, Detlef Ronneburger
We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [2, 3]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt...
It has been known since the mid-1980's [16, 48, 49] that integer division can be performed by poly-time uniform circuits of Majority gates; equivalently, the division problem lies in P-uniform...
NL-printable sets and Nondeterministic Kolmogorov Complexity (2007)
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. P-printable...
Eric Allender, Michal Kouck Y, V Vinay
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...
On the Complexity of Some Arithmetic Problems over IF2[T] (2007)
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 IF2. In particular, we consider the...
The Division Breakthroughs (2007)
Sometimes the simplest problems lead to the most interesting theory. Consider the division problem, given a and b in binary, output b a
Eric Allender, Eric Allender, Catherine Mccartin, Catherine Mccartin
Abstract. 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...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)
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...
A Survey on Private Information Retrieval (2007)
Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, Evan Golub, Clyde Kruskal, ...
In the June issue Jacobo Torn will take over as editor of this column and I look forward to many exciting columns under his direction. I would like to thank Grzegorz Rozenberg who served as BEATCS...
NL-printable sets and Nondeterministic Kolmogorov Complexity (2007)
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...
1 Depth Reduction for Circuits Send proofs to the following address: (2007)
Eric Allender Y, Ulrich Hertrampf, Eric Allender
Abstract. We prove that constant depth circuits of size n logO(1) n over the basis AND, OR, PARITY are nomorepowerful than circuits of this size with depth four. Similar techniques are used to obtain...
Eric Allender, Huong Lêthanh, Andris Ambainis
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...
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Martin Mundhenk
and by the Deutsche Akademische Austauschdienst (DAAD) grant 315/PPP/gu-ab, and by NSF grants CCR-9315354, CCR-9610348, and CCR-9509603. Portions of this work were performed while at the Institute of...
Grid Graph Reachability Problems (2006)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of stconnectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since • reachability on grid graphs is...
Minimizing DNF Formulas and AC 0 Circuits Given a Truth Table (2006)
Eric Allender, Lisa Hellerstein, Paul Mccabe, Toniann Pitassi
Abstract. For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include...
Grid Graph Reachability Problems (2006)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of stconnectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since • reachability on grid graphs is...
On the complexity of numerical analysis (2006)
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-pedersen, Peter Bro Miltersen
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the...
Grid Graph Reachability Problems (2006)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of stconnectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since • reachability on grid graphs is...
On the Complexity of Numerical Analysis (2006)
Allender, Eric, Bürgisser, Peter, Kjeldgaard-Pedersen, Johan, Miltersen, Peter Bro
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the...
The directed planar reachability problem (2005)
Eric Allender, Samir Datta, Sambuddha Roy
Abstract. We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
The directed planar reachability problem (2005)
Eric Allender, Samir Datta, Sambuddha Roy
Abstract. We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is...
The complexity of satisfiability problems: refining Schaefer’s theorem (2005)
Eric Allender, Michael Baul, Neil Immerman, Henning Schnoor, Heribert Vollmer
Abstract. Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NPcomplete, and identified all tractable cases. Schaefer’s...
Arithmetic Circuits and Counting Complexity Classes (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...
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? (2004)
Eric Allender, Harry Buhrman, Michal Koucký
We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R_C. We show that...
Written under the direction of (2004)
Detlef Ronneburger, Detlef Ronneburger, Kolmogorov Complexity, Detlef Ronneburger, Eric Allender
Kolmogorov complexity is a measure that describes the compressibility of a string. Strings with low complexity contain a lot of redundancy, while strings with high Kolmogorov complexity seem to lack...
Arithmetic Complexity, Kleene Closure, and Formal Power Series (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...
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...
Power from random strings (2002)
Eric Allender, Harry Buhrman, 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...
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, 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 efficient reductions, showing that...
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...
Power from Random Strings (2002)
Eric Allender, Harry Buhrman, Michal Koucky, Dieter Van 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...
A Note on the Representational Incompatibility (2002)
Of Function Approximation, 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 circuits for division: consequences and problems (2001)
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...
Time-space tradeoffs in the counting hierarchy (2001)
Eric Allender, Michal Kouck ´y, Detlef Ronneburger, Sambuddha Roy
We extend the lower bound techniques of [14], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjaˇsčiĭ’s theorem from the Boolean setting to...
For this volume, I have combined columns I wrote for the June, 1997 and October, 1998 Bulletin. As both are brief, and the second column refers to the first, this seemed appropriate. The first column...
Power from Random Strings (2001)
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....
Reducing The Complexity Of Reductions (2001)
Manindra Agrawal, Eric Allender, Russell Impagliazzo, 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...
Time-space tradeoffs in the counting hierarchy (2001)
Eric Allender, Michal Kouck ´y, Detlef Ronneburger, Sambuddha Roy, V Vinay
We extend the lower bound techniques of [17], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjaˇsčiĭ’s theorem from the Boolean setting to...
Uniform Circuits for Division: Consequences and Problems (2000)
The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR) -- storing a number in the form of its residues modulo many...
Complexity of Finite-Horizon Markov Decision Process Problems (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Martin Mundhenk, Name Judy Goldsmith
This paper considers the computational complexity of the basic tasks facing such a controller.
Complexity of Finite-Horizon Markov Decision Process Problems (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Judy Goldsmith
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...
The Complexity of Planarity Testing (2000)
Eric Allender And, Eric Allender, Meena Mahajan
. 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 (2000)
. 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 (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
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...
The Permanent Requires Large Uniform Threshold Circuits (1999)
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...
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...
Other Complexity Classes and Measures (1999)
By Eric Allender, Eric Allender, Michael C. Loui, Kenneth W. Regan
This material was written for Chapter 29 of the CRC Handbook of Algorithms and Theory of Computation, edited by Mikhail Atallah. 1 Introduction In the previous two chapters, we have ffl introduced...
Other Complexity Classes and Measures (1999)
Eric Allender, Michael C. Loui, Kenneth W. Regan
Introduction In the previous two chapters, we have ffl introduced the basic complexity classes, ffl summarized the known relationships between these classes, and ffl seen how reducibility and...
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...
A Lower Bound for Primality (1999)
Eric Allender Dept, 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...
Isolation, Matching, and Counting: Uniform And Nonuniform (1999)
Eric Allender, Kalus Reinhardt, Klaus Reinhardt Z, 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...
Arithmetic Complexity, Kleene Closure, and Formal Power Series (1999)
Eric Allender, V. Arvind, Meena Mahajan, Gapl More Precisely
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 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...
Reducibility and Completeness (1999)
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...
Reducibility and Completeness (1999)
Eric Allender Rutgers, Eric Allender, Michael C. Loui
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...
Progress in Descriptive Complexity (1999)
Exploration of the connections between computational complexity, descriptive complexity, and logic remains one of the most active and important areas of theoretical computer science. In this edition...
Other Complexity Classes and Measures (1999)
Eric Allender, Michael 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...
Eric Allender, Andris Ambainis, Huong Lêthanh, 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...
Reductions in circuit complexity: An isomorphism theorem and a gap theorem (1998)
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...
Reductions in circuit complexity: An isomorphism theorem and a gap theorem (1998)
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...
Reductions in circuit complexity: An isomorphism theorem and a gap theorem (1998)
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...
Characterizing Small Depth and Small Space Classes by Operators of Higher Types (1998)
Manindra Agrawal Dept, 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...
The Computational Complexity Column (1998)
Eric Allender Rutgers, Eric Allender, Jack H. Lutz, Elvira Mayordomo
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...
Uniform Inclusions in Nondeterministic Logspace (1998)
We show that the complexity class LogFew is contained in NL " SPL. Previously, this was known only to hold in the nonuniform setting. Key Words: Nondeterministic Logspace Computation, Nonuniform...
The Computational Complexity Column (1998)
Eric Allender, Edith Hemaspaandra
: 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...
The Computational Complexity Column (1998)
Eric Allender Rutgers, Eric Allender, Neil Immerman
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...
The Computational Complexity Column (1998)
Eric Allender Rutgers, Eric Allender, Lower Bounds
ega\Gamma n) to compute, and also requires circuit size 2 \Omega\Gamma 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...
By Eric Allender, Eric Allender, Michael C. Loui, Kenneth W. Regan
This material was written for Chapter 27 of the CRC Handbook of Algorithms and Theory of Computation, edited by Mikhail Atallah. 1 Introduction The purposes of complexity theory are to ascertain the...
Reducibility and Completeness (1998)
By Eric Allender, Eric Allender, Michael C. Loui, Kenneth W. Regan
This material was written for Chapter 28 of the CRC Handbook of Algorithms and Theory of Computation, edited by Mikhail Atallah. 1 Introduction There is little doubt that the notion of reducibility...
The Computational Complexity Column (1998)
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...
Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds (1998)
Eric Allender, Klaus Reinhardt, Shiyu Zhon
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 Permanent Requires Large Uniform Threshold Circuits (1998)
We show that the permanent cannot be computed by uniform constantdepth threshold circuits of size T (n), for any function T such that for all k, T (k) (n) = o(2 n ). More generally, we show that any...
Recent Advances Towards Proving P=BPP (1998)
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,...
Making Nondeterminism Unambiguous (1998)
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...
The Computational Complexity Column (1998)
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...
Reducing the complexity (1997)
c○Springer-Verlag Abstract. 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...
Martin Mundhenk, Judy Goldsmith, Eric Allender
A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. POMDPs are used to...
On TC 0 ,AC 0 , and arithmetic circuits (1997)
Continuing a line of investigation that has studied the function classes #P [Val79b], #SAC 1 [Val79a, Vin91, AJMV], #L [AJ93b, Vin91, AO94], and #NC 1 [CMTV96], we study the class of functions #AC 0....
Reducing the Complexity of Reductions (1997)
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
We prove that the Berman-Hartmanis isomorphism conjecture is true under AC 0 reductions. More generally, we show three theorems that hold for any complexity class C closed under (uniform) TC 0...
Reducing the Complexity of Reductions (1997)
Manindra Agrawal Dept, Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
We prove that the Berman-Hartmanis isomorphism conjecture is true under AC 0 reductions. More generally, we show three theorems that hold for any complexity class C closed under (uniform) TC 0...
On TC^0, AC^0, and Arithmetic Circuits (1997)
Manindra Agrawal, Eric Allender, Samir Datta
Continuing a line of investigation that has studied the function classes #P [Val79b], #SAC 1 [Val79a, Vin91, AJMV], #L [AJ93b, Vin91, AO94], and #NC 1 [CMTV96], we study the class of functions #AC 0...
Eric Allender, All J. Pruim, Brenda J. Latka, Jim Rogers, Kousha Etessami
The 1995-1996 DIMACS Special Year on Logic and Algorithms began with three week-long tutorial sessions on the topics of the special year: ffl Finite Model Theory ffl Proof Complexity ffl...
DIMACS Technical Report 97-50 (1997)
Ruspace Log, Eric Allender, Klaus-jorn Lange
We present a deterministic algorithm running in space O i log 2 n= log log n j solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(log n) time-bounded...
Making Nondeterminism Unambiguous (1997)
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...
The Complexity of Matrix Rank and Feasible Systems of Linear Equations (1997)
Eric Allender, Robert Beals, M. Ogihara, Mitsunori Ogihara
We characterize 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...
Making Nondeterminism Unambiguous (1997)
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...
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
The computational complexity of finite horizon policy evaluation and policy existence problems are studied for several policy types and representations of Markov decision processes. In almost all...
Rudimentary Reductions Revisited (1997)
: We show that log-bounded rudimentary reductions (defined and studied by Jones in 1975) characterize Dlogtime-uniform AC 0 . 1 Introduction In the first part of the oft-cited paper [Jon75], Jones...
The Permanent Requires Large Uniform Threshold Circuits (1997)
A recent paper by Caussinus, McKenzie, Th'erien, and Vollmer [CMTV96] shows that there are problems in the counting hierarchy that require superpolynomial-size uniform TC 0 circuits. The proof...
Arithmetic Complexity, Kleene Closure, and Formal Power Series (1997)
Eric Allender, V. Arvind, Meena Mahajan
In this paper we show how two fundamental operations used in formal language theory provide useful tools for the investigation of arithmetic complexity classes. More precisely, we use Kleene closure...
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
The computational complexity of finite horizon policy evaluation and policy existence problems are studied for several policy types and representations of Markov decision processes. In almost all...
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997)
By Martin, Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
The computational complexity of finite horizon policy evaluation and policy existence problems are studied for several policy types and representations of Markov decision processes. In almost all...
A Clarification Concerning the #L Hierarchy (1997)
In [AO96], it is stated (without proof) that if NC 1 (#L) = AC 0 (#L), then the #L hierarchy collapses to some level. This note provides a proof of that claim. The reader is referred to [AO96] for...
Martin Mundhenk, Judy Goldsmith, Eric Allender
A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. POMDPs are used to...
Circuit Complexity before the Dawn of the New Millennium (1997)
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...
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. (1997)
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...
On TC^0, AC^0, and Arithmetic Circuits (1997)
Manindra Agrawal, Eric Allender, Samir Datta
Continuing a line of investigation that has studied the function classes #P [Val79b], #SAC 1 [Val79a, Vin91, AJMV], #L [AJ93b, Vin91, AO94], and #NC 1 [CMTV96], we study the class of functions #AC 0...
Some Pointed Questions Concerning Asymptotic Lower Bounds (1997)
This column was originally written to appear in the Bulletin of the EATCS. In this column, I survey some aspects of complexity theory that can hardly be considered "recent". Instead, I will...
Reducing the Complexity of Reductions (1997)
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
We prove that the Berman-Hartmanis isomorphism conjecture is true under AC 0 reductions. More generally, we show three theorems that hold for any complexity class C closed under (uniform) TC 0...
The complexity of unobservable finite-horizon Markov decision processes (1996)
Martin Mundhenk, Judy Goldsmith, Eric Allender
Markov Decision Processes (MDPs) model controlled stochastic systems. Like Markov chains, an MDP consists of states and probabilistic transitions; unlike Markov chains, there is assumed to be an...
An Isomorphism Theorem for Circuit Complexity (1996)
Manindra Agrawal Eric, Eric Allender
We show that all sets complete for NC 1 under AC 0 reductions are isomorphic under AC 0 -computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do...
Structure and Complexity (1996)
Uwe Schöning, Klaus W. Wagner, Farid Ablayev, Eric Allender, ...
S On the Power of Randomized Branching Programs Farid Ablayev Kazan University (joint work with Marek Karpinski, Universitat Bonn) We define a notion of randomized branching programs in a natural way...
Relationships Among PL, L, and the Determinant (1996)
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...
The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract) (1996)
Eric Allender, Robert Beals, Mitsunori Ogihara
) Eric Allender y Robert Beals z Mitsunori Ogihara x Abstract We characterize the complexity of some natural and important problems in linear algebra. In particular, we identify natural complexity...
Relationships Among PL, #L, and the Determinant (1996)
Eric Allender, Mitsunori Ogihara
Recent results by Toda, Vinay, Damm, and Valiant have shown that the complexity of the determinant is characterized by the complexity of counting the number of accepting computations of a...
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds (1996)
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay
We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...
An Isomorphism Theorem for Circuit Complexity (1996)
Manindra Agrawal, Eric Allender
We show that all sets complete for NC 1 under AC 0 reductions are isomorphic under AC 0 - computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do...
The Complexity of Matrix Rank and Feasible Systems of Linear Equations (1996)
Eric Allender, Robert Beals, Mitsunori Ogihara
We characterize 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...
Circuit Complexity before the Dawn of the New Millennium (1996)
. 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...
Circuit Complexity before the Dawn of the New Millennium (1996)
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...
Measure on P: Robustness of the Notion (1995)
In [AS], we defined 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...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Measure on P: Robustness of the Notion (1995)
In [AS], we defined 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...
Nils Klarlund, Dexter Kozen, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, ...
Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper, we introduce a...
Symmetric Logspace is Closed under Complement (1995)
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.
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
Measure on small complexity classes, with applications for BPP (1994)
We present a notion of resource-bounded measure for P and other subexponential-time classes. This gen-emlization is based on Lutz’s notion of measure, but overcomes the limitations that cause...
A uniform circuit lower bound for the permanent (1994)
Abstract. 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...
Measure on Small Complexity Classes, with Applications for BPP (1994)
We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause...
Measure on Small Complexity Classes, with Applications for BPP (1994)
The main contributions of this work are: 1. We present a notion of resource-bounded measure for P and other subexponential-time classes. This is a generalization of Lutz's notion of measure, but...
A Uniform Circuit Lower Bound for the Permanent (1994)
. 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...
A Uniform Circuit Lower Bound for the Permanent (1994)
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...
Relationships Among PL, #L, and the Determinant (1994)
Eric Allender, Mitsunori Ogihara
Recent results by Toda, Vinay, Damm, and Valiant have shown that the complexity of the determinant is characterized by the complexity of counting the number of accepting computations of a...
Depth Reduction for Circuits of Unbounded Fan-In (1994)
Ulrich Hertrampf, Eric Allender, Eric Allender
. We prove that constant depth circuits of size n log O(1) n over the basis AND, OR, PARITY are no more powerful than circuits of this size with depth four. Similar techniques are used to obtain...
Towards a Measure for P (1994)
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...
Measure on Small Complexity Classes, with Applications for BPP (1994)
We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause...
Depth Reduction for Circuits of Unbounded Fan-In (1994)
Ulrich Hertrampf, Eric Allender, Eric Allender
. We prove that constant depth circuits of size n log O(1) n over the basis AND, OR, PARITY are no more powerful than circuits of this size with depth four. Similar techniques are used to obtain...
Measure on Small Complexity Classes, with Applications for BPP (1994)
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...
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time (1993)
Eric Allender, Richard Beigel, U. Hertrampf, Ulrich Hertrampf, S. Homer
this paper, if T is time-constructible, then
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time (1993)
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer X
this paper, if is time-constructible, then #n# # for all n
A First-Order Isomorphism Theorem (1993)
Eric Allender, Jose Balcázar, Neil Immerman
We show that for most complexity classes of interest, all sets complete under first-order projections are isomorphic under first-order isomorphisms. That is, a very restricted version of the...
Depth Reduction for Noncommutative Arithmetic Circuits (1993)
) Eric Allender Department of Computer Science Princeton University 35 Olden Street Princeton, NJ, 08544-2087 allender@cs.princeton.edu Jia Jiao y Department of Computer Science Rutgers University...
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time (1993)
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
this paper, if T is time-constructible, then
The Complexity Of Computing (1993)
Maximal Word Functions, Eric Allender, Danilo Bruschi, Giovanni Pighizzini
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...
A First-Order Isomorphism Theorem (1993)
We show that for most complexity classes of interest, all sets complete under firstorder projections (fops) are isomorphic under first-order isomorphisms. That is, a very restricted version of the...
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time (1993)
Eric Allender, Richard Beigel, U. Hertrampf, Ulrich Hertrampf, S. Homer
this paper, if T is time-constructible, then
Relationships Among PL, #L, and the Determinant (1993)
Eric Allender, Mitsunori Ogiwara
Recent results by Toda, Vinay, Damm, and Valiant have shown that the complexity of the determinant is characterized by the complexity of counting the number of accepting computations of a...
The Complexity of Computing Maximal Word Functions (1993)
Eric Allender, Danilo Bruschi, Giovanni Pighizzini
. Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [21]. By the...
The Complexity of Computing Maximal Word Functions (1993)
Eric Allender, Danilo Bruschi, Giovanni Pighizzini
Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [GS]. By the...
A First-Order Isomorphism Theorem (1993)
Eric Allender, José Balcázar, Neil Immerman
We show that for most complexity classes of interest, all sets complete under firstorder projections (fops) are isomorphic under first-order isomorphisms. That is, a very restricted version of the...
A First-Order Isomorphism Theorem (1993)
We show that for most complexity classes of interest, all sets complete under firstorder projections (fops) are isomorphic under first-order isomorphisms. That is, a very restricted version of the...
Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory (1992)
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...
Relating Equivalence And Reducibility To Sparse Sets (1992)
Eric Allender, Lane A. Hemaspaandra, 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...
Relating Equivalence And Reducibility To Sparse Sets (1992)
Eric Allender Rutgers, Eric Allender, Osamu Watanabe
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...
Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory (1992)
. This paper presents one method of using time-bounded Kolmogorov complexity as a measure of the complexity of sets, and outlines a number of applications of this approach to different questions in...
Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory (1992)
. This paper presents one method of using time-bounded Kolmogorov complexity as a measure of the complexity of sets, and outlines a number of applications of this approach to different questions in...
Relating Equivalence And Reducibility To Sparse Sets (1992)
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...
Relating Equivalence and Reducibility to Sparse Sets (1991)
Allender, Eric, Hemachandra, Lane A., Ogiwara, Mitsunori, Aka Ogihara, Watanabe, Osamu
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...
Rudimentary Reductions Revisited (1991)
We show that log-bounded rudimentary reductions #de#ned and studied by Jones in 1975# characterize Dlogtime-uniform AC .
Oracles versus proof techniques that do not relativize (1990)
ABSTRACT 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....
Width-bounded reducibility and binary search over complexity classes (1990)
Eric Allender, Christopher Wilson
We introduce a notion of width-bounded reducibility. Width-bounded reducibility provides a circuit-based realization of Ruzzo-Simon-Tompa reducibility [RS-84], and allows us to generalize that notion...
Lower Bounds for the Low Hierarchy (1989)
Allender, Eric, Hemachandra, Lane A.
The low hierarchy m NP [Sc-83} and the extended low hierarchy [BBS-86] have been useful in characterizing the complexity of certain interesting classes of sets. However, until now, there have been no...
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.
Manindra Agrawal Eric, 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...
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay
We investigate the phenomenon of depth-reduction in commutativeand non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.
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...
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay
We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...