5 citations · 8 across the 6 of their papers we have counts for
6 papers
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…
Improved Approximability Result for Test Set with Small Redundancy
Peng Cui
Test set with redundancy is one of the focuses in recent bioinformatics research. Set cover greedy algorithm (SGA for short) is a commonly used algorithm for test set with redundan…
A Tighter Analysis of Setcover Greedy Algorithm for Test Set
Peng Cui
Setcover greedy algorithm is a natural approximation algorithm for test set problem. This paper gives a precise and tighter analysis of performance guarantee of this algorithm. The…