Finding Colorings in One-Sided Expanders
Rares-Darius Buhai [email protected] ETH Zurich Yiding Hua [email protected] ETH Zurich David Steurer [email protected] ETH Zurich Andor Vári-Kakas [email protected] ETH Zurich · 2025
Read Finding Colorings in One-Sided Expanders by Rares-Darius Buhai [email protected] ETH Zurich Yiding Hua [email protected] ETH Zurich David Steurer [email protected] ETH Zurich Andor Vári-Kakas [email protected] ETH Zurich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02825.txt.
Description
Rares-Darius Buhai and three co-authors give new algorithms and hardness results for coloring and independent set problems on one sided expander graphs. Expanders are sparse yet highly connected graphs that appear across computer science. On a 3-colorable regular one sided expander, their method finds in polynomial time either a large independent set or a near complete proper 3-coloring.
That result improves a recent breakthrough that found much smaller independent sets in such graphs. A fast approximation for vertex cover on strong expanders also improves on past factors. A new stratification of coloring by matrices yields a sharp split. When the matrix has repeated rows the problem is hard, and when it does not, their algorithms solve it fast.
Catalog record
| CREATOR | Rares-Darius Buhai [email protected] ETH Zurich Yiding Hua [email protected] ETH Zurich David Steurer [email protected] ETH Zurich Andor Vári-Kakas [email protected] ETH Zurich |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 173 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-02825