1 citations · 1 across the 2 of their papers we have counts for
2 papers
cs.DS2010★ 1 cited
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
Yuichi Yoshida
In this paper, we consider lower bounds on the query complexity for testing CSPs in the bounded-degree model. First, for any ``symmetric'' predicate except…
cs.DS2010
Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP
Yuichi Yoshida
Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best…