New techniques and tighter bounds for local computation algorithms

作者：

Highlights：

• We introduce d-light graphs, a new family that includes graphs of constant bounded degree and Erdos–Renyi graphs.

• We develop new techniques for bounding the time and space requirements of LCAs.

• We use these techniques to develop algorithms for a large family of problems on d-light graphs.

• For example, we construct an LCA that requires O(log⁡nlog⁡log⁡n) space and O(log2⁡n) time for MIS.

• We show that the above LCA requires O(log⁡log⁡n) time and O(log⁡n) space in expectation.

摘要

•We introduce d-light graphs, a new family that includes graphs of constant bounded degree and Erdos–Renyi graphs.•We develop new techniques for bounding the time and space requirements of LCAs.•We use these techniques to develop algorithms for a large family of problems on d-light graphs.•For example, we construct an LCA that requires O(log⁡nlog⁡log⁡n) space and O(log2⁡n) time for MIS.•We show that the above LCA requires O(log⁡log⁡n) time and O(log⁡n) space in expectation.

论文关键词：Local computation algorithms,Sublinear algorithms,Pseudorandomness

论文评审过程：Received 18 December 2015, Revised 7 May 2016, Accepted 16 May 2016, Available online 3 June 2016, Version of Record 21 June 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.05.007