research
∙
01/26/2022
Perfect Matching in Random Graphs is as Hard as Tseitin
We study the complexity of proving that a sparse random regular graph on...
share
research
∙
07/09/2019
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Assuming the Unique Games Conjecture, we show that existing approximatio...
research
∙
04/02/2019
Simplified inpproximability of hypergraph coloring via t-agreeing families
We reprove the results on the hardness of approximating hypergraph color...
research
∙
10/05/2018
Improved Inapproximability of Rainbow Coloring
A rainbow q-coloring of a k-uniform hypergraph is a q-coloring of the ve...
research
∙
12/27/2017