https://sublinear.info/index.php?title=Open_Problems:97&feed=atom&action=historyOpen Problems:97 - Revision history2024-03-29T13:21:03ZRevision history for this page on the wikiMediaWiki 1.31.10https://sublinear.info/index.php?title=Open_Problems:97&diff=1296&oldid=prevKrzysztof Onak: Krzysztof Onak moved page Waiting:Local Computation Algorithm for MIS to Open Problems:97 without leaving a redirect2019-08-26T18:16:48Z<p>Krzysztof Onak moved page <a href="/index.php?title=Waiting:Local_Computation_Algorithm_for_MIS&action=edit&redlink=1" class="new" title="Waiting:Local Computation Algorithm for MIS (page does not exist)">Waiting:Local Computation Algorithm for MIS</a> to <a href="/index.php?title=Open_Problems:97" title="Open Problems:97">Open Problems:97</a> without leaving a redirect</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 18:16, 26 August 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>Krzysztof Onakhttps://sublinear.info/index.php?title=Open_Problems:97&diff=1295&oldid=prevKrzysztof Onak: Updating the header2019-08-26T18:16:31Z<p>Updating the header</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 18:16, 26 August 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Header</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Header</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|title=Local Computation Algorithm for MIS</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|source=wola19</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|source=wola19</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Mohsen Gaffhari</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Mohsen Gaffhari</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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  </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>$$</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>$$</div></td></tr>
</table>Krzysztof Onakhttps://sublinear.info/index.php?title=Open_Problems:97&diff=1221&oldid=prevCcanonne: 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<p>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)$,..."</p>
<p><b>New page</b></p><div>{{Header<br />
|title=Local Computation Algorithm for MIS<br />
|source=wola19<br />
|who=Mohsen Gaffhari<br />
}}<br />
<br />
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 <br />
$$<br />
\Delta^{O(\log\log \Delta)} \operatorname{poly}\!\log n<br />
$$<br />
queries.<br />
<br />
'''Question:''' Does there exist a $\operatorname{poly}(\log n, \Delta)$-query LCA for MIS?</div>Ccanonne