James Worrell

TCS Journal 2025 Journal Article

The monadic theory of toric words

• Valérie Berthé
• Toghrul Karimov
• Joris Nieuwveld
• Joël Ouaknine
• Mihir Vahanwala
• James Worrell

For which unary predicates P 1, …, P m is the MSO theory of the structure 〈 N; <, P 1, …, P m 〉 decidable? We survey the state of the art, leading us to investigate combinatorial properties of almost-periodic, morphic, and toric words. In doing so, we show that if each P i can be generated by a toric dynamical system of a certain kind, then the attendant MSO theory is decidable. We give various applications of toric words, including the recent result of [1] that the MSO theory of 〈 N; <, { 2 n: n ∈ N }, { 3 n: n ∈ N } 〉 is decidable.

IJCAI Conference 2022 Conference Paper

Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks

• Pascale Gourdeau
• Varun Kanade
• Marta Kwiatkowska
• James Worrell

A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. In this paper we address this issue within the framework of PAC learning, focusing on the class of decision lists. Given that distributional assumptions are essential in the adversarial setting, we work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. Our key results illustrate that the adversary's budget (that is, the number of bits it can perturb on each input) is a fundamental quantity in determining the sample complexity of robust learning. Our first main result is a sample-complexity lower bound: the class of monotone conjunctions (essentially the simplest non-trivial hypothesis class on the Boolean hypercube) and any superclass has sample complexity at least exponential in the adversary's budget. Our second main result is a corresponding upper bound: for every fixed k the class of k-decision lists has polynomial sample complexity against a log(n)-bounded adversary. This sheds further light on the question of whether an efficient PAC learning algorithm can always be used as an efficient log(n)-robust learning algorithm under the uniform distribution.

Highlights Conference 2022 Conference Abstract

The Pseudo-Reachability Problem for Linear Dynamical Systems

• James Worrell

Joint work with Joel Ouaknine, James Worrell, Rupak Majumdar, Sadegh Soudjani, Julian D'Costa and Mahmoud Salamati. A linear dynamical system is given by an update matrix M and a starting point s. The reachability problem for LDS asks, given a semialgebraic target S, whether the orbit ever hits S. This problem is open and at least as hard as the Skolem and the Positivity problems for linear recurrence sequences. We consider reachability questions for pseudo-orbits, which is a fundamental notion in theory of dynamical systems going back to works of Anosov, Bowen and Conley. An epsilon-pseudo orbit of s under M is a sequence such that x_0=s and x_{n+1}=Mx_n + d_n for a perturbation d_n of size at most epsilon. The pseudo-reachability problem then is to determine if for every epsilon>0, there exists an epsilon-pseudo-orbit that hits S. This can be viewed as a robust version of the reachability problem. In our work presented at MFCS21, we showed that the pseudo-Skolem problem (pseudo-reachability problem where the target S is a hyperplane) is decidable using established methods. In our ongoing work, relying on o-minimality of R_exp, we have shown that for diagonalisable systems, the pseudo-reachability problem is decidable for arbitrary semialgebraic targets. Moreover, our methods can readily be applied in the continuous setting and to certain other formulations of the robust reachability problem.

NeurIPS Conference 2022 Conference Paper

When are Local Queries Useful for Robust Learning?

• Pascale Gourdeau
• Varun Kanade
• Marta Kwiatkowska
• James Worrell

Distributional assumptions have been shown to be necessary for the robust learnability of concept classes when considering the exact-in-the-ball robust risk and access to random examples by Gourdeau et al. (2019). In this paper, we study learning models where the learner is given more power through the use of local queries, and give the first distribution-free algorithms that perform robust empirical risk minimization (ERM) for this notion of robustness. The first learning model we consider uses local membership queries (LMQ), where the learner can query the label of points near the training sample. We show that, under the uniform distribution, LMQs do not increase the robustness threshold of conjunctions and any superclass, e. g. , decision lists and halfspaces. Faced with this negative result, we introduce the local equivalence query (LEQ) oracle, which returns whether the hypothesis and target concept agree in the perturbation region around a point in the training sample, as well as a counterexample if it exists. We show a separation result: on one hand, if the query radius $\lambda$ is strictly smaller than the adversary's perturbation budget $\rho$, then distribution-free robust learning is impossible for a wide variety of concept classes; on the other hand, the setting $\lambda=\rho$ allows us to develop robust ERM algorithms. We then bound the query complexity of these algorithms based on online learning guarantees and further improve these bounds for the special case of conjunctions. We finish by giving robust learning algorithms for halfspaces with margins on both $\{0, 1\}^n$ and $\mathbb{R}^n$.

JMLR Journal 2021 Journal Article

On the Hardness of Robust Classification

• Pascale Gourdeau
• Varun Kanade
• Marta Kwiatkowska
• James Worrell

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of adversarially robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. We start with two negative results. We show that no non-trivial concept class can be robustly learned in the distribution-free setting against an adversary who can perturb just a single input bit. We show, moreover, that the class of monotone conjunctions cannot be robustly learned under the uniform distribution against an adversary who can perturb $\omega(\log n)$ input bits. However, we also show that if the adversary is restricted to perturbing $O(\log n)$ bits, then one can robustly learn the class of $1$-decision lists (which subsumes monotone conjunctions) with respect to the class of log-Lipschitz distributions. We then extend this result to show learnability of 2-decision lists and monotone $k$-decision lists in the same distributional and adversarial setting. Finally, we provide a simple proof of the computational hardness of robust learning on the boolean hypercube. Unlike previous results of this nature, our result does not rely on a more restricted model of learning, such as the statistical query model, nor on any hardness assumption other than the existence of an (average-case) hard learning problem in the PAC framework; this allows us to have a clean proof of the reduction, and the assumption is no stronger than assumptions that are used to build cryptographic primitives. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

NeurIPS Conference 2019 Conference Paper

On the Hardness of Robust Classification

• Pascale Gourdeau
• Varun Kanade
• Marta Kwiatkowska
• James Worrell

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. We start with two negative results. We show that no non-trivial concept class can be robustly learned in the distribution-free setting against an adversary who can perturb just a single input bit. We show moreover that the class of monotone conjunctions cannot be robustly learned under the uniform distribution against an adversary who can perturb $\omega(\log n)$ input bits. However if the adversary is restricted to perturbing $O(\log n)$ bits, then the class of monotone conjunctions can be robustly learned with respect to a general class of distributions (that includes the uniform distribution). Finally, we provide a simple proof of the computational hardness of robust learning on the boolean hypercube. Unlike previous results of this nature, our result does not rely on another computational model (e. g. the statistical query model) nor on any hardness assumption other than the existence of a hard learning problem in the PAC framework.

Highlights Conference 2018 Conference Abstract

Algebraic Invariants for Affine Programs

• James Worrell

ABSTRACT. Automatically generating invariants is a fundamental challenge in program analysis and verification. In this talk we give a select oveview of previous work on this problem, starting with Michael Karr's 1976 algorithm for computing affine invariants in affine programs (i. e. , programs having only non-deterministic (as opposed to conditional) branching and all of whose assignments are given by affine expressions). We then present the central result of the talk---an algorithm to compute all polynomial invariants that hold at each location of a given a affine program. Our main tool is an algebraic result of independent interest: given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate. This is joint work with Ehud Hrushovski, Joel Ouaknine, and Amaury Pouly.

TCS Journal 2018 Journal Article

Reachability Problems 2014: Special issue

• Joël Ouaknine
• Igor Potapov
• James Worrell

Highlights Conference 2016 Conference Abstract

Minimal probabilistic automata have to make irrational choices

• Mahsa Shirmohammadi
• Dmitry Chistikov
• Stefan Kiefer
• Ines Marusic
• James Worrell

In this talk, we answer the question of whether, given a probabilistic automaton (PA) with rational transition probabilities, there always exists a minimal equivalent PA that also has rational transition probabilities. The PA and its minimal equivalent PA accept all finite words with equal probabilities. We approach this problem by exhibiting a connection with a longstanding open question concerning nonnegative matrix factorization (NMF). NMF is the problem of decomposing a given nonnegative n*m matrix M into a product of a nonnegative n*d matrix W and a nonnegative d*m matrix H. In 1993 Cohen and Rothblum posed the problem of whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries. As a corollary we obtain a negative answer to the question on rationality of minimal probabilistic automata. This talk is based on the paper titled “On Restricted Nonnegative Matrix Factorization”, that will be presented in ICALP 2016, and the unpublished manuscript titled “Nonnegative Matrix Factorization Requires Irrationality”, that is now online on Arxiv (https: //arxiv. org/abs/1605. 06848v1).

JMLR Journal 2015 Journal Article

Complexity of Equivalence and Learning for Multiplicity Tree Automata

• Ines Marusic
• James Worrell

We consider the query and computational complexity of learning multiplicity tree automata in Angluin's exact learning model. In this model, there is an oracle, called the Teacher, that can answer membership and equivalence queries posed by the Learner. Motivated by this feature, we first characterise the complexity of the equivalence problem for multiplicity tree automata, showing that it is logspace equivalent to polynomial identity testing. We then move to query complexity, deriving lower bounds on the number of queries needed to learn multiplicity tree automata over both fixed and arbitrary fields. In the latter case, the bound is linear in the size of the target automaton. The best known upper bound on the query complexity over arbitrary fields derives from an algorithm of Habrard and Oncina (2006), in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, a smallest counterexample tree may already be exponential in the size of the target automaton. Thus the above algorithm has query complexity exponentially larger than our lower bound, and does not run in time polynomial in the size of the target automaton. We give a new learning algorithm for multiplicity tree automata in which counterexamples to equivalence queries are represented as DAGs. The query complexity of this algorithm is quadratic in the target automaton size and linear in the size of a largest counterexample. In particular, if the Teacher always returns DAG counterexamples of minimal size then the query complexity is quadratic in the target automaton size---almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

TCS Journal 2013 Journal Article

Addendum to “Recursively defined metric spaces without contraction” [Theoret. Comput. Sci. 380 (1/2) (2007) 143–163]

• Franck van Breugel
• Claudio Hermida
• Michael Makkai
• James Worrell

In this addendum, we correct some typos and fill a gap in the proof of Theorem 21 of [F. van Breugel, C. Hermida, M. Makkai, J. Worrell. Recursively defined metric spaces without contraction. Theoretical Computer Science 380 (1/2) (2007) 143–163]. We reprove Theorem 21 and fill the gap by Lemmas 2–4 of this paper.

Highlights Conference 2013 Conference Abstract

Zeno, Hercules and the Hydra: Downward rational termination is Ackermannian

• Ranko Lazic
• Joel Ouaknine
• James Worrell

Metric temporal logic (MTL) is one of the most prominent specification formalisms for real-time systems. Over infinite timed words, full MTL is undecidable, but satisfiability for its safety fragment was proved decidable several years ago. The problem is also known to be equivalent to a fair termination problem for a class of channel machines with insertion errors. However, the complexity has remained elusive, except for a non-elementary lower bound. Via another equivalent problem, namely termination for a class of rational relations, we show that satisfiability for safety MTL is not primitive recursive, yet is Ackermannian, i. e. , among the simplest non-primitive recursive problems. This is surprising since decidability was originally established using Higman's Lemma, suggesting a much higher non-multiply recursive complexity.

TCS Journal 2007 Journal Article

Recursively defined metric spaces without contraction

• Franck van Breugel
• Claudio Hermida
• Michael Makkai
• James Worrell

In this paper we use the theory of accessible categories to find fixed points of endofunctors on the category of 1-bounded complete metric spaces and nonexpansive functions. In contrast to previous approaches, we do not assume that the endofunctors are locally contractive, and our results do not depend on Banach’s fixed-point theorem. Our approach is particularly suitable for constructing models of systems that feature quantitative data. For instance, using the Kantorovich metric on probability measures we construct a quantitative model for probabilistic transition systems. The metric in our model can reasonably be seen as measuring the behavioural distance between states of the system; it depends exclusively on the transition probabilities and not on an arbitrary discount factor.

TCS Journal 2006 Journal Article

Approximating and computing behavioural distances in probabilistic transition systems

• Franck van Breugel
• James Worrell

In an earlier paper we presented a pseudometric on the states of a probabilistic transition system, yielding a quantitative notion of behavioural equivalence. The behavioural pseudometric was defined via the terminal coalgebra of a functor based on a metric on Borel probability measures. In the present paper we give a polynomial-time algorithm, based on linear programming, to calculate the distances between states up to a prescribed degree of accuracy.

TCS Journal 2005 Journal Article

A behavioural pseudometric for probabilistic transition systems

• Franck van Breugel
• James Worrell

Discrete notions of behavioural equivalence sit uneasily with semantic models featuring quantitative data, like probabilistic transition systems. In this paper, we present a pseudometric on a class of probabilistic transition systems yielding a quantitative notion of behavioural equivalence. The pseudometric is defined via the terminal coalgebra of a functor based on a metric on the space of Borel probability measures on a metric space. States of a probabilistic transition system have distance 0 if and only if they are probabilistic bisimilar. We also characterize our distance function in terms of a real-valued modal logic.

TCS Journal 2005 Journal Article

Domain theory, testing and simulation for labelled Markov processes

• Franck van Breugel
• Michael Mislove
• Joël Ouaknine
• James Worrell

This paper presents a fundamental study of similarity and bisimilarity for labelled Markov processes (LMPs). The main results characterize similarity as a testing preorder and bisimilarity as a testing equivalence. In general, LMPs are not required to satisfy a finite-branching condition—indeed the state space may be a continuum, with the transitions given by arbitrary probability measures. Nevertheless we show that to characterize bisimilarity it suffices to use finitely-branching labelled trees as tests. Our results involve an interaction between domain theory and measure theory. One of the main technical contributions is to show that a final object in a suitable category of LMPs can be constructed by solving a domain equation D ≅ V ( D ) Act, where V is the probabilistic powerdomain. Given an LMP whose state space is an analytic space, bisimilarity arises as the kernel of the unique map to the final LMP. We also show that the metric for approximate bisimilarity introduced by Desharnais, Gupta, Jagadeesan and Panangaden generates the Lawson topology on the domain D.

TCS Journal 2005 Journal Article

On the final sequence of a finitary set functor

• James Worrell

A standard construction of the final coalgebra of an endofunctor involves defining a chain of iterates, starting at the final object of the underlying category and successively applying the functor. In this paper we show that, for a finitary set functor, this construction always yields a final coalgebra in ω 2 = ω + ω steps.

TCS Journal 2004 Journal Article

Measuring the probabilistic powerdomain

• Keye Martin
• Michael Mislove
• James Worrell

In this paper we initiate the study of measurements on the probabilistic powerdomain. We show how measurements on an underlying domain naturally extend to its probabilistic powerdomain, so that the kernel of the extension consists of exactly those normalized measures on the kernel of the measurement on the underlying domain. This result is combined with now-standard results from the theory of measurements to obtain a new proof that the fixed point associated with a weakly hyperbolic IFS with probabilities is the unique invariant measure whose support is the attractor of the underlying IFS.

TCS Journal 2001 Journal Article

On the structure of categories of coalgebras

• Peter Johnstone
• John Power
• Toru Tsujishita
• Hiroshi Watanabe
• James Worrell

Consideration of categories of transition systems and related constructions leads to the study of categories of F-coalgebras, where F is an endofunctor of the category of sets, or of some more general ‘set-like’ category. It is fairly well known that if E is a topos and F: E→E preserves pullbacks and generates a cofree comonad, then the category of F-coalgebras is a topos. Unfortunately, in most of the examples of interest in computer science, the endofunctor F does not preserve pullbacks, though it comes close to doing so. In this paper we investigate what can be said about the category of coalgebras under various weakenings of the hypothesis that F preserves pullbacks. It turns out that almost all the elementary properties of a topos, except for effectiveness of equivalence relations, are still inherited by the category of coalgebras; and the latter can be recovered by embedding the category in its effective completion. However, we also show that, in the particular cases of greatest interest, the category of coalgebras is not itself a topos.