Open Problems:97 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Local Computation Algorithm for MIS to Open Problems:97 without leaving a redirect

2019-08-26T18:16:48Z

Krzysztof Onak moved page Waiting:Local Computation Algorithm for MIS to Open Problems:97 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-26T18:16:31Z

Updating the header

Ccanonne: 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)$,..."

2019-08-07T21:14:37Z

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)$,..."

New page

{{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)$, 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?

← Older revision	Revision as of 18:16, 26 August 2019
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=wola19
 |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
 $$