…“Would you tell me, please, which way I ought to go from here?”
“That depends a good deal on where you want to get to,” said the Cat.
“I don't much care where” said Alice.
“Then it doesn't matter which way you go,” said the Cat.
“so long as I get somewhere,” Alice added as an explanation.
“Oh, you're sure to do that,” said the Cat, “if you only walk long enough.”
Alice felt that this could not be denied…
.?...|
..)e.+#
....%|
If I were a NetHack monster, I would be a floating eye.
I see and sense absolutely everything that happens around me.
I just don't do very much about it.
programmern. an active entity, typically a human, that writes a
program, and that might or might not also be a user of the
program. (From the Common
Lisp HyperSpec.)
Address
Laboratoire d'Informatique de l'École Polytechnique (LIX)
Bâtiment Turing, bureau 2011
1 rue Honoré d'Estienne d'Orves, Campus de l'École Polytechnique
91120 Palaiseau, France
Email
Papers
Strategy Recovery for
Stochastic Mean Payoff Games (submitted).
We prove that to find optimal positional strategies for stochastic
mean payoff games when the value of every state of the game is known, in
general, is as hard as solving such games tout court. This answers a
question posed by Daniel Andersson and Peter Bro Miltersen.
Max-Closed Semilinear Constraint Satisfaction
(with M. Bodirsky)
(submitted).
A semilinear relation S is max-closed if it is preserved by taking the
componentwise maximum. The constraint satisfaction problem for max-closed
semilinear constraints is at least as hard as determining the winner in
Mean Payoff Games, a notorious problem of open computational complexity.
Mean Payoff Games are known to be in the intersection of NP and co-NP,
which is not known for max-closed semilinear constraints. Semilinear
relations that are max-closed and additionally closed under translations
have been called tropically convex in the literature. One of our main
results is a new duality for open tropically convex relations, which puts
the CSP for tropically convex semilinaer constraints in general into NP
intersected co-NP. This extends the corresponding complexity result for
and-or precedence constraints aka the max-atoms problem. To this end, we
present a characterization of max-closed semilinear relations in terms of
syntactically restricted first-order logic, and another characterization
in terms of a finite set of relations L that allow primitive positive
definitions of all other relations in the class. We also present a
subclass of max-closed constraints where the CSP is in P; this class
generalizes the class of max-closed constraints over finite domains, and
the feasibility problem for max-closed linear inequalities. Finally, we
show that the class of max-closed semilinear constraints is maximal in the
sense that as soon as a single relation that is not max-closed is added to
L, the CSP becomes NP-hard.
On the Computing Power of +, -, and x (LICS '14DOI:10.1145/2603088.2603159)
Modify the Blum-Shub-Smale model of computation replacing the permitted
computational primitives (the real field operations) with any finite set
B
of real functions semialgebraic over the rationals. Consider the class of
boolean decision problems that can be solved in polynomial time in the new
model by machines with no machine constants. How does this class depend on
B? We prove that it is always contained in the class obtained for
B={+,-,x}. Moreover, if B is a set of continuous semialgebraic functions
containing + and -, and such that arbitrarily small numbers can be
computed using B, then we have the following dichotomy: either our class
is P or it coincides with the class obtained for B={+,-,x}.
Condensation and
topological phase transitions in a dynamical network model with rewiring
of the links (with
L. Ferretti
and
G. Bianconi)
(Phys. Rev. E, 89, April 2014, DOI:10.1103/PhysRevE.89.042810).
Growing network models with both heterogeneity of the nodes and topological constraints can give rise to a rich phase structure. We present a simple model based on preferential attachment with rewiring of the links. Rewiring probabilities are modulated by the negative fitness of the nodes and by the constraint for the network to be a simple graph. At low temperatures and high rewiring rates, this constraint induces a Bose-Einstein condensation of paths of length 2, i.e. a new phase transition with an extended condensate of links. The phase space of the model includes further transitions in the scaling of the connected component and the degeneracy of the network.
Duality between preferential attachment and static random networks on hyperbolic spaces (with
L. Ferretti
and
M. Cortelezzi)
(EPL 105 (3), February 2014,
DOI:10.1209/0295-5075/105/38001).
There is a complex relation between the mechanism of preferential attachment, scale-free degree distributions and hyperbolicity in complex networks. In fact, both preferential attachment and hidden hyperbolic spaces often generate scale-free networks. We show that there is actually a duality between a class of growing spatial networks based on preferential attachment on the sphere and a class of static random networks on the hyperbolic plane. Both classes of networks have the same scale-free degree distribution as the Barabasi-Albert model. As a limit of this correspondence, the Barabasi-Albert model is equivalent to a static random network on an hyperbolic space with infinite curvature.
Groups definable in two orthogonal sorts (with A. Berarducci)
(Israel Journal of Mathematics 208 (1), September 2015,
413–441,
DOI:10.1007/s11856-015-1205-5).
This work can be thought as a contribution to the model theory of group
extensions. We study the groups G which are interpretable in the disjoint union
of two structures (seen as a two-sorted structure). We show that if one of the
two structures is superstable of finite Lascar rank and the Lascar rank is
definable, then G is an extension of a group internal to the (possibly)
unstable sort by a definable subgroup internal to the stable sort. In the final
part of the paper we show that if the unstable sort is an o‐minimal expansion
of the reals, then G has a natural Lie structure and the extension is a
topological cover.
On the computational complexity of a game of cops and robbers (Theoretical Computer Science 477 (2013) 48–56,
DOI:10.1016/j.tcs.2012.11.041).
We study the computational complexity of a perfect‐information two‐player
game proposed by Aigner and Fromme. The game takes place on an undirected graph
where n simultaneously moving cops attempt to capture a single robber, all
moving at the same speed. The players are allowed to pick their starting
positions at the first move. The question of the computational complexity of
deciding this game was
raised in the '90s by Goldstein and Reingold. We prove that the game is hard
for PSPACE.
Discrete subgroups of locally definable groups
(with A. Berarducci & M. Edmundo)
(Selecta Mathematica 19 (3), August 2013, 719–736,
DOI:10.1007/s00029-013-0123-9).
We work in the category of locally definable groups in an o‐minimal
expansion of a field. Eleftheriou and Peterzil conjectured that every
definably generated abelian connected group G in
this category, is a cover of a definable group. We prove that this is the
case under a natural convexity assumption inspired by the same authors,
which in fact gives a necessary and sufficient condition. The proof is
based on the study of the zero‐dimensional compatible subgroups
of G. Given a locally definable connected
group G (not necessarily definably generated), we
prove that the n‐torsion subgroup of G is
finite and that every zero‐dimensional compatible subgroup
of G has finite rank. Under a convexity
hypothesis we show that every zero‐dimensional compatible subgroup
of G is finitely generated.
Splitting definably compact groups in o‐minimal structures (Journal of Symbolic Logic 76 (3) (2011) 973–986,
DOI:10.2178/jsl/1309952529).
An argument of A. Borel shows that every compact connected Lie group is homeomorphic to the Cartesian product of its derived subgroup and a torus. We prove a parallel result for definably compact definably connected groups definable in an o‐minimal expansion of a real closed field. As opposed to the Lie case, however, we provide an example showing that the derived subgroup may not be a semidirect factor of the group.
On the homotopy type of definable groups in an o‐minimal structure
(with A. Berarducci) (Journal of the London Mathematical Society (2) 83 (2011) 563–586,
final version,
DOI:10.1112/jlms/jdq080).
Given a definably compact group G in a saturated o‐minimal structure, there is a canonical homomorphism from G to a compact real Lie group F(G). We establish a similar result for the (o‐mininimal) universal cover of a definably compact group. We also show that F(G) determines the definable homotopy type of G. A crucial step is to show that the fundamental group of an open subset of F(G) is isomorphic to the definable fundamental group of its preimage in G. Our results depend on the study of the o‐minimal fundamental groupoid of G.
Higher homotopy of groups definable in o‐minimal structures
(with A. Berarducci & M. Otero) (Israel Journal of Mathematics 180(1) 143–161,
DOI:10.1007/s11856-010-0098-6).
It is known that a definably compact group G is an extension
of a compact Lie group L by a divisible torsion‐free normal subgroup. We show
that the o‐minimal higher homotopy groups of G are isomorphic to the
corresponding higher homotopy groups of L. As a consequence, we obtain that all
abelian definably compact groups of a given dimension are definably homotopy
equivalent, and that their universal cover are contractible.
Arithmetic of Dedekind cuts on ordered Abelian groups
(with A. Fornasiero) (Annals of Pure and Applied Logic 156 (2008) 210–244,
DOI:10.1016/j.apal.2008.05.001).
We study the set of Dedekind cuts over a linearly ordered Abelian group as a structure over the language (0,<,+,-).
Moreover, we obtain a simple set of axioms for the universal part of the theory of such structures.
Finally, we prove that every structure satisfying the given axioms is a sub-structure of the set of cuts over a suitable group.