# Going for Speed: Sublinear Algorithms for Dense r-CSPs

arXiv: https://arxiv.org/abs/1407.7887 · HTML: https://mlsanity.com/paper/1407.7887/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2014.

## Built on by (most cited first, 2 of 2)

- [Multidimensional Scaling: Approximation and Complexity](https://mlsanity.com/paper/2109.11505/) (2021)
- [Approximating a RUM from Distributions on k-Slates](https://mlsanity.com/paper/2305.13283/) (2023)

## Abstract (arXiv)

We give new sublinear and parallel algorithms for the extensively studied problem of approximating n-variable r-CSPs (constraint satisfaction problems with constraints of arity r up to an additive error. The running time of our algorithms is O(n/ε2) + 2O(1/ε2) for Boolean r-CSPs and O(k4 n / ε2) + 2O(log k / ε2) for r-CSPs with constraints on variables over an alphabet of size k. For any constant k this gives optimal dependence on n in the running time unconditionally, while the exponent in the dependence on 1/ε is polynomially close to the lower bound under the exponential-time hypothesis, which is 2^Omega(ε^(-1/2)). For Max-Cut this gives an exponential improvement in dependence on 1/ε compared to the sublinear algorithms of Goldreich, Goldwasser and Ron (JACM'98) and a linear speedup in n compared to the algorithms of Mathieu and Schudy (SODA'08). For the maximization version of k-Correlation Clustering problem our running time is O(k4 n / ε2) + kO(1/ε2), improving the previously best n k^O(1/ε3 log k/ε) by Guruswami and Giotis (SODA'06).