Mikhail Raskin

Mikhail Raskin

Auto-generated profile, based on publicly available information

Mikhail Raskin

Department of Informatics Technical University of Munich Munich Germany

Research Focus & Metrics

Academic Career Length

16Years (2011-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
31 May 2019
Verified
Book Chapter
Closed access
PDF file
JEJavier Esparza
Javier Esparza
MRMikhail Raskin
Mikhail Raskin
CWChana Weil-Kennedy
Chana Weil-Kennedy

24 March 2021 in Distributed Computing
Verified
Journal Article
Open access
PDF file
JEJavier Esparza
Javier Esparza
SJStefan Jaax
Stefan Jaax
MRMikhail Raskin
Mikhail Raskin
CWChana Weil-Kennedy
Chana Weil-Kennedy
Population protocols (Angluin et al. in PODC, 2004) are a model of distributed computation in which indistinguishable, finite-state agents interact in pairs to decide if their initial configuration, i.e., the initial number of agents in each state, satisfies a given property. In a seminal paper Angluin et al. classified population protocols according to their communication mechanism, and conducted an exhaustive study of the expressive power of each class, that is, of the properties they can decide (Angluin et al. in Distrib Comput 20(4):279–304, 2007). In this paper we study the correctness problem for population protocols, i.e., whether a given protocol decides a given property. A previous paper (Esparza et al. in Acta Inform 54(2):191–215, 2017) has shown that the problem is decidable for the main population protocol model, but at least as hard as the reachability problem for Petri nets, which has recently been proved to have non-elementary complexity. Motivated by this result, we study the computational complexity of the correctness problem for all other classes introduced by Angluin et al., some of which are less powerful than the main model. Our main results show that for the class of observation models the complexity of the problem is much lower, ranging from $$\varPi _2^p$$ Π 2 p to .

20 July 2021 in Logical Methods in Computer Science
Verified
Journal Article
Open access
PDF file
MBMichael Blondin
Michael Blondin
CHChristoph Haase
Christoph Haase
FMFilip Mazowiecki
Filip Mazowiecki
MRMikhail Raskin
Mikhail Raskin
We study the reachability problem for affine $\mathbb{Z}$-VASS, which are integer vector addition systems with states in which transitions perform affine transformations on the counters. This problem is easily seen to be undecidable in general, and we therefore restrict ourselves to affine $\mathbb{Z}$-VASS with the finite-monoid property (afmp-$\mathbb{Z}$-VASS). The latter have the property that the monoid generated by the matrices appearing in their affine transformations is finite. The class of afmp-$\mathbb{Z}$-VASS encompasses classical operations of counter machines such as resets, permutations, transfers and copies. We show that reachability in an afmp-$\mathbb{Z}$-VASS reduces to reachability in a $\mathbb{Z}$-VASS whose control-states grow linearly in the size of the matrix monoid. Our construction shows that reachability relations of afmp-$\mathbb{Z}$-VASS are semilinear, and in particular enables us to show that reachability in $\mathbb{Z}$-VASS with transfers and $\mathbb{Z}$-VASS with copies is PSPACE-complete. We then focus on the reachability problem for affine $\mathbb{Z}$-VASS with monogenic monoids: (possibly infinite) matrix monoids generated by a single matrix. We show that, in a particular case, the reachability problem is decidable for this class, disproving a conjecture about affine $\mathbb{Z}$-VASS with infinite matrix monoids we raised in a preliminary version of this paper. We complement this result by presenting an affine $\mathbb{Z}$-VASS with monogenic matrix monoid and undecidable reachability relation.

1 August 2014 in Theoretical Computer Science
Verified
Journal Article
Closed access
KCKrishnendu Chatterjee
Krishnendu Chatterjee
MHMonika Henzinger
Monika Henzinger
SKSebastian Krinninger
Sebastian Krinninger
VLVeronika Loitzenbauer
Veronika Loitzenbauer
MRMichael A. Raskin
Michael A. Raskin

19 March 2024 in SIAM Journal on Computing
Verified
Journal Article
Closed access
ACArnaud Casteigts
Arnaud Casteigts
MRMichael Raskin
Michael Raskin
MRMalte Renken
Malte Renken
VZViktor Zamaraev
Viktor Zamaraev
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős–Rényi random graph, [Formula: see text], by considering a random permutation [Formula: see text] of the edges and interpreting the ranks in [Formula: see text] as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at [Formula: see text], any fixed pair of vertices can asymptotically almost surely (a.a.s.) reach each other; at [Formula: see text], at least one vertex (and, in fact, any fixed vertex) can a.a.s. reach all others; and at [Formula: see text], all the vertices can a.a.s. reach each other; i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size [Formula: see text] as soon as it becomes temporally connected, which is nearly optimal, as [Formula: see text] is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size [Formula: see text] in general [Kempe, Kleinberg, and Kumar, J. Comput. System Sci., 64 (2002), pp. 820–842]. In fact, they do not even always admit spanners of size [Formula: see text] [Axiotis and Fotakis, On the size and the approximability of minimum temporally connected subgraphs, 2016, pp. 149:1–149:14]. Thus, our result implies that the obstructions found in these works—and more generally any non-negligible obstruction—are statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners—i.e., spanners of size [Formula: see text] composed of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)—exist a.a.s. at [Formula: see text], this threshold being also sharp. Finally, we show that optimal spanners (of size [Formula: see text]) also exist a.a.s. at [Formula: see text]. Whether this value is a sharp threshold is open; we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well and that in some cases they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson’s celebrated results on percolation in weighted graphs.

23 March 2021
Verified
Book Chapter
Open access
PDF file
ABA. R. Balasubramanian
A. R. Balasubramanian
JEJavier Esparza
Javier Esparza
MRMikhail Raskin
Mikhail Raskin
In rendez-vous protocols an arbitrarily large number of indistinguishable finite-state agents interact in pairs. The cut-off problem asks if there exists a number B such that all initial configurations of the protocol with at least B agents in a given initial state can reach a final configuration with all agents in a given final state. In a recent paper [17], Horn and Sangnier prove that the cut-off problem is equivalent to the Petri net reachability problem for protocols with a leader, and in "Image missing" for leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to "Image missing" and "Image missing" , respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is "Image missing" -complete for leaderless protocols, "Image missing" -complete for symmetric protocols with a leader, and in "Image missing" for leaderless symmetric protocols, thereby solving all the problems left open in [17].