Eric Allender

TCS Journal 2023 Journal Article

Cryptographic hardness under projections for time-bounded Kolmogorov complexity

• Eric Allender
• John Gouwar
• Shuichi Hirahara
• Caleb Robelle

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP -Turing reductions; neither is known to be NP -complete. Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P ) under nonuniform ≤ m NC 0 reductions. In this paper, we improve this, to show that MKTP ‾ is hard for the (apparently larger) class NISZK L under not only ≤ m NC 0 reductions but even under projections. Also MKTP ‾ is hard for NISZK under ≤ m P / poly reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK L is the non-interactive version of the class SZK L that was studied by Dvir et al. As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP ).

MFCS Conference 2021 Conference Paper

Depth-First Search in Directed Planar Graphs, Revisited

• Eric Allender
• Archit Chauhan
• Samir Datta

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.

MFCS Conference 2017 Conference Paper

Better Complexity Bounds for Cost Register Automata

• Eric Allender
• Andreas Krebs
• Pierre McKenzie

Cost register automata (CRAs) 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 tropical semiring (N U {infinity}, \min, +) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC^1 when the semiring is (Z, +, x) or (Gamma^*, max, concat). This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC^1 versus GapNC^1.

MFCS Conference 2017 Conference Paper

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

• 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) within a factor of n^{1 - o(1)} is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function. We also prove that MKTP is hard for the complexity class DET under non-uniform NC^0 reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of "local" reductions such as NC^0 reductions. We exploit this local reduction to obtain several new consequences: * MKTP is not in AC^0[p]. * Circuit size lower bounds are equivalent to hardness of a relativized version MKTP^A of MKTP under a class of uniform AC^0 reductions, for a large class of sets A. * Hardness of MCSP^A implies hardness of MKTP^A for a wide class of sets A. This is the first result directly relating the complexity of MCSP^A and MKTP^A, for any A.

I&C Journal 2017 Journal Article

Zero knowledge and circuit minimization

• 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 problems share, as candidate NP -intermediate problems.

I&C Journal 2013 Journal Article

Limits on the computational power of random strings

• Eric Allender
• Luke Friedman
• William Gasarch

How powerful is the set of random strings? What can one say about a set A that is efficiently reducible to R, the set of Kolmogorov-random strings? We present the first upper bound on the class of computable sets in P R and NP R. The two most widely-studied notions of Kolmogorov complexity are the “plain” complexity C ( x ) and “prefix” complexity K ( x ); this gives rise to two common ways to define the set of random strings “R”: R C and R K. (Of course, each different choice of universal Turing machine U in the definition of C and K yields another variant R C U or R K U.) Previous work on the power of “R” (for any of these variants) has shown: • BPP ⊆ { A: A ⩽ tt p R }. • PSPACE ⊆ P R. • NEXP ⊆ NP R. Since these inclusions hold irrespective of low-level details of how “R” is defined, and since BPP, PSPACE and NEXP are all in Δ 1 0 (the class of decidable languages), we have, e. g. : NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U. Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to R K U. We show: • BPP ⊆ Δ 1 0 ∩ ⋂ U { A: A ⩽ tt p R K U } ⊆ PSPACE. • NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U ⊆ EXPSPACE. Hence, in particular, PSPACE is sandwiched between the class of sets polynomial-time Turing- and truth-table-reducible to R. As a side-product, we obtain new insight into the limits of techniques for derandomization from uniform hardness assumptions.

MFCS Conference 2012 Conference Paper

Reductions to the Set of Random Strings: The Resource-Bounded Case

• Eric Allender
• Harry Buhrman
• Luke Friedman
• Bruno Loff

Abstract This paper is motivated by a conjecture [1, 5] 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 in [5] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead. We show that if a set A is reducible in polynomial time to the set of time- t -bounded Kolmogorov-random strings (for all large enough time bounds t ), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.

TCS Journal 2006 Journal Article

NL-printable sets and nondeterministic Kolmogorov complexity

• Eric Allender

P-printable sets were defined by Hartmanis and Yesha and have been investigated by several researchers. The analogous notion of L-printable sets was defined by Fortnow et al. ; both P-printability and L-printability were shown to be related to notions of resource-bounded Kolmogorov complexity. Nondeterministic logspace (NL)-printability was defined by Jenner and Kirsig, but some basic questions regarding this notion were left open. In this paper we answer a question of Jenner and Kirsig by providing a machine-based characterization of the NL-printable sets. In order to relate NL-printability to resource-bounded Kolmogorov complexity, the paper introduces nondeterministic space-bounded Kolmogorov complexity. We present some of the basic properties of this notion of Kolmogorov complexity. Using similar techniques, we investigate relationships among classes between NL and UL.

MFCS Conference 2005 Conference Paper

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

• Eric Allender
• Michael Bauland
• 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 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 distinct if and only if P ≠ NP). We show that if one considers AC 0 isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).

I&C Journal 2004 Journal Article

The complexity of planarity testing

• 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 L=SL. The upper bound of SL matches the lower bound of L in the context of (nonuniform) circuit complexity, since L /poly is equal to SL /poly. Similarly, we show that a planar embedding, when one exists, can be found in FL SL. Previously, these problems were known to reside in the complexity class AC 1, via the O(logn) time CRCW PRAM algorithm of Ramachandran and Reif, although planarity checking for degree-three graphs had been shown to be in SL [Chicago J. Theoret. Comput. Sci. (1995); J. ACM 31 (2) (1984) 401].

NeurIPS Conference 2002 Conference Paper

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics

• Eric Allender
• Sanjeev Arora
• Michael Kearns
• Cristopher Moore
• Alexander Russell

We establish a new hardness result that shows that the difficulty of plan- ning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed family of fac- tored MDPs with linear rewards whose optimal policies and value func- tions simply cannot be represented succinctly in any standard parametric form. Previous hardness results indicated that computing good policies from the MDP parameters was difficult, but left open the possibility of succinct function approximation for any fixed factored MDP. Our result applies even to policies which yield a polynomially poor approximation to the optimal value, and highlights interesting connectionswith the com- plexity class of Arthur-Merlin games.

FOCS Conference 2002 Conference Paper

Power from Random Strings

• Eric Allender
• Harry Buhrman
• Michal Koucký 0001
• 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 sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.

TCS Journal 1998 Journal Article

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 logarithmic depth are as powerful as uniform arithmetic circuits of polynomial degree (and unrestricted depth); earlier proofs did not work in the uniform setting. This also provides a unified proof of the circuit characterizations of the class LOGCFL and its counting variant #LOGCFL. We show that AC1 has no more power than arithmetic circuits of polynomial size and degree n O(log log n) (improving the trivial bound of n O(log n)). Connections are drawn between TC1 and arithmetic circuits of polynomial size and degree. Then we consider non-commutative computation. We show that over the algebra (∑∗, max, concat), arithmetic circuits of polynomial size and polynomial degree can be reduced to O(log 2 n) depth (and even to O(log n) depth if unbounded-fanin gates are allowed). This establishes that OptLOGCFL is in AC1. This is the first depth-reduction result for arithmetic circuits over a non-commutative semiring, and it complements the lower bounds of Kosaraju and Nisan showing that depth reduction cannot be done in the general non-commutative setting. We define new notions called “short-left-paths” and “short-right-paths” and we show that these notions provide a characterization of the classes of arithmetic circuits for which optimal depth reduction is possible. This class also can be characterized using the AuxPDA model. Finally, we characterize the languages generated by efficient circuits over the semiring (2∑∗, union, concat) in terms of simple one-way machines, and we investigate and extend earlier lower bounds on non-commutative circuits.

FOCS Conference 1997 Conference Paper

Making Nondeterminism Unambiguous

• 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=UAuxPDA(log n, n/sup O(1)/)/poly.

STOC Conference 1997 Conference Paper

Reducing the Complexity of Reductions

• Manindra Agrawal
• Eric Allender
• Russell Impagliazzo
• Toniann Pitassi
• Steven Rudich

MFCS Conference 1997 Conference Paper

The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes

• Martin Mundhenk
• Judy Goldsmith
• Eric Allender

Abstract 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. We consider several flavors of finite-horizon POMDPs. Our results concern the complexity of the policy evaluation and policy existence problems, which are characterized in terms of completeness for complexity classes. We prove a new upper bound for the policy evaluation problem for POMDPs, showing it is complete for Probabilistic Logspace. From this, we prove policy existence problems for several variants of unobservable, succinctly represented MDPs to be complete for NP PP, a class for which not many natural problems are known to be complete.

STOC Conference 1996 Conference Paper

The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract)

• Eric Allender
• Robert Beals
• Mitsunori Ogihara

MFCS Conference 1995 Conference Paper

Measure on P: Robustness of the Notion

• Eric Allender
• Martin J. Strauss

Abstract 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 of Mayordomo [M] that provides a measure on PSPACE). In this paper, we show that several other ways of defining measure in terms of covers and martingales yield precisely the same notion as in [AS]. (Similar “robustness” results have been obtained previously for the notions of measure defined by [L92] and [M], but — for reasons that will become apparent below — different proofs are required in our setting.) To our surprise, and in contrast to the measures of Lutz [L92] and Mayordomo.

FOCS Conference 1994 Conference Paper

Measure on Small Complexity Classes, with Applications for BPP

• Eric Allender
• Martin J. 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 measure, and use it to explore the class of sets that are hard for BPP. Bennett and Gill showed that almost all sets are hard for BPP; Lutz improved this from Lebesgue measure to measure on ESPACE. We use our measure to improve this still further, showing that for all /spl epsiv/>0, almost every set in E/sub /spl epsiv// is hard for BPP, where E/sub /spl epsiv//=/spl cup//sub /spl delta/>

TCS Journal 1993 Journal Article

Almost-everywhere complexity hierarchies for nondeterministic time

• Eric Allender
• Richard Beigel
• Ulrich Hertrampf
• Steven Homer

We present an almost-everywhere complexity hierarchy for nondeterministic time, and show that it is essentially the best result of this sort that can be proved using relativizable proof techniques.

STOC Conference 1993 Conference Paper

Depth reduction for noncommutative arithmetic circuits

• Eric Allender
• Jia Jiao

TCS Journal 1990 Journal Article

Downward translations of equality

• Eric Allender
• Christopher Wilson

In this paper we construct oracles relative to which DTIME(T(n)) equals NTIME(T(n)) and DTIME(t(n)) does not equal NTIME (t(n)), for t(n) sufficiently smaller than T(n). A stronger result than this is also obtained, though for fewer T(n), expressedin two parts. For T(n)⩽2 n, there is an oracle relative to which DTIME(T(n)) equals NTIME(T(n)) and NTIME(2n) contains a set not in DTIME(t(n)) for any t(n) growing more slowly than T(n). For T(n)⩽22 n+0(1), there is an oracle relative to which DTIME(T(n)) equals NTIME(T(n)) and NTIME(log T(n)) contains a set not in DTIME(t(n)) for t(n) growing more slowly than T(n). These results expand on those obtained by Dekhtyar (1976), Book et al. (1982), and Allender (1989).

I&C Journal 1990 Journal Article

Kolmogorov complexity and degrees of tally sets

• Eric Allender
• Osamu Watanabe

We show that either Ep m(TALLY)=Ep btt(TALLY) or Ep m(TALLY)⊂Ep 1−tt(TALLY)⊂Ep 2−tt(TALLY)⊂Ep 3−tt(TALLY)…, where E r p (TALLY) denotes the class of sets which are equivalent to a tally set under ≤r p reductions. Furthermore, the question of whether or not E m p (TALLY) = E btt p (TALLY) is equivalent to the question of whether or not NE predicates can be solved in deterministic exponential time. The proofs use the techniques of generalized Kolmogorov complexity. As corollaries to some of the main results, we obtain new results about the Kolmogorov complexity of sets in P.

MFCS Conference 1990 Conference Paper

On the Power of Uniform Families of Constant Depth Treshold Circuits

• Eric Allender
• Ulrich Hertrampf

Abstract We prove that every set in uniform-AC 0 can be recognized by a uniform family of depth-three threshold circuits of size \(n^{log^{O(1)} n}\).

FOCS Conference 1989 Conference Paper

A Note on the Power of Threshold Circuits

• Eric Allender

The author presents a very simple proof of the fact that any language accepted by polynomial-size depth-k unbounded-fan-in circuits of AND and OR gates is accepted by depth-three threshold circuits of size n raised to the power O(log/sup k/n). The proof uses much of the intuition of S. Toda's result that the polynomial hierarchy is contained in P/sup Hash P/ (30th Ann. Symp. Foundations Comput. Sci. , p. 514-519, 1989). >

STOC Conference 1987 Conference Paper

Some Consequences of the Existence of Pseudorandom Generators

• Eric Allender

If secure pseudorandom generators exist, then probabilistic computation does not uniformly speed up deterministic computation. If sets in P must contain infinitely many noncomplex strings, then nondeterministic computation does not uniformly speed up deterministic computation. Connections are drawn between pseudorandom generation, generalized Kolmogorov complexity, and immunity properties of complexity classes.

TCS Journal 1985 Journal Article

Improved lower bounds for the cycle detection problem

• Eric Allender
• Maria M. Klawe

Lower bounds for the ‘cycle detection problem’ were recently investigated by Fich (1981, 1983). She showed that Floyd's algorithm was optimal among those algorithms which have M = 2 memory locations and which make a finite number of ‘jumps’. A lower bound for the case where M > 2 was also presented, but the question of whether having more than two memory locations could actually yield a better algorithm was left open. In this report, we show that it cannot. A lower bound was also presented by Fich (1981, 1983) for algorithms which have two memory locations and which make a finite number of ‘back advances’. We show here that the same lower bound holds even if the restriction on back advances is dropped.