5 citations · 8 across the 6 of their papers we have counts for
4 papers · 1 filter
Refuting Unique Game Conjecture
Peng Cui
In this short note, the author shows that the gap problem of some -CSPs with the support of its predicate the ground of a balanced pairwise independent distribution can be solve…
Approximation Resistance by Disguising Biased Distributions
Peng Cui
In this short note, the author shows that the gap problem of some 3-XOR is NP-hard and can be solved by running Charikar\&Wirth's SDP algorithm for two rounds. To conclude, the aut…
Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion
Peng Cui
In this paper, the author puts forward a variation of Feige's Hypothesis, which claims that it is hard on average refuting Unbalanced Max 3-XOR under biased assignments on a natura…
On Unique Games with Negative Weights
Peng Cui
In this paper, the author defines Generalized Unique Game Problem (GUGP), where weights of the edges are allowed to be negative. Two special types of GUGP are illuminated, GUGP-NWA…