English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Tighter Connections Between Formula-SAT and Shaving Logs

Abboud, A., & Bringmann, K. (2018). Tighter Connections Between Formula-SAT and Shaving Logs. Retrieved from http://arxiv.org/abs/1804.08978.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0001-3DF7-5 Version Permalink: http://hdl.handle.net/21.11116/0000-0002-6602-9
Genre: Paper
Latex : Tighter Connections Between Formula-{SAT} and Shaving Logs

Files

show Files
hide Files
:
arXiv:1804.08978.pdf (Preprint), 426KB
Name:
arXiv:1804.08978.pdf
Description:
File downloaded from arXiv at 2018-05-03 08:39 Accepted at ICALP'18, 36 pages, v2: corrected some references
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Abboud, Amir1, Author
Bringmann, Karl2, Author              
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-known algorithms for fundamental problems by logarithmic factors. For example, the $O(n^2)$ dynamic programming solution to the Longest Common Subsequence problem (LCS) was improved to $O(n^2/\log^2 n)$ in several ways and using a variety of ingenious tricks. This line of research, also known as "the art of shaving log factors", lacks a tool for proving negative results. Specifically, how can we show that it is unlikely that LCS can be solved in time $O(n^2/\log^3 n)$? Perhaps the only approach for such results was suggested in a recent paper of Abboud, Hansen, Vassilevska W. and Williams (STOC'16). The authors blame the hardness of shaving logs on the hardness of solving satisfiability on Boolean formulas (Formula-SAT) faster than exhaustive search. They show that an $O(n^2/\log^{1000} n)$ algorithm for LCS would imply a major advance in circuit lower bounds. Whether this approach can lead to tighter barriers was unclear. In this paper, we push this approach to its limit and, in particular, prove that a well-known barrier from complexity theory stands in the way for shaving five additional log factors for fundamental combinatorial problems. For LCS, regular expression pattern matching, as well as the Fr\'echet distance problem from Computational Geometry, we show that an $O(n^2/\log^{7+\varepsilon} n)$ runtime would imply new Formula-SAT algorithms. Our main result is a reduction from SAT on formulas of size $s$ over $n$ variables to LCS on sequences of length $N=2^{n/2} \cdot s^{1+o(1)}$. Our reduction is essentially as efficient as possible, and it greatly improves the previously known reduction for LCS with $N=2^{n/2} \cdot s^c$, for some $c \geq 100$.

Details

show
hide
Language(s): eng - English
 Dates: 2018-04-242018-04-302018
 Publication Status: Published online
 Pages: 36 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1804.08978
URI: http://arxiv.org/abs/1804.08978
BibTex Citekey: Abboud_arXiv1804.08978
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show