Pierre McKenzie

I&C Journal 2024 Journal Article

Perspective on complexity measures targeting read-once branching programs

• Yaqiao Li
• Pierre McKenzie

A model of computation for which reasonable yet still incomplete lower bounds are known is the read-once branching program. Here variants of complexity measures successful in the study of read-once branching programs are defined and studied. Some new or simpler proofs of known bounds are uncovered. Branching program resources and the new measures are compared extensively. The new variants are developed in part in the hope of tackling read-k branching programs for the tree evaluation problem. Other computation problems are studied as well. In particular, a common view of a function studied by Gál and a function studied by Bollig and Wegener leads to the general combinatorics of blocking sets. Technical combinatorial results of independent interest are obtained. New leads towards further progress are discussed. An exponential lower bound for non-deterministic read-k branching programs for the GEN function is also derived, independently from the new measures.

I&C Journal 2018 Journal Article

Handling infinitely branching well-structured transition systems

• Michael Blondin
• Alain Finkel
• Pierre McKenzie

Most decidability results concerning well-structured transition systems apply to the finitely branching variant. Yet some models (inserting automata, ω-Petri nets, …) are naturally infinitely branching. Here we develop tools to handle infinitely branching WSTS by exploiting the crucial property that in the (ideal) completion of a well-quasi-ordered set, downward-closed sets are finite unions of ideals. Then, using these tools, we derive decidability results and we delineate the undecidability frontier in the case of the termination, the maintainability and the coverability problems. Coverability and boundedness under new effectiveness conditions are shown decidable.

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

Does Looking Inside a Circuit Help?

• Russell Impagliazzo
• Valentine Kabanets
• Antonina Kolokolova
• Pierre McKenzie
• Shadab Romani

The Black-Box Hypothesisstates that any property of Boolean functions decided efficiently (e. g. , in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an upper bound on its circuit size. If this hypothesis is true, then P neq NP. We focus on the consequences of the hypothesis being false, showing that (under general conditions on the structure of a counterexample) it implies a non-trivial algorithm for CSAT. More specifically, we show that if there is a property F of boolean functions such that F has high sensitivity on some input function f of subexponential circuit complexity (which is a sufficient condition for F being a counterexample to the Black-Box Hypothesis), then CSAT is solvable by a subexponential-size circuit family. Moreover, if such a counterexample F is symmetric, then CSAT is in Ppoly. These results provide some evidence towards the conjecture (made in this paper) that the Black-Box Hypothesis is false if and only if CSAT is easy.

MFCS Conference 2017 Conference Paper

The Power of Programs over Monoids in DA

• Nathan Grosshans
• Pierre McKenzie
• Luc Segoufin

The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class NC^1. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame and we exhibit a regular language, recognized by a program over a monoid from J, yet not recognizable classically by morphisms from the class QJ. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.

MFCS Conference 2012 Conference Paper

The Lower Reaches of Circuit Uniformity

• Christoph Behle
• Andreas Krebs
• Klaus-Jörn Lange
• Pierre McKenzie

Abstract The effect of severely tightening the uniformity of Boolean circuit families is investigated. The impact on NC 1 and its subclasses is shown to depend on the characterization chosen for the class, while classes such as P appear to be more robust. Tightly uniform subclasses of NC 1 whose separation may be within reach of current techniques emerge.

MFCS Conference 2009 Conference Paper

Branching Programs for Tree Evaluation

• Mark Braverman
• Stephen A. Cook
• Pierre McKenzie
• Rahul Santhanam
• Dustin Wehr

Abstract The problem \(FT^{h}_{d}(k)\) consists in computing the value in [ k ] = {1, .. ., k } taken by the root of a balanced d -ary tree of height h whose internal nodes are labelled with d -ary functions on [ k ] and whose leaves are labelled with elements of [ k ]. We propose \({FT^{h}_{d}(k)}\) as a good candidate for witnessing \({\mathbf{L}} \subsetneq{\mathbf{LogDCFL}}\). We observe that the latter would follow from a proof that k -way branching programs solving \({FT^{h}_{d}(k)}\) require \(\Omega(k^{\mbox{\scriptsize unbounded function}(h)})\) size. We introduce a “state sequence” method that can match the size lower bounds on \(FT^{h}_{d}(k)\) obtained by the Nec̆iporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ( k 3 ) and Θ( k 5/2 ) for deterministic and nondeterministic branching programs solving \(FT^{3}_{2}(k)\) respectively. We propose as a challenge to break the quadratic barrier inherent in the Nec̆iporuk method by adapting the state sequence method to handle \(FT^{4}_{d}(k)\).

MFCS Conference 2009 Conference Paper

Few Product Gates But Many Zeros

• Bernd Borchert
• Pierre McKenzie
• Klaus Reinhardt

Abstract A d-gem is a { +, −, ×}-circuit having very few ×-gates and computing from { x } ∪ ℤ a univariate polynomial of degree d having d distinct integer roots. We introduce d -gems because they could help factoring integers and because their existence for infinitely many d would blatantly disprove a variant of the Blum-Cucker-Shub-Smale conjecture. A natural step towards validating the conjecture would thus be to rule out d -gems for large d. Here we construct d -gems for several values of d up to 55. Our 2 n -gems for n ≤ 4 are skew, that is, each { +, − }-gate adds an integer. We prove that skew 2 n -gems if they exist require n { +, − }-gates, and that these for n ≥ 5 would imply new solutions to the Prouhet-Tarry-Escott problem in number theory. By contrast, skew d -gems over the real numbers are shown to exist for every d.

TCS Journal 2009 Journal Article

The complexity of Solitaire

• Luc Longpré
• Pierre McKenzie

Klondike is the well-known 52-card Solitaire game available on almost every computer. The problem of determining whether an n -card Klondike initial configuration can lead to a win is shown NP -complete. The problem remains NP -complete when only three suits are allowed instead of the usual four. When only two suits of opposite color are available, the problem is shown NL -hard. When the only two suits have the same color, two restrictions are shown in AC 0 and in NL respectively. When a single suit is allowed, the problem drops in complexity down to AC 0 [3], that is, the problem is solvable by a family of constant-depth unbounded-fan-in {and, or, mod3 }-circuits. Other cases are studied: for example, “no King” variant with an arbitrary number of suits of the same color and with an empty “pile” is NL -complete.

CSL Conference 2008 Conference Paper

Extensional Uniformity for Boolean Circuits

• Pierre McKenzie
• Michael Thomas 0001
• Heribert Vollmer

Abstract Imposing an extensional uniformity condition on a non-uniform circuit complexity class \(\mathcal{C}\) means simply intersecting \(\mathcal{C}\) with a uniform class \(\mathcal{L}\). By contrast, the usual intensional uniformity conditions require that a resource-bounded machine be able to exhibit the circuits in the circuit family defining \(\mathcal{C}\). We say that \((\mathcal{C}, \mathcal{L})\) has the Uniformity Duality Property if the extensionally uniform class \(\mathcal{C}\cap\mathcal{L}\) can be captured intensionally by means of adding so-called \(\mathcal{L}\) -numerical predicates to the first-order descriptive complexity apparatus describing the connection language of the circuit family defining \(\mathcal{C}\). This paper exhibits positive instances and negative instances of the Uniformity Duality Property.

MFCS Conference 2007 Conference Paper

The Complexity of Solitaire

• Luc Longpré
• Pierre McKenzie

Abstract Klondike is the well-known 52-card Solitaire game available on almost every computer. The problem of determining whether an n -card Klondike initial configuration can lead to a win is shown NP-complete. The problem remains NP-complete when only three suits are allowed instead of the usual four. When only two suits of opposite color are available, the problem is shown NL-hard. When the only two suits have the same color, two restrictions are shown in AC 0 and in NL respectively. When a single suit is allowed, the problem drops in complexity down to AC 0 [3], that is, the problem is solvable by a family of constant depth unbounded fan-in { and, or, mod 3 }-circuits. Other cases are studied: for example, “no King” variant with an arbitrary number of suits of the same color and with an empty “pile” is NL-complete.

I&C Journal 2004 Journal Article

A well-structured framework for analysing petri net extensions

• Alain Finkel
• Pierre McKenzie
• Claudine Picaronny

Transition systems defined from recursive functions IN p → IN p are introduced and named WSNs, or well-structured nets. Such nets sit conveniently between Petri net extensions and general transition systems. In the first part of this paper, we study decidability properties of WSN classes obtained by imposing natural restrictions on their defining functions, with respect to termination, coverability, and four variants of the boundedness problem. We are able to precisely answer almost all the questions which arise, thus gaining much insight into old and new generalized Petri net decidability results. In the second part, we specialize our analysis to WSNs defined from affine functions, which elegantly encompass most Petri net extensions studied in the literature. Again, we study decidability properties of natural classes of affine WSN with respect to the above six computational problems. In particular, we develop an algorithm computing limits of iterated nonnegative affine functions, in order to decide the path-place variant of the boundedness problem for non-negative affine WSN.

TCS Journal 2003 Journal Article

Alternating and empty alternating auxiliary stack automata

• Markus Holzer
• Pierre McKenzie

We consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. In this way we get new characterizations of NP, the polynomial hierarchy, PSpace, and bounded query classes like co-DP = NL 〈 NP [1]〉 and Θ 2 P = P NP [O(log n)], in a uniform framework.

MFCS Conference 2000 Conference Paper

Alternating and Empty Alternating Auxiliary Stack Automata

• Markus Holzer 0001
• Pierre McKenzie

Abstract We consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. In this way we get new characterizations of NP, the polynomial hierarchy, PSpace, and bounded query classes like NL 〈 NP [1]〉 and Θ 2 P = P NP [O(logn)], in a uniform framework.

MFCS Conference 2000 Conference Paper

Equation Satisfiability and Program Satisfiability for Finite Monoids

• David A. Mix Barrington
• Pierre McKenzie
• Cristopher Moore
• Pascal Tesson
• Denis Thérien

Abstract We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [ 4 ] by exhibiting quasi-polynomial time algorithms for a subclass of solvable non-nilpotent groups and relate this question to a natural circuit complexity conjecture. In the special case when M is aperiodic, we show that PROGRAM SATISFIABILITY is in P when the monoid belongs to the variety DA and is NP-complete otherwise. In contrast, we give an example of an aperiodic outside DA for which EQUATION SATISFIABILITY is computable in polynomial time and discuss the relative complexity of the two problems. We also study the closure properties of classes for which these problems belong to P and the extent to which these fail to form algebraic varieties.

FOCS Conference 1997 Conference Paper

Separation of the Monotone NC Hierarchy

• Ran Raz
• Pierre McKenzie

We prove tight lower bounds, of up to n/sup /spl epsiv//, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. Monotone-NC/spl ne/monotone-P. 2. /spl forall/i/spl ges/1, monotone-NC/sup i//spl ne/monotone-NC/sup i+1/. 3. More generally: For any integer function D(n), up to n/sup /spl epsiv// (for some /spl epsiv/>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const/spl middot/D(n) (for some constant Const). Only a separation of monotone-NC/sup 1/ from monotone-NC/sup 2/ was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of-this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1. For st-connectivity, we get a tight lower bound of /spl Omega/(log/sup 2/ n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-clique function, with k/spl les/n/sup /spl epsiv//, we get a tight lower bound of /spl Omega/(k log n). Only a bound of /spl Omega/(k) was previously known.

TCS Journal 1997 Journal Article

Verifying identical communicating processes is undecidable

• Alain Finkel
• Pierre McKenzie

We prove that boundedness and reachability tree finiteness are undecidable for systems of two identical automata communicating via two perfect unbounded one-way FIFO channels and constructed solely from cycles about their initial states. Using a form of mutual exclusion for such systems, we prove further that undecidability holds even when the identical automata are totally indistinguishable in the sense that their initial states are identical and both channels are initially empty.

I&C Journal 1996 Journal Article

Logspace and Logtime Leaf Languages

• Birgit Jenner
• Pierre McKenzie
• Denis Thérien

The computation tree of a nondeterministic machineMwith inputxgives rise to aleaf stringformed by concatenating the outcomes of all the computations in the tree in lexicographical order. We may characterize problems by considering, for a particular “leaf language”Y, the set of allxfor which the leaf string ofMis contained inY. In this way, in the context of polynomial time computation, leaf languages were shown to capture many complexity classes. In this paper, we study the expressibility of the leaf language mechanism in the contexts of logarithmic space and of logarithmic time computation. We show that logspace leaf languages yield a much finer classification scheme for complexity classes than polynomial time leaf languages, capturing also many classes withinP. In contrast, logtime leaf languages basically behave like logtime reducibilities. Both cases are more subtle to handle than the polynomial time case. We also raise the issue of balanced versus nonbalanced computation trees underlying the leaf language. We indicate that it is a nontrivial problem to obtain information about the leaf string of a nonbalanced computation tree and present conditions under which it does not matter whether the computation tree is balanced or not.

TCS Journal 1993 Journal Article

Extensions to Barrington's M-program model

• François Bédard
• François Lemieux
• Pierre McKenzie

Barrington's “polynomal-length program over a monoid” is a model of computation which has been studied intensively in connection with the structure of the complexity class NC1 [Barrington (1986), Barrington and Thérien (1987, 1988), McKenzie and Thérien (1989), Péladeau (1989)]. Here two extensions of the model are considered. First, with the use of nonassociative structures (hence, groupoids) instead of (associative) monoids, polynomial-length program characterizations of complexity classes TC0, NL, and LOGCFL, as well as new characterizations of NC1, are given. New “word problems” complete for LOGCFL, for NL and for NC1 under DLOGTIME-reductions are obtained as corollaries. Second, using monoids but permitting the use of a different monoid to handle each input length, new complexity classes are defined. Combinatorial arguments are then developed to resolve the relationships between various such classes defined in terms of polynomial-length programs over growing abelian monoid sequences. Then the orders of growing abelian group and monoid sequences required to accept specific languages defined in terms of the presence of a given substring are investigated. Finally, the two extensions are combined to obtain characterizations of L and NL in terms of polynomial-length programs defined over polynomially growing groupoid sequences. It is further argued that such programs are generally no more powerful than LOGCFL.

I&C Journal 1991 Journal Article

Oracle branching programs and Logspace versus P

• David A.Mix Barrington
• Pierre McKenzie

We define the notion of an oracle branching program in order to investigate space-bounded computation. Within this new framework we examine the P-complete problem GEN which consists of determining membership in a subalgebra of a general (not necessarily associative) binary algebra (input as a multiplication table). Our work begins with the statement of a conceptually simple conjecture highlighting the combinatorics which underlie the relationship between Logspace and P. We show that natural subclasses of P can be expressed as natural subproblems for GEN. Finally, we prove optimal lower bounds on the size of branching programs for GEN with certain natural oracles.

MFCS Conference 1989 Conference Paper

Oracle Branching Programs and Logspace versus P

• David A. Mix Barrington
• Pierre McKenzie

FOCS Conference 1985 Conference Paper

Fast Parallel Computation with Permutation Groups

• Eugene M. Luks
• Pierre McKenzie

We develop fast parallel solutions to a number of basic problems involving solvable and nilpotent permutation groups. Testing solvability is in NC, and RNC includes, for solvable groups, finding order, testing membership, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in RNC, find the center, a central composition series, and point-wise stabilizers of sets. There are applications to graph isomorphism. In fact, we exhibit a class of vertex-colored graphs for which determining isomorphism is NC-equivalent to computing ranks of matrices Over small fields. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to RNC.

FOCS Conference 1983 Conference Paper

The Parallel Complexity of the Abelian Permutation Group Membership Problem

• Pierre McKenzie
• Stephen A. Cook

We show that the permutation group membership problem can be solved in depth (logn)3 on a Monte Carlo Boolean circuit of polynomial size in the restricted case in which the group is abelian. We also show that this restricted problem is NC1-hard for NSPACE(logn).