Orthogonal Vectors Conjecture and Sparse Graph Properties Workshop
Exploring the computational complexity of low-polynomial-time problems, this workshop delves into the Orthogonal Vectors Problem and its conjectures. It introduces concepts like the Sparse OV Problem, first-order graph properties, and model checking in graphs. Discussing the hardness of problems related to disjoint sets and model checking, the workshop sheds light on implications for complexity theory and theoretical computer science.
- Computational complexity
- Sparse graphs
- Orthogonal vectors
- Model checking
- Theoretical computer science
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computational Complexity of Low-Polynomial Time Problems Workshop Dec. 3, 2015 Orthogonal Vectors is hard for first-order properties on sparse graphs Jiawei Gao, Russell Impagliazzo UC San Diego
Introduction ? Orthogonal Vectors Problem (OV) 1 1 0 1 1 Input: A set of ? Boolean vectors of dimension ?. (Usually ? is between log? and ??(1).) ? 0 1 0 0 1 1 0 0 1 1 Output: Whether there exist vectors ?, ? such that ? ? = 0. ? ? 1 0 1 0 0 When ? = O(log?), Simple algorithm: O(?2log?) Best algorithm: ?2 (1/ log(?/ log ?)) [AWY 15] 0 1 0 1 0 Orthogonal Vectors Conjecture OV with ? = O(log?) requires time ?2 o(1). Implied by SETH 1 11/28/2024
Introduction ?2 ? Sparse OV ?2 ? FO graph properties OV ?2 ? .. ?2 ? k-clique Hitting set ?? ? Polynomial k-dominating set NP-complete 21 ? ? k-CNF-SAT 2 11/28/2024
Sparse OV Problem 2 Disjoint Sets Bipartite graph with ? edges. An edge ?,? exists iff ? ?. Input: the list of all edges. Output: whether there exists disjoint sets ?1, ?2. OV is a special case when the bipartite graph is very unbalanced. ? 0 1 0 0 1 ? 1 0 1 0 0 1 ?? 2 ?? 3 Question: Whether bipartite graph ? = satisfy 4 ?,? ,? 5 ?1 ? ?2 ? ? ? ((?1,?) ?) ((?2,?) ?) 3 11/28/2024
Sparse OV Conjecture Orthogonal Vectors Conjecture OV with ? = O(log?) requires time ?2 o(1). Sparse Orthogonal Vectors Conjecture 2 Disjoint Sets requires time ?2 o(1). 4 11/28/2024
First-order graph property Graph = binary relations + unary relations. First-order formula ? with k+1 quantifiers (either or ). Input: Graph ? with ? vertices and ? edges. (input size is ?). The model checking problem for ? is to decide whether ? ?. Examples ? ? ? (? ?) (? ?) Hitting Set ?-Clique ( 1?1 ???) ? ?(??,??) ? ?(??,??+1) ? ?-Dominating Set ( 1?1 ???) ( ?+1??+1) ?=1 ? ?-Orthogonal Vectors ( 1?1 ???) ( ?+1?) j=1 (??? = 1) 5 11/28/2024
First-order model checking Model checking for ? + 1 -quantifier formula ? is solvable in O(?? 1?) time. We conjecture it requires (??) time. Model Checking Conjecture Implied by SETH and OVC W.l.o.g. assume input size ? = ?1+o(1). The graph is sparse. For dense graphs: [Williams 14] Decidable in time O(?? 2+?). When ? 9, decidable in time O(??). Require time ??under SETH. 6 11/28/2024
Main Result 2 Disjoint Sets is hard for model checking on graphs, under randomized reductions. Model Checking Conjecture is another name for Sparse OV Conjecture. Theorem If 2 Disjoint Sets can be solved in subquadratic time, then model checking for (? + ?)-quantifier formula (? 2) can be solved in ?(?? ?) by randomized algorithms. 7 11/28/2024
Fine-grained reductions Problem 1 Time ?1(?) Problem 2 Time ?2(?) FGR Preserves fine-grained time complexity of problems. If 2 can be solved substantially faster than ?2? , then 1 can be solved substantially faster than ?1? . 8 11/28/2024
Hardnessin 3-quantifier problems There exists fine-grained reduction from (k+1)-quantifier problems to k-quantifier problems. (? 2) We just need to consider the cases where ? = 2. (k+1)-quantifier problems 3-quantifier problems Time ?2 FGR2 Disjoint Sets Time ?2 k-quantifier problems . . . FGR FGR FGR Time ?? 1 Time ?? Need to show By exhaustive search Theorem 1 2 Disjoint Sets is hard in 3-quantifier problems under randomized fine- grained reductions. 9 11/28/2024
Hardnessin 3-quantifier problems Theorem 2 If problems are solvable in subquadratic time, then problems are solvable in subquadratic time. Theorem 3 2 Disjoint Sets is complete in problems under randomized FGR. Hard problems Easy problems Thm. 3 Thm. 2 2 Disj. Sets O(?3/2) 3-Clique 3-Independent Set Hitting Set Graph Radius 2 Graph Diameter 2 10 11/28/2024
From to Theorem 2 If problems are solvable in subquadratic time, then problems are solvable in subquadratic time. Dense structures [AVWW 16] Hitting Set OV We show the generalized case on sparse graphs. ?1 ?2 ?3? ?1 ?2 ?3? 11 11/28/2024
Completeness in Theorem 3 2 Disjoint Sets is complete in problems under randomized FGR. Lemma These three problems are equivalent under randomized FGR: 2 Disjoint Sets Set Containment 2 Set Covering The only randomized reduction. Other parts of the proof are deterministic. 12 11/28/2024
Basic Problems Set Containment 2 Set Cover 2 Disjoint Sets ?1 ?2 ?1 ?2= ? ?1 ?2= ?1 (? ?1) (? ?2) ?2 ? ? ?1 (? ?1) (? ?2) ?2 ? ? ?1 ?2 ? ? (? ?1) (? ?2) ? ? ? ?1 ?2 ?1 ?2 ?1 ?2 To preserve the sparsity of input graph, we are not allowed to complement the sets directly. 13 11/28/2024
Equivalence of Basic Problems We do Universe-Shrinking Self-Reductions on Basic Problems. ? ? ? ?1 ?1 ?1 ?2 ?2 randomized self reduction ?2 complement sets Problem 2 Problem 1 Problem 1 Preserves fine-grained complexity on sparse graphs. 14 11/28/2024
Equivalence of Basic Problems Reduction from Set Containment to 2 Disjoint Sets The graph is sparse, so there aren t many large-degree vertices. Large degree ( ??) At most O(?1 ?) of them. Exhaustive search on them, and remove them. Small degree (< ??) Self-reduce to a smaller universe ? = ??. Complement all sets on universe ? . Because degree is small, error probability is small. 15 11/28/2024
Universe-shrinking technique Use Bloom Filter to randomly map each element in ? to t = ?? elements in ? independently. :? ? ?. ? = ?1 For set ? ?, let ? = ? ? (?). , ,?? . ? ? ?1 ?2 For Set Containment problem: 1. If ?1 ?2 then ?1 2. If ?1 ?2 but ?1 ?2 ?2 . , an error occurs. Yes instances Yes instances. No instances No instances. (high probability) Yes instances. (unlikely to happen) When ?2is small, probability of false positive is exponentially small. 16 11/28/2024
Hybrid Problem Problems Hybrid Problem Basic Problems Hybrid Problem A combination of Basic Problems ? is partitioned to ?0, ?1, ?2, ?3. A solution (?1,?2) must simultaneously satisfy: 1. ?1 ?0 and ?2 ?0 are disjoint. 2. ?1 ?1 is contained in ?2 ?1. 3. ?1 ?2 contains ?2 ?2. 4. ?1 ?3 ?2 ?3 = ?3. We can construct an instance of the Hybrid Problem of linear size in linear time. 17 11/28/2024
Conclusion ?2 ? FO graph properties Sparse OV .. ?2 ? k-OV Hitting set ?? ? Polynomial k-dominating set NP-complete If SETH is false 21 ? ? k-CNF-SAT 18 11/28/2024
Conclusion ?2 ? Sparse OV ?2 ? ?? ? FO graph properties Polynomial 19 11/28/2024
Open Problems 1. Find a complete (k+1)-quantifier problem for ? > 2. We found complete problems for specific quantifier structures. E.g. k-Orthogonal Vectors is complete for 1 ? problems. But we don t know if k-Orthogonal Vectors is complete for general (k+1)-quantifier problem. 2. Are there similar results for dense graphs? If we measure by #edges, we go through all (k+1) variables using time O(??). If we measure by #vertices in dense graphs, there won t be such advantage. 3. Model checking in higher-arity structures. From graph properties to hypergraph properties. 20 11/28/2024
Open Problems 4. Completeness results for dynamic programming. Can we clean up more mess in the graph? Many SETH-hard problems have dynamic programming algorithms. When can t we do better than dynamic programming? Thank you. 21 11/28/2024
