Testing Assignments of Boolean CSPs and Testable Properties

Testing Assignments of Boolean CSPs Yuichi Yoshida (NII / PFI) based on joint work with Arnab Bhattacharyya (DIMACS / Rutgers)

Algebraic Characterizations of Testable CSPs Yuichi Yoshida (NII / PFI) based on joint work with Arnab Bhattacharyya (DIMACS / Rutgers)

Property Testing Can we test whether a function f : V D satisfies P or far from P efficiently? dist(f, g) = Prx V[f(x) g(x)] f is -far from a property P if dist(x, y) for all g satisfying P. An -tester for P: all functions accept w.p. 2/3 P -far reject w.p. 2/3

Example of Testable Properties All the following properties are constant-query testable. Function f: ?2n {0,1} k-junta Linearity, low-degree polynomial Graph f: V V {0, 1} Triangle-freeness, k-colorability Monotone properties, hereditary properties Properties representable by Szemer di s regularity lemma

Constraint Satisfaction Problems : finite collection of relations CSP( ): set of instances defined by constraints using relations from Two testing problems related to CSPs f represents an instance Dense model Bounded-degree model f represents an assignment of an instance (This talk)

Testing CSP Assignments For a parameter > 0 and a satisfiable CSP( ) instance ? on variable set V and domain D, Input: f: V D Output: Yes if f satisfies ?. No if f is -far from satisfying assignments of ?.

Testing 2-Coloring 2-coloring is testable with O(1/ ) queries. Assume input graph G is connected. If we query f(v), then we have a supposed coloring. When f is -far, at least n vertices are inconsistent. We can find it by randomly sampling O(1/ ) vertices. v v How does affect the query complexity to test CSP( )?

Whats known 2-COL: O(1) CSP( ) (monotonicity testing) O( n), (log n / loglog n) [FLNRRS 02] O(log n/ ) on hypercube [CS 12] 2-SAT: O( n), (log n / loglog n), [FLNRRS 02]. 3-LIN, 3-SAT: (n) [BHR 06] Can we characterize exactly when CSP( ) is constant-query / sublinear-query testable? Yes for list H-homomorphisms [Y. 12] and Boolean CSPs [BY 12].

Polymorphisms determine complexity Pol( ): Set of polymorphisms of Theorem [Jeavons 98]: If CSP( ) is in P, then any CSP( ) with Pol( ) Pol( ) is in P. Theorem [Y. 12]: If CSP( ) is testable with q(n, m, ) queries, then any CSP( ) with Pol( ) Pol( ) is testable with O(1/ ) + q(O(n+m), O(m), O( )) queries Same thing holds for varieties.

Testing List H-Homomorphism

List H-Homomorphism f: V(G) V(H) is a homomorphism from a graph G to a graph H if (f(u),f(v)) E(H) whenever (u,v) G. Given a list constraint L:V(G) 2V(H), f is a list homomorphismif f is a homomorphism and f(v) L(v) for every v V(G). G H { , } / { } { , }

Testing List H-Homomorphisms Completely classify H w.r.t. the query complexity to test LHOM(H): H (1) but not O( n), (log n / log log n) not (n) Query complexity reflexive complete or irreflexive complete bipartite bi-arc

Graph classes Reflexive complete Irreflexive complete bipartite Bi-arc: too messy to define here. A reflexive graph is bi-arc iff it is interval

Connection to Computational Complexity 1. O(1) NL & easy to count 2. O( n) NL 3. not (n) NPC all CSPs non reflexive complete or irreflexive complete bipartite bi-arc easy to count NL

Proof Sketch O(1): adhoc argument. not (n): not admits type 1 LHOM(H) can simulate 3SAT but testing 3SAT requires (n) queries. O( n) admits majority operation next page

O(n ) Run a propagation algorithm ((2,3)-minimality) and get Su, v V(H)2 for each u, v V. Ex. 2-COL u u v v Su,v = {{ , }, { , }} u u v v [Helly property] Any partial assignment satisfying Su,v is extendable to a full satisfying assignment.

O(n ) [Algorithm] (Suppose f satisfies the list constraint.) Query f(v) for each vwith probability (n/ ). if (u, v) with (f(u), f(v)) Su,vthen reject. elseaccept. When f is a list H-homomorphism Always accept. When f is -far U: set of violated pairs. For any vertex cover C of U, f|V\C is extendable to a satisfying assignment (Helly property).

O(n ) [Algorithm] (Suppose f satisfies the list constraint.) Query f(v) for each v with probability (n/ ). if (u, v) with (f(u), f(v)) Su,vthen reject. elseaccept. When f is -far: Any vertex cover has size n A set of n/2 disjoint violated pairs exists. O( (n/ )) vertices is enough to find a violated pair.

Testing Boolean CSPs

Posts Lattice Inclusion structure of Boolean algebras

BF R0 R1 Main Result CSP( ) R2 Contains NU M M0 M1 2-SAT : O(1) : O(n1- ), (log n / log log n) : (n) M2 S2 S2 S2 0 1 S2 01 11 S2 S2 02 12 S2 S2 00 10 S3 S3 0 1 S3 S3 01 11 S3 S3 02 12 S3 S3 D 00 10 S0 S1 S01 D1 S11 S02 S12 S00 S10 D2 Horn 3-SAT L V E L3 L0 L1 V0 E0 V1 E1 V2 L2 E2 N O(1) N2 logn loglogn) O(n1 ), ( 3-LIN I (n) I0 I1 No corresponding NAE 3-SAT I2

Connection to computational complexity For non-trivial Boolean CSPs, O(1) NL Easy to count o(n) NL (n) NPC All CSPs 3SAT Easy to count NL 2SAT 3LIN2 2COL

Components of the Result Pre-existing bounds from [FLNRRS 02], [BHR 06], [Y 12] plus: 1. O(n1-1/k) upper bound for testing CSP( ) with Pol( ) containing a k-near-unanimity operation. f: Dk D is a k-near-unanimity if for all x, y D f(y,x, ,x) = f(x,y,x, ,x) = = f(x, ,x,y) = x. Proof is similar to the majority argument. 2. (n) lower bound for testing Horn 3-SAT. Reduction from 3-LIN! 3. (Some trick to get rid of weights)

Linear Lower Bound for Horn 3-SAT Reduction from hard instances of 3-LIN. ?LIN Unique Neighbor Property

Hard Horn 3-SAT Instance Horn 3-SAT instance ?Horn constructed as follows: for each equation of ?LIN xi + xj + xk = 0 (mod 2) ?Horn contains the 12 constraints: vi vj vk vi vk vj vj vk vi vi vj vk vi vk vjvj vk vi vi vj vk vi vk vjvj vk vi vi vj vk vi vk vj vj vk vi

Reduction from 3-LIN Given assignment fLIN for ?LIN, define assignment fHorn for ?Horn to be: fHorn(vi) = fLIN(xi), fHorn(vi ) = fLIN(xi) Claim: fLIN -far from ?LIN fHorn also -far from ?Horn. Supppose gHorn satisfies ?Horn and is -close to fHorn We show S = {xi | gHorn(vi) = gHorn(vi )} violates UNP!

Example Take a variable vi S and a constraint vi + vj + vk = 0 (vj, vk S) from UNP. Suppose that gHorn(vi) = gHorn(vi ) = 1. From the constraints we have made, gHorn(vj) = gHorn(vj ) = gHorn(vk) = gHorn(vk ) vj and vk must be in S, but it violates UNP.

Restricting Structure Can we characterize query complexity in terms of structure of instances? Gaifman graph ? Theorem: Suppose Pol( ) contains a k-near-unanimity. Then CSP( ) is testable with O(kwlog n) queries on instances whose Gaifman graphs have treewidth w.

Open Questions Other connection between CSPs and property testing? Classification in terms of constraint languages Conservative CSPs? Admits type 1, 2, or 5 (n) queries k-near-unanimity o(n) queries What happens in between? Classification in terms of structure of instances. Is every CSP sublinear-query testable when the Gaifman graph has bounded-treewidth?