2 citations · 2 across the 2 of their papers we have counts for
4 papers · 1 filter
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…
On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if al…
On the Approximability of Presidential Type Predicates
Neng Huang, Aaron Potechin
Given a predicate , let be the set of constraint satisfaction problems whose constraints are of the form . We say that is approximable…
On the Decision Tree Complexity of String Matching
Xiaoyu He, Neng Huang, Xiaoming Sun
String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision t…