11 citations · 27 across the 17 of their papers we have counts for
Showing 2019 · cs.CCShow all
2 papers · 2 filters
cs.CC2019
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Per Austrin, Aleksa Stankovic
Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove t…
cs.CC2019
Simplified inpproximability of hypergraph coloring via t-agreeing families
Per Austrin, Amey Bhangale, Aditya Potukuchi
We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal -agreeing families of . Sp…