Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs by Yuichi Yoshida
Explore lower bounds on query complexity for testing bounded-degree Constraint Satisfaction Problems (CSPs) through a detailed analysis of Max CSP inputs, approximation algorithms, and known results. The study delves into the significance of constant-time approximation and the bounded-degree model, providing insights into the complexities of Max XOR problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lower Bounds on Query Complexity for Testing Bounded- Degree CSPs Yuichi Yoshida Kyoto University & Preferred Infrastructure
Max CSP (Constraint Satisfaction Problem) Input: I = (V, ?) V: variables ?: constraints Objective: satisfy constraints as many as possible by assigning values to variables Ex. Max (2-)XOR V = {x1, x2, x3}, opt(I) = 2 (x1= 1, x2= 0, x3= 1)
Approximation Max XOR is NP-Hard in general. How about approximation? Value x is called -approximation to x* if x* x x*
Known Results for Poly-Time Approximation of Max XOR Satisfiable inputs: 1 Complexity Complexity P (propagataion) General inputs: 0.5 0.878... 0.878...+ 16/17+ Complexity Complexity P (random assignment) P (SDP) [GW95] UG-Hard [KKMO08] NP-Hard [Has01]
Constant-time Approximation Want to design faster algorithm (O(1) time) Value x is called ( , )-approximation to x* if x* - n x x* Need oracle access to inputs bounded-degree model 1. 2.
Bounded-Degree Model [GR02] Only consider inputs with degree bound d. degree: # of constraints containing the variable. I = (V, ?) is given as oracle OI: V [d] ?. OI(v, i) = i-th constraint containing v. x2 x1 x3 Query complexity: # of accesses to OI
Known Results for Const-Time Approximation of Max XOR Satisfiable inputs: 1 Query complexity Query complexity (n1/2) [GR99] Complexity Complexity P (propagataion) ~ General inputs: Query complexity Query complexity Complexity Complexity 0.5 O(1) (n1/2) [GR02] (n1/2+ ) P (random assignment) P P (SDP)[GW95] 0.5+ 0.878... ? ? UG-Hard [KKMO08] 0.878...+ (n) [YI10] NP-Hard [Has01] 16/17+
Our result > 0, , , d > 0, any (1/2+ , )-approx. algorithm for Max XOR requires (n1/2+ ) queries. Need (n1/2+ ) queries to beat RA. RA can be done in O(1) time. Break the barrier of n1/2, given by the birthday paradox.
(n1/2) Lower bounds for Max XOR To get lower bounds for randomized (1/2+ , )- approx. algorithm. Yao s minimax principle Suffices to consider lower bounds for determistic algorithm s.t.: Distribution ? of inputs ?1 opt(I) = m(= (n)) Correctly decides, w.p. 2/3, which distrib. generated I ? + opt(I) (1/2+ )m
Construction of ?+ Make d-regular random graph G (d = d( )). Make constraints on G randomly. 1. 2. u v w >0, d>0, I R? + satisfies opt(I) (1/2 + )m w.h.p.
Construction of ?1 Make G as before. Choose assignment randomly. Make constraints so that each constraint is satisfied by . u (1) 1. 2. 3. v (0) w (0) I R?1 satisfies opt(I) = m.
(n1/2) Lower bounds for Max XOR Knowledge (graph): subgraph an algorithm A has seen. ?1: knowledge distrib. on ?1. ? + : knowledge distrib. on ? + . It suffices to show dTV(?1, ? + ) = o(1)[GR02]
(n1/2) Lower bounds for Max XOR The probability that o(n1/2)-query deterministic algorithm on I R? finds cycles is o(1). [GR02] ? + ?1 dTV(?1, ? + ) = o(1). q.e.d.
What if we have found a cycle? Can check the consistency of constraints. u v w ?1 and ? + are distinguishable by O(n1/2) queries. Cannot get a lower bound of (n1/2+ )
Construction of ?1- Make G as previous case. Choose assignment randomly. Make constraints so that each constraint is satisfied by . w.p 1- . u (1) 1. 2. 3. v (0) w (0) I R?sat satisfies opt(I) (1-O( ))m w.h.p.
Key Lemma H = (V, E+e): knowledge made by O(n1/2+ )-query algorithm on ?1- . Wecannot guess the value of v from the value of u and constraints on E. u (u x) (...) x ( y) e y (...) (...) v
Proof Sketch Cannot guess the constraint on e from constraints on E. Consider how dTV(?1- , ? + ) increases. e do not create a new cycle: no increase e creates new cycle:increases by O(1/nc( )). 1. 2. 2. occurrs at most nO( ) times. By choosing small enough, we have dTV(?1- , ? + ) = o(1).
Symmetric Predicates P: {0,1}k {0,1} is symmetric: P(x) = P(y) if |x| = |y| P(y) = P( ) Ex. NAE(u, v, w): u, v, w are not all equal. XOR(x, y, z, w) = x y z w EQU(x1, , xk): satisfied when x1 = x2= = xk
Lower Bounds for Symmetric Predicates Let P be symmetric predicate of arity k 3 except EQU. > 0, , , d > 0, any(|P-1(1)|/2k+ , )-approx. algorithm for Max CSP(P) needs (n1/2+ ) queries even if inputs are satisfiable. > 0, (1, )-approx. algorithm exists for Max EQU with O(n1/2) queries if inputs are satisfiable. ~
Other Results predicate P of arity k 3 s.t. every (2k/2k+ , )- approx. algorithm needs (n) queries. Borrow techqniques from showing integrality gaps in Lasserre hierarchy. Every (d/polylog d, )-approx. algorithm for maximum independent set needs (n) queries.
Future Work Correct bound for (1/2+ , )-approx. algorithm of Max XOR: O(n1/2+ )? or (n)? Make use of SDP, random walk, spectral algorithm in sublinear time? General Domain Seems Hellinger distance is much easier to deal with for analysis.
