Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs - Computer Science > Data Structures and AlgorithmsReport as inadecuate




Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: In this paper, we consider lower bounds on the query complexity for testingCSPs in the bounded-degree model.First, for any ``symmetric- predicate $P:{0,1}^{k} \to {0,1}$ except \equwhere $k\geq 3$, we show that every randomized algorithm that distinguishessatisfiable instances of CSPP from instances $|P^{-1}0|-2^k-\epsilon$-farfrom satisfiability requires $\Omegan^{1-2+\delta}$ queries where $n$ is thenumber of variables and $\delta>0$ is a constant that depends on $P$ and$\epsilon$. This breaks a natural lower bound $\Omegan^{1-2}$, which isobtained by the birthday paradox. We also show that every one-sided errortester requires $\Omegan$ queries for such $P$. These results are hereditaryin the sense that the same results hold for any predicate $Q$ such that$P^{-1}1 \subseteq Q^{-1}1$. For EQU, we give a one-sided error testerwhose query complexity is $\tilde{O}n^{1-2}$. Also, for 2-XOR or,equivalently E2LIN2, we show an $\Omegan^{1-2+\delta}$ lower bound fordistinguishing instances between $\epsilon$-close to and $1-2-\epsilon$-farfrom satisfiability.Next, for the general k-CSP over the binary domain, we show that everyalgorithm that distinguishes satisfiable instances from instances$1-2k-2^k-\epsilon$-far from satisfiability requires $\Omegan$ queries. Thematching NP-hardness is not known, even assuming the Unique Games Conjecture orthe $d$-to-$1$ Conjecture. As a corollary, for Maximum Independent Set ongraphs with $n$ vertices and a degree bound $d$, we show that everyapproximation algorithm within a factor $d-\poly\log d$ and an additive errorof $\epsilon n$ requires $\Omegan$ queries. Previously, only super-constantlower bounds were known.



Author: Yuichi Yoshida

Source: https://arxiv.org/







Related documents