Zobrazeno 1 - 10
of 203
pro vyhledávání: '"Ghaffari, Mohsen"'
Tabular reinforcement learning methods cannot operate directly on continuous state spaces. One solution for this problem is to partition the state space. A good partitioning enables generalization during learning and more efficient exploitation of pr
Externí odkaz:
http://arxiv.org/abs/2409.16791
Autor:
Ghaffari, Mohsen, Trygub, Anton
We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the m
Externí odkaz:
http://arxiv.org/abs/2409.15476
Autor:
Ghaffari, Mohsen, Trygub, Anton
We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in $\tilde{O}(n)$ rounds and each node is awake during only $poly(\log n)$ rounds. When a node is not aw
Externí odkaz:
http://arxiv.org/abs/2409.15470
Autor:
Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Modanese, Augusto, Olivetti, Dennis, Rabie, Mikaël, Suomela, Jukka, Uitto, Jara
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockme
Externí odkaz:
http://arxiv.org/abs/2407.05445
We revisit the classic broadcast problem, wherein we have $k$ messages, each composed of $O(\log{n})$ bits, distributed arbitrarily across a network. The objective is to broadcast these messages to all nodes in the network. In the distributed CONGEST
Externí odkaz:
http://arxiv.org/abs/2404.12930
Autor:
Ghaffari, Mohsen, Grunau, Christoph
We present an efficient parallel derandomization method for randomized algorithms that rely on concentrations such as the Chernoff bound. This settles a classic problem in parallel derandomization, which dates back to the 1980s. Consider the \textit{
Externí odkaz:
http://arxiv.org/abs/2311.13771
We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein inequalities. Our method increases the algorithm's computational work
Externí odkaz:
http://arxiv.org/abs/2311.13764
Autor:
Ghaffari, Mohsen, Portmann, Julian
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy complexity substantially. These algorithms work in the standard CONGE
Externí odkaz:
http://arxiv.org/abs/2305.11639
Autor:
Ghaffari, Mohsen, Portmann, Julian
Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the notion of awake complexity for distributed algorithms, which measures the number of rounds in which a node is awake. In the other rounds, the node is sleeping and performs no compu
Externí odkaz:
http://arxiv.org/abs/2305.06120