Author name cluster

Pierre Ohlmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AAAI Conference 2022 Conference Paper

Scaling Neural Program Synthesis with Distribution-Based Search

Nathanaël Fijalkow
Guillaume Lagarde
Théo Matricon
Kevin Ellis
Pierre Ohlmann
Akarsh Nayan Potta

We consider the problem of automatically constructing computer programs from input-output examples. We investigate how to augment probabilistic and neural program synthesis methods with new search algorithms, proposing a framework called distribution-based search. Within this framework, we introduce two new search algorithms: HEAP SEARCH, an enumerative method, and SQRT SAMPLING, a probabilistic method. We prove certain optimality guarantees for both methods, show how they integrate with probabilistic and neural techniques, and demonstrate how they can operate at scale across parallel compute environments. Collectively these findings offer theoretical and applied studies of search algorithms for program synthesis that integrate with recent developments in machine-learned program synthesizers.

PDF Details

Highlights Conference 2022 Conference Abstract

Well-Ordered Monotonic Universal Graphs for Half Positionality

Pierre Ohlmann

I will present recent work on how to characterize half-positionality over arbitrary arenas by means of universal graphs. More precisely, we will see that an objective is positional if and only if it has a well-ordered universal monotonic graph, for each cardinal. I will also describe a few examples, and state some open problems.

Details

Highlights Conference 2021 Conference Abstract

Generic algorithm for parity and mean payoff games

Pierre Ohlmann

In this talk, we present linear graphs for generic positional objectives in the context of infinite duration two player games over finite graphs such as the parity or mean payoff objectives. These were originally designed to capture the new quasi-polynomial value iteration algorithms for parity games. We show that this framework also allows to formalize other families of algorithms such as strategy-improvement algorithms, or (in the context of parity games), attractor-based algorithms.

Details

GandALF Workshop 2021 Workshop Paper

New Algorithms for Combinations of Objectives using Separating Automata

Ashwani Anand
Nathanaël Fijalkow
Aliénor Goubault-Larrecq
Jérôme Leroux
Pierre Ohlmann

The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that separating automata is a powerful tool for constructing algorithms solving games with combinations of objectives. We construct two new algorithms: the first for disjunctions of parity and mean payoff objectives, matching the best known complexity, and the second for disjunctions of mean payoff objectives, improving on the state of the art. In both cases the algorithms are obtained through the construction of small separating automata, using as black boxes the existing constructions for parity objectives and for mean payoff objectives.

PDF Details DOI

Highlights Conference 2020 Conference Abstract

On the complexity of the sequential flow problem

Pierre Ohlmann

A flow system over a finite set Q of states is given by a finite set C of actions, which are directed graphs over Q with arcs labelled by capacities, that is, either a non-negative number or ∞. When the controller plays an given action, any number of token which is in q and below the capacity of an arc from q to q’ may be moved to q’. The sequential flow problem (SFP) is a control problem in such a system which considers arbitrary number of tokens: is it the case that for any number n of tokens in a designated source state s, the controller may find a sequence of actions that leads all tokens to a designated target state t? The SFP was introduced in the context of stochastic control problems of arbitrary numbers of agents, and its complexity remains open. In this talk, I will present an existing EXPSPACE algorithm, and present ongoing work towards a PSPACE upper bound. This is the result of joint ongoing works with Thomas Colcombet, Nathanaël Fijalkow, Mahsa Shirmohammadi and Arnaud Sangnier.

Details

MFCS Conference 2020 Conference Paper

Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

Nathanaël Fijalkow
Pawel Gawrychowski
Pierre Ohlmann

We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in both cases solving them is in NP ∩ coNP and not known to be in P. In a breakthrough result Calude, Jain, Khoussainov, Li, and Stephan constructed in 2017 a quasipolynomial time algorithm for solving parity games, which was quickly followed by a few other algorithms with the same complexity. Our objective is to investigate how these techniques can be extended to mean payoff games. The starting point is the combinatorial notion of universal trees: all quasipolynomial time algorithms for parity games have been shown to exploit universal trees. Universal graphs extend universal trees to arbitrary (positionally determined) objectives. We show that they yield a family of value iteration algorithms for solving mean payoff games which includes the value iteration algorithm due to Brim, Chaloupka, Doyen, Gentilini, and Raskin. The contribution of this paper is to prove tight bounds on the complexity of algorithms for mean payoff games using universal graphs. We consider two parameters: the largest weight N in absolute value and the number k of weights. The dependence in N in the existing value iteration algorithm is linear, we show that this can be improved to N^{1 - 1/n} and obtain a matching lower bound. However, we show that we cannot break the linear dependence in the exponent in the number k of weights implying that universal graphs do not yield a quasipolynomial time algorithm for solving mean payoff games.

Details

Highlights Conference 2018 Conference Abstract

Characterization of non-associative circuits using automata, and applications

Pierre Ohlmann

ABSTRACT. Arithmetic circuit are the algebraic analogue of boolean circuits. As a natural model for computing multivariate polynomials, they have been extensively studied. The most important open question in the field of algebraic complexity theory is that of separating the classes VP and VNP, the analogues of P and NP. More precisely, can one obtain super-polynomial lower bounds for circuits computing a given explicit polynomial? Despite decades of efforts, this question yet seems out of reach, the best general lower bound being only slightly super-linear. The most common approach is to prove lower bounds for restricted classes of circuits, such as monotone or constant-depth circuits. Another approach would be removing relations arising from the mathematical structure underlying the computations, making it harder for circuits to compute polynomials and thus conceivably easier to obtain lower bounds. In this line of thought, Nisan (1991) was able to obtain breakthrough results in the context of non-commutative computations, separating circuits and formulas and characterizing the minimal size of Algebraic Branching Programs (ABP). Likewise, circuits for which the multiplication is assumed to be non-associative, meaning that (xy)x and x(yx) are different monomials, have been considered. General exponential lower bounds can be proved in this setting. We highlight a syntactical equivalence between non-associative circuits and acyclic Multiplicity Tree Automata (MTA), which leads to a general algebraic characterization of the size of the smallest non-associative circuit computing a given non-associative polynomial. As a direct consequence of this characterization, we unify several recent circuit lower bounds in the non-commutative setting. Going deeper in the comprehension of this new algebraic tool, we are able to considerably extend a known lower bound to a class which is very close to general.

Details