Zobrazeno 1 - 10
of 339
pro vyhledávání: '"Studený P"'
Autor:
Studený, Milan
Five different ways of combinatorial description of non-empty faces of the cone of supermodular functions on the power set of a finite basic set $N$ are introduced. Their identification with faces of the cone of supermodular games allows one to assoc
Externí odkaz:
http://arxiv.org/abs/2410.19454
Autor:
Dhar, Anubhav, Kujawa, Eli, Lievonen, Henrik, Modanese, Augusto, Muftuoglu, Mikail, Studený, Jan, Suomela, Jukka
The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algorithms, - the quantum version of the LOCAL model, - finitely dependent d
Externí odkaz:
http://arxiv.org/abs/2409.13795
In prior work, Gupta et al. (SPAA 2022) presented a distributed algorithm for multiplying sparse $n \times n$ matrices, using $n$ computers. They assumed that the input matrices are uniformly sparse--there are at most $d$ non-zeros in each row and co
Externí odkaz:
http://arxiv.org/abs/2404.15559
We introduce an algebraic concept of the frame for abstract conditional independence (CI) models, together with basic operations with respect to which such a frame should be closed: copying and marginalization. Three standard examples of such frames
Externí odkaz:
http://arxiv.org/abs/2402.14053
Autor:
Gupta, Chetan, Latypov, Rustam, Maus, Yannic, Pai, Shreyas, Särkkä, Simo, Studený, Jan, Suomela, Jukka, Uitto, Jara, Vahidi, Hossein
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in $O(\log D)$ rounds in the massively parallel computation model (MPC), with $O(n^\delta)$ words of local memory per machine, for any given consta
Externí odkaz:
http://arxiv.org/abs/2305.03693
We study matrix multiplication in the low-bandwidth model: There are $n$ computers, and we need to compute the product of two $n \times n$ matrices. Initially computer $i$ knows row $i$ of each input matrix. In one communication round each computer c
Externí odkaz:
http://arxiv.org/abs/2203.01297
Autor:
Balliu, Alkida, Brandt, Sebastian, Chang, Yi-Jun, Olivetti, Dennis, Studený, Jan, Suomela, Jukka
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[\Theta(\log n), \Theta(n)]$ region, in two settings. We present one algorithm for unr
Externí odkaz:
http://arxiv.org/abs/2202.08544
Autor:
Balliu, Alkida, Korhonen, Janne H., Kuhn, Fabian, Lievonen, Henrik, Olivetti, Dennis, Pai, Shreyas, Paz, Ami, Rybicki, Joel, Schmid, Stefan, Studený, Jan, Suomela, Jukka, Uitto, Jara
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orient
Externí odkaz:
http://arxiv.org/abs/2108.02655
Autor:
Studený, Milan, Kratochvíl, Václav
Publikováno v:
Mathematical Methods of Operations Research 95 (2022) 35-80
The class of exact transferable utility coalitional games, introduced in 1972 by Schmeidler, has been studied both in the context of game theory and in the context of imprecise probabilities. We characterize the cone of exact games by describing the
Externí odkaz:
http://arxiv.org/abs/2103.02414
Autor:
Balliu, Alkida, Brandt, Sebastian, Chang, Yi-Jun, Olivetti, Dennis, Studený, Jan, Suomela, Jukka, Tereshchenko, Aleksandr
Consider any locally checkable labeling problem $\Pi$ in rooted regular trees: there is a finite set of labels $\Sigma$, and for each label $x \in \Sigma$ we specify what are permitted label combinations of the children for an internal node of label
Externí odkaz:
http://arxiv.org/abs/2102.09277