{"ID":6497580,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09626","arxiv_id":"2607.09626","title":"New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms","abstract":"Local Computation Algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a special type of sublinear algorithms that, given probing access to a possibly massive input, are required to provide query access to a consistent solution, without maintaining a state between different queries. In this paper, we try to understand LCA through the lens of complexity classifications, described by the following question: Given a target complexity function $f(n)$, is there a problem whose local computation complexity is $f(n)$, up to polylogarithmic factors? We restrict our focus to Locally Checkable Labeling (LCL) problems, which can be seen as constant-degree constraint satisfaction problems. Possible complexity classes of this problem family have been extensively studied in various distributed computation models, including the $\\mathrm{VOLUME}$ model proposed by Rosenbaum and Suomela (2020), which is an invariant of local computation algorithms with additional locality requirements. In this paper, we provide new LCL complexity constructions in the $\\mathrm{VOLUME}$ model, and generalize the results to LCAs. Specifically, we show that there are LCLs whose probe complexities in the $\\mathrm{VOLUME}$ and LCA models are $Θ(\\log^k n)$ and $\\tilde Θ(n^{p/q})$ for any positive integer $k \\ge 1$ and rational $p/q \\in (0,1]$. Our approach, completely different from the approach to a similar result in the distributed $\\mathrm{LOCAL}$ model by Balliu et al. (2018), is to stack instances of complexity $Θ(\\log n)$ and $\\tilde Θ(n^{1/k})$ in the $\\mathrm{VOLUME}$ model constructed by Rosenbaum and Suomela (2020).","short_abstract":"Local Computation Algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a special type of sublinear algorithms that, given probing access to a possibly massive input, are required to provide query access to a consistent solution, without maintaining a state between different queries. In this pap...","url_abs":"https://arxiv.org/abs/2607.09626","url_pdf":"https://arxiv.org/pdf/2607.09626v1","authors":"[\"Sijin Peng\"]","published":"2026-07-10T17:25:22Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.DS\"]","methods":"[]","has_code":false}