Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

被引:31
作者
Abboud, Amir [1 ]
Williams, Virginia Vassilevska [1 ]
Yu, Huacheng [1 ]
机构
[1] Stanford Univ, Stanford, CA 94305 USA
来源
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2015年
关键词
DYNAMIC TRANSITIVE CLOSURE; LOWER BOUNDS; EXPONENTIAL-TIME; ALGORITHM; CONNECTIVITY; COMPLEXITY;
D O I
10.1145/2746539.2746594
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining "less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including: Tight n(3-o(1)) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs. New n(1-o(1)) lower bounds for the amortized update and query times of dynamic algorithms for single-source reachability, strongly connected components, and Max-Flow. New n(1.5-o(1)) lower bound for computing a set of n st-maximum-flow values in a directed graph with n nodes and O(n) edges. There is a hierarchy of natural graph problems on n nodes with complexity n(c) for c is an element of (2, 3). Only slightly non-trivial consequences of this conjecture were known prior to our work. Along the way we also obtain new conditional lower bounds for the Single-Source-Max Flow problem.
引用
收藏
页码:41 / 50
页数:10
相关论文
共 73 条
[1]  
Abboud A., 2014, FOCS
[2]  
Abboud A, 2014, LECT NOTES COMPUT SC, V8737, P1, DOI 10.1007/978-3-662-44777-2_1
[3]  
Abboud A, 2014, LECT NOTES COMPUT SC, V8572, P39
[4]  
Abboud A, 2013, LECT NOTES COMPUT SC, V7965, P1
[5]  
Abboud Amir, 2015, SODA
[6]  
Amir A, 2014, LECT NOTES COMPUT SC, V8572, P114
[7]  
[Anonymous], ABS13126713 CORR
[8]  
Aronov Boris, 2005, P SODA
[9]   Subquadratic algorithms for 3SUM [J].
Baran, Ilya ;
Demaine, Erik D. ;
Patrascu, Mihai .
ALGORITHMICA, 2008, 50 (04) :584-596
[10]  
Barequet Gill., 1999, Proc. of the 10th SODA, P862