Author

K. Makarychev

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

Sharper Gaussian Covers in the Bansal--Huang--Lee Coloring Framework

Bansal, Huang, and Lee recently gave a polynomial-time algorithm that colors every $3$-colorable graph on $n$ vertices with $O(n^{0.19539})$ colors. We improve their bound to $O(n^{0.17794})$ colors. The improvement comes from a sharper rule for combining Gaussian covers. We prove the rule from Ehrhard's inequality by...

K. Makarychev, Yu. S. Makarychev · 0 citations

Preprint Oct 2026

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

We give a polynomial-time algorithm that achieves an $\alpha_{GW} + \tilde{\Omega}(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $\alpha_{GW}+\tilde{\Omega}(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show...

Rares-Darius Buhai, Suprovat Ghoshal, Pravesh K. Kothari et al. · 0 citations