Homepage of Marcello Mamino

…“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.
Which NetHack Monster Are You?

Myself

programmer n. 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 '14 DOI: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.
Valid XHTML 1.0 Strict Valid CSS!