Falsifying SETH and Orthogonal Vectors Conjecture

more consequences of falsifying seth n.w
1 / 21
Embed
Share

Explore the consequences of falsifying the Strong Exponential Time Hypothesis (SETH) and the Orthogonal Vectors Conjecture in the realm of fine-grained complexity theory. Discover the implications for classic complexity theory, multivariate complexity, problem-solving approaches like ?-SAT and Orthogonal Vectors, and more.

  • Complexity Theory
  • Fine-grained Complexity
  • SETH
  • Orthogonal Vectors
  • Conjectures
rayaanacharya
bcyn Follow

Uploaded on | 1 Views

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.

Download 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.

E N D

Presentation Transcript

  1. (More) Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture or A Sample of Fine-grained Complexity Jesper Nederlof joint work with Karl Bringmann, Amir Abboud, Holger Dell (Slides partly by Karl Bringmann and Holger Dell)

  2. Classic Complexity Theory Integer Linear Programming Satisfiability Maximum Matching Travelling Salesperson Longest common subsequence Clique Linear Programming Polynomial time Not in polynomial time unless P=NP

  3. Fine-grained Complexity Multivariate Complexity k O(nk ) O(2kn) Exponential Time Algorithms Complexity in P O(n ) O*(2 n ) O*(1.34 n) O*(2n ) O(n2) ... 2O(n) n! n ? ( ) suppresses factors poly in input size

  4. Fine-Grained Complexity OV, ?2 APSP, ?3 3SUM, ?2 SAT, 2? SETH

  5. Fine-Grained Complexity Problem ?-SAT: Given formula in ?-CNF with ? variables, is it satisfiable? ?1 ?2 ?3 ?2 ?3 ?5 ( ?1 ?4 ?5) Strong Exponential Time Hypothesis: [IP 01] SAT, 2? SETH ? > 0 ?:?-SAT has no ? (21 ? ?)-time algorithm Example Implications: [CDLMNOPSW 16] Hitting Set, Set Splitting, NAE-SAT: ? (2?) but not ? ((2 ?)?) Independent Set: ? (2??) but not ? ((2 ?)??) [LMS 11] [B 17, ABHS 18+] Subset Sum: ?(? + ?) but not ?1 ?2?(?)

  6. Fine-Grained Complexity OV, ?2 Problem Orthogonal Vectors: Given sets ?,? {0,1}?of size ?, are any ? ?,? ? orthogonal? ( ??? ??= 0) OV-Hypothesis: (moderate dimension) SAT, 2? SETH ?,? > 0: OV in ? = ?? has no ?(?2 ?)-time algorithm Example Implications: [BI 15,ABVW 15,BK 15,VWR 13,B 14,BI 16,BGL 17] No ?(?2 ?) algorithm for: Edit Distance, LCS, Diameter-2, Frechet distance, RegExp Matching, ... No ?(? ?2 ?) algorithm for All Pairs Maxflow [KT 17] Dynamic graph algorithms, ...

  7. Fine-Grained Complexity OV, ?2 APSP, ?3 Problem All Pairs Shortest Paths: Given graph ? with distance (weight) per edge compute distance between any two vertices SAT, 2? SETH APSP-Hypothesis: ? > 0: APSP has no ?(?3 ?) algorithm Example Implications: [VWW 10,AGVW 15] No ?(?3 ?) algorithm for: Negative Triangle, Shortest Cycle, Radius, ...

  8. Fine-Grained Complexity OV, ?2 APSP, ?3 3SUM, ?2 Problem 3SUM: Given set ? of ? integers, are there ?,?,? ? with ? + ? = ?? SAT, 2? SETH 3SUM-Hypothesis: ? > 0: 3SUM has no ?(?2 ?) algorithm Example Implications: No ?(?2 ?) algorithm for: Colinearity, Conv3SUM, ... [GO 95,P 10,AVWW 14] No ?(?3 ?) algorithm for ExactWeightTriangle [P 10,VW 09] Dynamic Problems, Listing Triangles, ...

  9. Fine-Grained Complexity OV, ?2 APSP, ?3 3SUM, ?2 Success of fine-grained complexity: These hypotheses explain why we cannot improve running times of fastest algorithms for many problems SAT, 2? SETH Yield reasons to stop searching for faster algorithms Non-matching lower bounds suggest faster algorithms same as for NP-hardness, but not as elegant .. Why are these hypotheses worth introducing, besides mentioned implications?

  10. Reason 1: Decades of Effort OV, ?2 Many people tried Fastest known algorithms for ?-SAT: ?(21 ?/? ?) for some ? > 0 [PPSZ 98] SAT, 2? SETH [MS 85,S 92,K 99,PPZ 97,S 99,DGHKKPRS 02, HSSW 02,BS 03,MS 11,CSTT 13,H 14, ] Not for lack of trying: OV is at least as hard as ?-SAT

  11. Reason 2: Restricted Algorithms OV, ?2 Hypotheses hold for algorithms of some specific form ? ? ? ? ? ? SAT, 2? SETH Standard framework for refuting a ?-SAT instance: Resolution SETH holds for regular resolution and tree-like resolution [BI 13,BT 16] A weak version of SETH holds for `witness compression algorithms [PP 10,D 13] OVH holds for formulas and branching programs [KW 18+]

  12. Reason 3: Circuit Lower Bounds OV, ?2 Falsifying these hypotheses is difficult, since it would imply difficult-to-prove statements If SETH fails then: [W 13,JMV 15] SAT, 2? SETH NEXP is not contained in linear-size VSP-circuits is very likely, but seems difficult to prove

  13. Reason 4: Implications of falsifying hypotheses OV, ?2 Falsifying these hypotheses implies other `amazing algorithms If SETH fails then there are ? 2 ??-time algorithms for: Hitting Set, Set Splitting, NAE-SAT, SAT on restricted circuit classes [CDLMNOPSW 16] SAT, 2? SETH add TC0 If OVH fails then: [GIKW 17] First-order model checking with ? 3 quantifiersis in time ?(?? 1 ?) on structures of total size ?. e.g. ? ? ?:? ?,? ? ?,? ?(?,?) does ? contain a triangle? add a weighted, dense problem ? ? ?:? ?,? ? ?,? does ? have diameter=2?

  14. Our Contributions [ABDN 18] OV, ?2 We find more consequences of falsifying SETH/OVH If SETH fails then: SAT, 2? SETH there are ? 2 ??-time algorithms for sparse-TC0-SAT If OVH fails then: there are ? 2 ??-time algorithms for sparse-TC1-SAT there are ? ?1 ? ?-time algorithms for weighted ?-Clique (even in hypergraphs)

  15. Circuit-SAT

  16. Circuit-SAT ? = class of circuits ? ?-SAT: Given a circuit ? ? on ? variables, is ? satisfiable? ?(?) = inf{ ? | ?-SAT is in time ? (2? ?) } SETH: lim ? ? ? CNF = 1 ?1 ?2 ?? sparsification lemma [IPZ 01] lim ?,? ? ? sparse ? CNF = 1 ..sparse TC0 ? sparse depth , , ,??? circuit lim ?,? ? ? sparse depth d , , ,??? circuit = 1 [ABDN 18] OVH fails: lim ?,? ? ? sparse depth ? log? , , ,??? circuit < 1 [ABDN 18] .. sparse TC1 Proof techniques: Refined Cook-Levin; Depth reduction by Valiant

  17. Weighted k-Clique

  18. Weighted k-Clique 3 OV, ?2 APSP, ?3 1 -2 4 -1 3 -2 [VWW 10] 2 3 1 -1 Neg-?- Clique, ?? SAT, 2? SETH 0 -5

  19. Weighted k-Clique 3 OV, ?2 APSP, ?3 1 -2 4 -1 3 -2 [VWW 10] 2 3 1 -1 Neg-?- Clique, ?? SAT, 2? SETH 0 -5 Problem Negative-?-Clique: Given edge-weighted graph ? is there a k-Clique with negative total edge-weight? Neg-?-Clique-Hypothesis: ? > 0,? 3: Neg-?-Clique has no ?(?? ?) algorithm

  20. Weighted k-Clique 3 OV, ?2 APSP, ?3 1 -2 4 -1 3 -2 [VWW 10] 2 [ABDN 18] 3 1 -1 Neg-?- Clique, ?? SAT, 2? SETH 0 -5 relates two fine-grained hypotheses falsifying OV implies amazing algorithm for Neg-?-Clique Proof technique: chain of tight reductions Neg-?-Clique -> Exact-?-Clique-> Clique in Hypergraphs -> OV

  21. Concluding Remarks Fine-grained complexity is a currently very popular subject Hypotheses are very productive (often lead to faster algorithms if no connection to hypotheses can be made) Two of these hypotheses are SETH (? (2?) is best for ?-CNF-SAT) and OVH ( ? ?2poly ? is best for OV) This work*: If SETH fails then: there are ? 2 ??-time algorithms for sparse-TC0-SAT If OVH fails then: there are ? 2 ??-time algorithms for sparse-TC1-SAT there are ? ?1 ? ?-time algorithms for weighted ?-Clique *Amir Abboud and Karl Bringmann and Holger Dell and JN: More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture. In the conference proceedings of STOC 2018.

Related


No related presentations.

More Related Content