Applications of Random Algebraic Constructions to Hardness of Approximation

Boris Bukh, Karthik C. S., Bhargav Narayanan

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixe…