# Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders

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

## Key facts

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

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

- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)

## Abstract (arXiv)

We show sublinear-time algorithms for Max Cut and Max E2Lin(q) on expanders in the adjacency list model that distinguishes instances with the optimal value more than 1-varepsilon from those with the optimal value less than 1-ρ for ρ gg varepsilon. The time complexities for Max Cut and Max 2Lin(q) are widetildeO(frac1φ2ρ · m1/2+O(varepsilon/(φ2ρ))) and widetildeO(poly(fracqφρ)· (mq)1/2+O(q6varepsilon/φ2ρ2)), respectively, where m is the number of edges in the underlying graph and φ is its conductance. Then, we show a sublinear-time algorithm for Unique Label Cover on expanders with φ gg ε in the bounded-degree model. The time complexity of our algorithm is widetildeOd(2^qO(1)·φ1/q· varepsilon-1/2· n^1/2+qO(q)· varepsilon^41.5-q· φ-2), where n is the number of variables. We complement these algorithmic results by showing that testing 3-colorability requires Omega(n) queries even on expanders.