Difference between revisions of "Open Problems:97"
(Created page with "{{Header |title=Local Computation Algorithm for MIS |source=wola19 |who=Mohsen Gaffhari }} In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$,...") |
m (Krzysztof Onak moved page Waiting:Local Computation Algorithm for MIS to Open Problems:97 without leaving a redirect) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=wola19 | |source=wola19 | ||
|who=Mohsen Gaffhari | |who=Mohsen Gaffhari | ||
}} | }} | ||
| − | |||
In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$, an algorithm gets, upon query any vertex $v$ of its choosing, the list of neighbors of $v$. In this model, the current state-of-the-art for the query complexity of computing a Maximal Independent Set (MIS) for graph $G$ of maximum degree at most $\Delta$ is an upper bound of | In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$, an algorithm gets, upon query any vertex $v$ of its choosing, the list of neighbors of $v$. In this model, the current state-of-the-art for the query complexity of computing a Maximal Independent Set (MIS) for graph $G$ of maximum degree at most $\Delta$ is an upper bound of | ||
$$ | $$ | ||
Latest revision as of 18:16, 26 August 2019
| Suggested by | Mohsen Gaffhari |
|---|---|
| Source | WOLA 2019 |
| Short link | https://sublinear.info/97 |
In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$, an algorithm gets, upon query any vertex $v$ of its choosing, the list of neighbors of $v$. In this model, the current state-of-the-art for the query complexity of computing a Maximal Independent Set (MIS) for graph $G$ of maximum degree at most $\Delta$ is an upper bound of $$ \Delta^{O(\log\log \Delta)} \operatorname{poly}\!\log n $$ queries.
Question: Does there exist a $\operatorname{poly}(\log n, \Delta)$-query LCA for MIS?
