Pierre McKenzie

115 papers A* 8A 8B 13C 1Misc 4Journal 65Unranked 12
YearRankTypeTitle / Venue / Authors
2024 J jnl
Perspective on complexity measures targeting read-once branching programs.
Inf. Comput.
Yaqiao Li, Pierre McKenzie
2023 J jnl
Catalytic Branching Programs from Groups and General Protocols.
ACM Trans. Comput. Theory
Hugo Côté, Pierre McKenzie
2023 — ch.
Pebbles and Branching Programs for Tree Evaluation.
Logic, Automata, and Computational Complexity
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2023 J jnl
Perspective on complexity measures targetting read-once branching programs.
CoRR
Yaqiao Li, Pierre McKenzie
2023 — ch.
Towards a Complexity Theory of Parallel Computation.
Logic, Automata, and Computational Complexity
Paul Beame, Pierre McKenzie
2022 J jnl
Tameness and the power of programs over monoids in DA.
Log. Methods Comput. Sci.
Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2021 J jnl
Tameness and the power of programs over monoids in DA.
CoRR
Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2021 J jnl
The Reachability Problem for Two-Dimensional Vector Addition Systems with States.
J. ACM
Michael Blondin, Matthias Englert, Alain Finkel, Stefan Göller, Christoph Haase, Ranko Lazic, Pierre McKenzie, Patrick Totzke
2019 J jnl
Better Complexity Bounds for Cost Register Automata.
Theory Comput. Syst.
Eric Allender, Andreas Krebs, Pierre McKenzie
2018 J jnl
Handling infinitely branching well-structured transition systems.
Inf. Comput.
Michael Blondin, Alain Finkel, Pierre McKenzie
2018 J jnl
The Algebraic Theory of Parikh Automata.
Theory Comput. Syst.
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2017 B conf
Better Complexity Bounds for Cost Register Automata.
MFCS
Eric Allender, Andreas Krebs, Pierre McKenzie
2017 J jnl
Better Complexity Bounds for Cost Register Machines.
Electron. Colloquium Comput. Complex.
Eric Allender, Andreas Krebs, Pierre McKenzie
2017 J jnl
Does Looking Inside a Circuit Help?
Electron. Colloquium Comput. Complex.
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
2017 B conf
Does Looking Inside a Circuit Help?.
MFCS
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
2017 A* ed.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017
STOC
Hamed Hatami, Pierre McKenzie, Valerie King
2017 B conf
The Power of Programs over Monoids in DA.
MFCS
Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2017 J jnl
Well Behaved Transition Systems.
Log. Methods Comput. Sci.
Michael Blondin, Alain Finkel, Pierre McKenzie
2016 J jnl
Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method.
ACM Trans. Comput. Theory
Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2016 J jnl
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method.
CoRR
Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
2016 J jnl
On Generalized Addition Chains.
CoRR
Yara Elias, Pierre McKenzie
2016 J jnl
The complexity of intersecting finite automata having few final states.
Comput. Complex.
Michael Blondin, Andreas Krebs, Pierre McKenzie
2016 J jnl
Well Behaved Transition Systems.
CoRR
Michael Blondin, Alain Finkel, Pierre McKenzie
2015 A* conf
Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete.
LICS
Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, Pierre McKenzie
2014 — conf
Extremely uniform branching programs.
NCMA
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2014 — conf
Handling Infinitely Branching WSTS.
ICALP (2)
Michael Blondin, Alain Finkel, Pierre McKenzie
2014 J jnl
On Generalized Addition Chains.
Integers
Yara Elias, Pierre McKenzie
2014 J jnl
Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141).
Dagstuhl Reports
Javier Esparza, Alain Finkel, Pierre McKenzie, Joël Ouaknine
2014 J jnl
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete.
CoRR
Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, Pierre McKenzie
2013 — conf
Can Chimps Go It Alone?
DCFS
Pierre McKenzie
2013 J jnl
Few Product Gates but Many Zeroes.
Chic. J. Theor. Comput. Sci.
Bernd Borchert, Pierre McKenzie, Klaus Reinhardt
2013 — conf
The Algebraic Theory of Parikh Automata.
CAI
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2013 J jnl
The Algebraic Theory of Parikh Automata.
Electron. Colloquium Comput. Complex.
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2013 J jnl
Unambiguous constrained Automata.
Int. J. Found. Comput. Sci.
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2012 J jnl
Affine Parikh automata.
RAIRO Theor. Informatics Appl.
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2012 J jnl
Bounded Parikh Automata.
Int. J. Found. Comput. Sci.
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2012 J jnl
Pebbles and Branching Programs for Tree Evaluation.
ACM Trans. Comput. Theory
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2012 Misc conf
The Complexity of Intersecting Finite Automata Having Few Final States.
CSR
Michael Blondin, Pierre McKenzie
2012 J jnl
The Complexity of Intersecting Finite Automata Having Few Final States.
Electron. Colloquium Comput. Complex.
Michael Blondin, Andreas Krebs, Pierre McKenzie
2012 B conf
The Lower Reaches of Circuit Uniformity.
MFCS
Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
2012 C conf
Unambiguous Constrained Automata.
Developments in Language Theory
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2011 — conf
Bounded Parikh Automata
WORDS
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2011 J jnl
Low uniform versions of NC1.
Electron. Colloquium Comput. Complex.
Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
2011 — conf
On the Expressiveness of Parikh Automata and Related Models.
NCMA
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2011 J jnl
Storming the Parikh Automaton
CoRR
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
2010 J jnl
Extensional Uniformity for Boolean Circuits.
SIAM J. Comput.
Pierre McKenzie, Michael Thomas, Heribert Vollmer
2010 J jnl
Pebbles and Branching Programs for Tree Evaluation
CoRR
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2010 Misc conf
The Computational Complexity of RaceTrack.
FUN
Markus Holzer, Pierre McKenzie
2009 B conf
Branching Programs for Tree Evaluation.
MFCS
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009 B conf
Few Product Gates But Many Zeros.
MFCS
Bernd Borchert, Pierre McKenzie, Klaus Reinhardt
2009 — conf
Fractional Pebbling and Thrifty Branching Programs.
FSTTCS
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009 J jnl
The complexity of Solitaire.
Theor. Comput. Sci.
Luc Longpré, Pierre McKenzie
2008 J jnl
Extensional Uniformity for Boolean Circuits
CoRR
Pierre McKenzie, Michael Thomas, Heribert Vollmer
2008 B conf
Extensional Uniformity for Boolean Circuits.
CSL
Pierre McKenzie, Michael Thomas, Heribert Vollmer
2008 J jnl
Incremental Branching Programs.
Theory Comput. Syst.
Anna Gál, Michal Koucký, Pierre McKenzie
2008 J jnl
Worst Case Nonzero-Error Interactive Communication.
IEEE Trans. Inf. Theory
Hugues Mercier, Pierre McKenzie, Stefan Wolf
2007 J jnl
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.
Comput. Complex.
Pierre McKenzie, Klaus W. Wagner
2007 B conf
The Complexity of Solitaire.
MFCS
Luc Longpré, Pierre McKenzie
2006 J jnl
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].
J. Comput. Syst. Sci.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
2006 Misc conf
Incremental Branching Programs.
CSR
Anna Gál, Michal Koucký, Pierre McKenzie
2006 — conf
Incremental branching programs.
Complexity of Boolean Functions
Anna Gál, Pierre McKenzie, Michal Koucký
2006 J jnl
The many faces of a translation.
J. Comput. Syst. Sci.
Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
2005 J jnl
Incremental branching programs
Electron. Colloquium Comput. Complex.
Anna Gál, Michal Koucký, Pierre McKenzie
2005 B conf
Worst-case randomized interactive communication.
ISIT
Hugues Mercier, Pierre McKenzie, Stefan Wolf
2004 J jnl
A well-structured framework for analysing petri net extensions.
Inf. Comput.
Alain Finkel, Pierre McKenzie, Claudine Picaronny
2004 J jnl
Arithmetic Circuits and Polynomial Replacement Systems.
SIAM J. Comput.
Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner
2003 J jnl
Alternating and empty alternating auxiliary stack automata.
Theor. Comput. Sci.
Markus Holzer, Pierre McKenzie
2003 J jnl
Completeness results for graph isomorphism.
J. Comput. Syst. Sci.
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
2003 A conf
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers.
STACS
Pierre McKenzie, Klaus W. Wagner
2002 J jnl
The complexity of tensor calculus.
Comput. Complex.
Carsten Damm, Markus Holzer, Pierre McKenzie
2001 J jnl
On the Complexity of Some Problems on Groups Input as Multiplication Tables.
J. Comput. Syst. Sci.
David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie
2001 — book
Systems and Software Verification, Model-Checking Techniques and Tools.
Béatrice Bérard, Michel Bidoit, Alain Finkel, François Laroussinie, Antoine Petit, Laure Petrucci, Philippe Schnoebelen, Pierre McKenzie
2001 J jnl
The Descriptive Complexity Approach to LOGCFL.
J. Comput. Syst. Sci.
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
2000 B conf
Alternating and Empty Alternating Auxiliary Stack Automata.
MFCS
Markus Holzer, Pierre McKenzie
2000 — conf
Arithmetic Circuits and Polynomial Replacement Systems.
FSTTCS
Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner
2000 B conf
Equation Satisfiability and Program Satisfiability for Finite Monoids.
MFCS
David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien
2000 A conf
On the Complexity of Some Problems on Groups Input as Multiplication Tables.
CCC
David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie
2000 J jnl
Reversible Space Equals Deterministic Space.
J. Comput. Syst. Sci.
Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp
2000 J jnl
The Complexity of Tensor Calculus
Electron. Colloquium Comput. Complex.
Carsten Damm, Markus Holzer, Pierre McKenzie
2000 A conf
The Complexity of Tensor Calculus.
CCC
Carsten Damm, Markus Holzer, Pierre McKenzie
2000 A* conf
The Many Faces of a Translation.
ICALP
Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
1999 Misc conf
Circuits and Context-Free Languages.
COCOON
Pierre McKenzie, Klaus Reinhardt, V. Vinay
1999 A* conf
Modular Temporal Logic.
LICS
Augustin Baziramwabo, Pierre McKenzie, Denis Thérien
1999 J jnl
Separation of the Monotone NC Hierarchy.
Comb.
Ran Raz, Pierre McKenzie
1999 A conf
The Descriptive Complexity Approach to LOGCFL.
STACS
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
1998 A conf
A Note on the Hardness of Tree Isomorphism.
CCC
Birgit Jenner, Pierre McKenzie, Jacobo Torán
1998 J jnl
Nondeterministic
J. Comput. Syst. Sci.
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer
1998 B conf
On the Complexity of Free Monoid Morphisms.
ISAAC
Klaus-Jörn Lange, Pierre McKenzie
1998 J jnl
The Descriptive Complexity Approach to LOGCFL
Electron. Colloquium Comput. Complex.
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
1998 J jnl
The descriptive complexity approach to LOGCFL
CoRR
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
1997 J jnl
Finite Moniods: From Word to Circuit Evaluation.
SIAM J. Comput.
Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien
1997 A conf
Reversible Space Equals Deterministic Space.
CCC
Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp
1997 A* conf
Separation of the Monotone NC Hierarchy.
FOCS
Ran Raz, Pierre McKenzie
1997 J jnl
Verifying Identical Communicating Processes is Undecidable.
Theor. Comput. Sci.
Alain Finkel, Pierre McKenzie
1996 J jnl
Logspace and Logtime Leaf Languages.
Inf. Comput.
Birgit Jenner, Pierre McKenzie, Denis Thérien
1996 A conf
Nondeterministic NC
CCC
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer
1995 J jnl
Circuits, Matrices, and Nonassociative Computation.
J. Comput. Syst. Sci.
Martin Beaudry, Pierre McKenzie
1994 — conf
Logspace and Logtime Leaf Languages.
SCT
Birgit Jenner, Pierre McKenzie, Denis Thérien
1994 J jnl
Special Issue on Circuit Complexity: Foreword.
Comput. Complex.
Pierre McKenzie, Denis Thérien
1993 J jnl
Extensions to Barrington's M-Program Model.
Theor. Comput. Sci.
François Bédard, François Lemieux, Pierre McKenzie
1992 — conf
Cicuits, Matrices, and Nonassociative Computation.
SCT
Martin Beaudry, Pierre McKenzie
1992 J jnl
The Membership Problem in Aperiodic Transformation Monoids.
J. ACM
Martin Beaudry, Pierre McKenzie, Denis Thérien
1991 J jnl
NC¹: The Automata-Theoretic Viewpoint.
Comput. Complex.
Pierre McKenzie, Pierre Péladeau, Denis Thérien
1991 J jnl
Oracle branching programs and Logspace versus P
Inf. Comput.
David A. Mix Barrington, Pierre McKenzie
1990 — conf
Extensions to Barrington's M-Program Model.
SCT
François Bédard, François Lemieux, Pierre McKenzie
1989 A* conf
Automata Theory Meets Circuit Complexity.
ICALP
Pierre McKenzie, Denis Thérien
1989 B conf
Oracle Branching Programs and Logspace versus P.
MFCS
David A. Mix Barrington, Pierre McKenzie
1989 A conf
Testing Membership: Beyond Permutation Groups (Extended Abstract).
STACS
Martin Beaudry, Pierre McKenzie, Denis Thérien
1988 J jnl
Parallel Algorithms for Solvable Permutation Groups.
J. Comput. Syst. Sci.
Eugene M. Luks, Pierre McKenzie
1987 J jnl
Problems Complete for Deterministic Logarithmic Space.
J. Algorithms
Stephen A. Cook, Pierre McKenzie
1987 J jnl
The Parallel Complexity of Abelian Permutation Group Problems.
SIAM J. Comput.
Pierre McKenzie, Stephen A. Cook
1985 A* conf
Fast Parallel Computation with Permutation Groups
FOCS
Eugene M. Luks, Pierre McKenzie
1984 — —
Parallel complexity and permutation groups.
Pierre McKenzie
1984 J jnl
Permutations of Bounded Degree Generate Groups of Polynomial Diameter.
Inf. Process. Lett.
Pierre McKenzie
1983 A* conf
The Parallel Complexity of the Abelian Permutation Group Membership Problem
FOCS
Pierre McKenzie, Stephen A. Cook