Fine-Grained Complexity - Hardness in P - Max Planck Society
[Pages:54]Fine-Grained Complexity Hardness in P
Lecture 1: SETH and OV
Karl Bringmann
Machine Model
Random Access Machine (RAM):
CPU
? memory of ! 1 cells
? can perform all reasonable operations on two cells in ! 1 time (arithmetic + logical operations...)
? can read/write any cell in ! 1 time
storage:
101 011 001 111 ... 100 101 111
cell / word consisting of (log () bits
can recognize palindromes in time !(()
the details do not matter!
Reminder: SETH and OV
Problem !-SAT: Given formula in '-CNF with 1 variables, is it satisfiable?
2, ?25 26 25 ?26 28 (?2, 29 28)
Strong Exponential Time Hypothesis: [Impagliazzo,Paturi'01] # > 0 ': '-SAT has no )(2 ,-. /)-time algorithm
Problem Orthogonal Vectors: Given sets @, B {0,1}G of size 1, are any H @, J B orthogonal? (L HL JL = 0)
OV-Hypothesis: (moderate dimension) # > 0: OV has no )(15-. poly(?))-time algorithm
LD-OV-Hypothesis: (low dimension) # > 0 O > 0: OV in ? = O log 1 has no )(15-.)-time algorithm
SETH
[Williams'05]
LD-OVH
OVH
Reminder: Fine-Grained Reductions
transfer hardness of one problem to another one by reductions
problem ( instance '
size $ ' is a `yes'-instance
reduction
)($) time
()
problem ! instance &
size "($) & is a `yes'-instance
*($) algorithm for + implies a ) $ + *(" $ ) algorithm for if - has no ) $ + *(" $ ) algorithm then + has no *($) algorithm
Reminder: Fine-Grained Reductions
A fine-grained reduction from (", 1) to (#, 1') is an algorithm ! for " with oracle access to # s.t.:
problem , instance *
reduction
problem $
instance *1 size ')
... ...
size ' Properties:
total time %(')
instance *. size '-
for any instance *, algorithm !(*) correctly solves problem " on *
! runs in time %(') = 0(1('))23) for some 4 > 0
for any 7 > 0 there is a 8 > 0 s.t. :-;) 1(':))2= 1('))2?
Landscape of Polytime Problems 3SUM-hard
SETH SAT 2(
[Patrascu, Williams'10]
[Williams'05]
k-DomSet !$
OV !"
[B'14]
Frechet !"
[V-Williams,Roditty'13]
SETH-hard
[Abboud,B,Hermelin, Shabtay'17+]
SubsetSum !+&
[Backurs,Indyk'15]
Edit Distance !"
[B,K?nnemann'15,Abboud, Backurs,V-Williams'15]
3SUM !"
X+Y !"
[Gajentaan,Overmars'95]
GeomBase !"
Colinear !"
Separator !"
PlanarMotion Planning !"
Diameter !"
Dynamic Time Warping !"
APSP-hard
[B,K?nnemann'15, Abboud,Backurs, V-Williams'15]
LCS !"
[B,K?nnemann'15]
Longest Palindromic Subsequence !"
[Impagliazzo]
NFA-Acceptance !"
[Backurs,Indyk'16]
RegExp Matching !"
APSP !#
[Backurs,Dikkala, Tzamos'16]
[V-Williams, Williams'10]
Radius !#
Maximum Submatrix !#
Metricity !#
[B,Gawrychowski, Mozes,Weimann'18]
Betweenness Centrality !#
Tree Edit
Survey: On some fine-grained questions in
Distance !#
algorithms and complexity, V. Vassilevska Williams
NegTriangle !#
I. Easy Example II. Longest Common Subsequence III. Hardness of Approximation IV. Further Topics V. Summary
Landscape of Polytime Problems 3SUM-hard
SETH SAT 2(
[Patrascu, Williams'10]
[Williams'05]
k-DomSet !$
OV !"
[B'14]
Frechet !"
[V-Williams,Roditty'13]
SETH-hard
[Abboud,B,Hermelin, Shabtay'17+]
SubsetSum !+&
[Backurs,Indyk'15]
Edit Distance !"
[B,K?nnemann'15,Abboud, Backurs,V-Williams'15]
3SUM !"
X+Y !"
[Gajentaan,Overmars'95]
GeomBase !"
Colinear !"
Separator !"
PlanarMotion Planning !"
Diameter !"
Dynamic Time Warping !"
APSP-hard
[B,K?nnemann'15, Abboud,Backurs, V-Williams'15]
LCS !"
[B,K?nnemann'15]
Longest Palindromic Subsequence !"
[Impagliazzo]
NFA-Acceptance !"
[Backurs,Indyk'16]
RegExp Matching !"
APSP !#
[Backurs,Dikkala, Tzamos'16]
[V-Williams, Williams'10]
Radius !#
Maximum Submatrix !#
Metricity !#
[B,Gawrychowski, Mozes,Weimann'18]
Betweenness Centrality !#
Tree Edit Distance !#
NegTriangle !#
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- ftp server application guide tp link
- first setup your router go to admin page at http 192 168 8 1
- arduino part 1 type and blink university of minnesota
- 1 466 4 26 cfr ch i 4 1 21 edition
- arduino part 1 type and blink edu
- connections and ip address xerox
- the impact of snp density on quantitative genetic analyses of body size
- how to log in totolink router s setting interface
- analysis of usp residual solvents using agilent j w db‑wax ultra
- binary lesson 6 classful subnetting 24 25 and 26
Related searches
- essays in sociology max weber
- planck constant max planck
- complexity of insertion sort
- hardness in lower left abdomen
- social complexity definition anthropology
- time complexity of fibonacci series
- water hardness in my area
- time complexity of fibonacci
- eval complexity pt
- fine art reproductions in oil
- planck s constant in 1985
- fine arts colleges in usa