All reports by Author Eric Allender:

__
TR17-158
| 23rd October 2017
__

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan#### Minimum Circuit Size, Graph Isomorphism, and Related Problems

__
TR17-073
| 28th April 2017
__

Eric Allender, Shuichi Hirahara#### New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

__
TR17-072
| 25th April 2017
__

Eric Allender, Andreas Krebs, Pierre McKenzie#### Better Complexity Bounds for Cost Register Machines

Revisions: 1

__
TR15-162
| 9th October 2015
__

Eric Allender, Joshua Grochow, Cris Moore#### Graph Isomorphism and Circuit Size

Revisions: 1

__
TR15-145
| 5th September 2015
__

Eric Allender, Asa Goodwillie#### Arithmetic circuit classes over Zm

__
TR15-018
| 31st January 2015
__

Eric Allender, Ian Mertz#### Complexity of Regular Functions

Revisions: 1

__
TR14-176
| 16th December 2014
__

Eric Allender, Dhiraj Holden, Valentine Kabanets#### The Minimum Oracle Circuit Size Problem

__
TR14-122
| 30th September 2014
__

Eric Allender, Anna Gal, Ian Mertz#### Dual VP Classes

Revisions: 2

__
TR14-068
| 5th May 2014
__

Eric Allender, Bireswar Das#### Zero Knowledge and Circuit Minimization

Revisions: 1

__
TR13-177
| 10th December 2013
__

Eric Allender, Nikhil Balaji, Samir Datta#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

__
TR12-054
| 2nd May 2012
__

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff#### Reductions to the set of random strings:the resource-bounded case

Revisions: 1

__
TR12-028
| 30th March 2012
__

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret#### Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

Revisions: 1

__
TR12-027
| 29th March 2012
__

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang#### Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

__
TR11-083
| 22nd May 2011
__

Eric Allender, Fengming Wang#### On the power of algebraic branching programs of width two

__
TR10-139
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Limits on the Computational Power of Random Strings

Revisions: 1

__
TR10-138
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

__
TR10-070
| 17th April 2010
__

Eric Allender, Klaus-Joern Lange#### Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

__
TR10-069
| 17th April 2010
__

Eric Allender, Vikraman Arvind, Fengming Wang#### Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1
,
Comments: 1

__
TR10-055
| 31st March 2010
__

Eric Allender#### Avoiding Simplicity is Complex

Revisions: 2

__
TR09-051
| 2nd July 2009
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy#### The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

__
TR08-038
| 4th April 2008
__

Eric Allender, Michal Koucky#### Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

__
TR05-149
| 7th December 2005
__

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy#### Grid Graph Reachability Problems

Revisions: 1

__
TR05-148
| 6th December 2005
__

Eric Allender, Samir Datta, Sambuddha Roy#### The Directed Planar Reachability Problem

Revisions: 1

__
TR05-126
| 5th November 2005
__

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks#### Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

__
TR05-037
| 8th April 2005
__

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen#### On the Complexity of Numerical Analysis

Revisions: 1
,
Comments: 1

__
TR04-108
| 24th November 2004
__

Eric Allender, Samir Datta, Sambuddha Roy#### Topology inside NC^1

__
TR04-100
| 23rd November 2004
__

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer#### The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

__
TR04-044
| 1st June 2004
__

Eric Allender, Harry Buhrman, Michal Koucky#### What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

__
TR02-028
| 15th May 2002
__

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek#### Power from Random Strings

Revisions: 1

__
TR01-041
| 23rd May 2001
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay#### Time-Space Tradeoffs in the Counting Hierarchy

__
TR01-033
| 27th April 2001
__

Eric Allender, David Mix Barrington, William Hesse#### Uniform Circuits for Division: Consequences and Problems

__
TR00-065
| 7th September 2000
__

Eric Allender, David Mix Barrington#### Uniform Circuits for Division: Consequences and Problems

Comments: 2

__
TR99-012
| 19th April 1999
__

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh#### Bounded Depth Arithmetic Circuits: Counting and Closure

Comments: 1

__
TR99-010
| 1st April 1999
__

Eric Allender, Igor E. Shparlinski, Michael Saks#### A Lower Bound for Primality

Comments: 1

__
TR99-008
| 19th March 1999
__

Eric Allender, Vikraman Arvind, Meena Mahajan#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1
,
Comments: 1

__
TR98-057
| 10th September 1998
__

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

__
TR98-023
| 16th April 1998
__

Eric Allender, Shiyu Zhou#### Uniform Inclusions in Nondeterministic Logspace

__
TR98-019
| 5th April 1998
__

Eric Allender, Klaus Reinhardt#### Isolation, Matching, and Counting

__
TR97-016
| 29th April 1997
__

Manindra Agrawal, Eric Allender, Samir Datta#### On TC^0, AC^0, and Arithmetic Circuits

__
TR97-014
| 25th April 1997
__

Klaus Reinhardt, Eric Allender#### Making Nondeterminism Unambiguous

__
TR96-048
| 12th September 1996
__

Eric Allender, Klaus-Joern Lange#### StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

__
TR96-024
| 21st March 1996
__

Eric Allender, Robert Beals, Mitsunori Ogihara#### The complexity of matrix rank and feasible systems of linear equations

__
TR96-023
| 21st March 1996
__

Eric Allender#### A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

__
TR96-002
| 10th January 1996
__

Manindra Agrawal, Eric Allender#### An Isomorphism Theorem for Circuit Complexity

__
TR95-043
| 14th September 1995
__

Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay#### Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

__
TR95-028
| 9th June 1995
__

Eric Allender, Martin Strauss#### Measure on P: Robustness of the Notion

__
TR94-004
| 12th December 1994
__

Eric Allender, Martin Strauss#### Measure on Small Complexity Classes, with Applications for BPP

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>>

Eric Allender, Shuichi Hirahara

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

Eric Allender, Andreas Krebs, Pierre McKenzie

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

Eric Allender, Joshua Grochow, Cris Moore

We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied ... more >>>

Eric Allender, Asa Goodwillie

We continue the study of the complexity classes VP(Zm) and LambdaP(Zm) which was initiated in [AGM15]. We distinguish between “strict” and “lax” versions of these classes and prove some new equalities and inclusions between these arithmetic circuit classes and various subclasses of ACC^1.

more >>>Eric Allender, Ian Mertz

We give complexity bounds for various classes of functions computed by cost register automata.

more >>>Eric Allender, Dhiraj Holden, Valentine Kabanets

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP$^{QBF}$ is known to be complete for PSPACE under ZPP reductions. We show that it is not ... more >>>

Eric Allender, Anna Gal, Ian Mertz

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of

a class of high-degree polynomials that can be simulated via arithmetic circuits ...
more >>>

Eric Allender, Bireswar Das

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is

efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $C$ defined ... more >>>

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>

Eric Allender, Fengming Wang

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several

settings.

Eric Allender, Luke Friedman, William Gasarch

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

Eric Allender, Luke Friedman, William Gasarch

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>

Eric Allender, Klaus-Joern Lange

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

Eric Allender, Vikraman Arvind, Fengming Wang

A recurring theme in the literature on derandomization is that probabilistic

algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is

needed for derandomization, existing lower bounds seem rather pathetic ...
more >>>

Eric Allender

It is a trivial observation that every decidable set has strings of length $n$ with Kolmogorov complexity $\log n + O(1)$ if it has any strings of length $n$ at all. Things become much more interesting when one asks whether a similar property holds when one

considers *resource-bounded* Kolmogorov complexity. ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.

The Kolmogorov measures that have been ...
more >>>

Eric Allender, Michal Koucky

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 size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

Eric Allender, David 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. Grid graphs are a useful tool in this regard, since

* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and

* reachability on certain classes of grid graphs gives ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

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 logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

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 Min-DNF, and

Min-Circuit (also called MCSP). We begin by presenting a new reduction

proving that Min-DNF is NP-complete. It is significantly ...
more >>>

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 following problem,

which we call PosSLP:

Given a division-free straight-line program

producing an integer N, decide whether N>0.

more >>>

Eric Allender, Samir Datta, Sambuddha Roy

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 constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.

We consider other generalizations of ...
more >>>

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>>

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 efficient

reducibility to the set of Kolmogorov-random strings R_C.

We show that this question cannot be posed without explicitly dealing

with issues raised by the choice of universal

machine in the ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

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 these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>

Eric Allender, David Mix 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 DLOG-uniform

TC^0. At the time that the results in this paper were proved and

submitted for conference presentation, it was unknown whether division

lay in DLOGTIME-uniform TC^0 (also known as ...
more >>>

Eric Allender, David Mix Barrington

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

small primes. Integer division provides one of the few natural

examples of problems for which ...
more >>>

Eric Allender, Andris Ambainis, David Mix Barrington, 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

characterizations of the computational power of threshold circuits,

and provide a link between the circuit classes AC^0 ...
more >>>

Eric Allender, Igor E. Shparlinski, Michael Saks

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 proved for the set of prime numbers. In

this short note, we answer this question ...
more >>>

Eric Allender, Vikraman 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

languages and the formal power series operations of inversion and

root ...
more >>>

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 quantifying over oracles. We obtain new

characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ...
more >>>

Eric Allender, Shiyu Zhou

We show that the complexity class LogFew is contained

in NL $\cap$ SPL. Previously, this was known only to

hold in the nonuniform setting.

Eric Allender, Klaus Reinhardt

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 providing motivation for studying

the complexity class SPL.

Using similar ...
more >>>

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 is as the

class of functions computed by constant-depth polynomial-size

arithmetic circuits of unbounded fan-in addition ...
more >>>

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 context-free languages. In terms of complexity classes,

this can be stated as:

NL/poly = UL/poly

LogCFL/poly ...
more >>>

Eric Allender, Klaus-Joern Lange

We present a deterministic algorithm running in space

O((log^2 n)/loglog n) solving the connectivity problem

on strongly unambiguous graphs. In addition, we present

an O(log n) time-bounded algorithm for this problem

running on a parallel pointer machine.

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 linear equations is feasible and (b) computing the rank of

an integer matrix, ...
more >>>

Eric Allender

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer

[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0

is properly contained in the counting hierarchy. Thus, [CMTV] shows

that there are problems in ModPH that require superpolynomial-size

uniform ACC^0 ...
more >>>

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 show that, for all complexity classes C

closed under NC$^1$-computable many-one reductions, the sets ...
more >>>

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

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the ...
more >>>

Eric Allender, Martin Strauss

In (Allender and Strauss, FOCS '95), we defined a notion of

measure on the complexity class P (in the spirit of the work of (Lutz,

JCSS '92) that provides a notion of measure on complexity classes at least

as large as E, and the work of (Mayordomo, Phd. ...
more >>>

Eric Allender, Martin Strauss

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 Lutz's

definitions to apply only to classes at least as large as E. We

present many of the basic properties of this ...
more >>>