98,023 research outputs found
Improved Sublinear-Time Edit Distance for Preprocessed Strings
Full text linkWe study the problem of approximating the edit distance of two strings in
sublinear time, in a setting where one or both string(s) are preprocessed, as
initiated by Goldenberg, Rubinstein, Saha (STOC '20). Specifically, in the -gap edit distance problem, the goal is to distinguish whether the edit
distance of two strings is at most or at least . We obtain the following
results:
* After preprocessing one string in time , we can solve -gap edit distance in time .
* After preprocessing both strings separately in time , we can
solve -gap edit distance in time .
Both results improve upon some previously best known result, with respect to
either the gap or the query time or the preprocessing time.
Our algorithms build on the framework by Andoni, Krauthgamer and Onak (FOCS
'10) and the recent sublinear-time algorithm by Bringmann, Cassis, Fischer and
Nakos (STOC '22). We replace many complicated parts in their algorithm by
faster and simpler solutions which exploit the preprocessing.Comment: Appears at ICALP '2
Joshua Davis: Author of Spare Parts
Full text linkCitation: K-State First (2016). Joshua Davis: Author of Spare Parts [Flier]. Manhattan, Kansas: K-State First.Flyer advertising Joshua Davis's author talk at Kansas State University
A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties
No full textAn important class of problems in logics and database theory is given by fixing a first-order property psi over a relational structure, and considering the model-checking problem for psi. Recently, Gao, Impagliazzo, Kolokolova, and Williams (SODA 2017) identified this class as fundamental for the theory of fine-grained complexity in P, by showing that the (Sparse) Orthogonal Vectors problem is complete for this class under fine-grained reductions. This raises the question whether fine-grained complexity can yield a precise understanding of all first-order model-checking problems. Specifically, can we determine, for any fixed first-order property psi, the exponent of the optimal running time O(m^{c_psi}), where m denotes the number of tuples in the relational structure?
Towards answering this question, in this work we give a dichotomy for the class of exists^k-forall-quantified graph properties. For every such property psi, we either give a polynomial-time improvement over the baseline O(m^k)-time algorithm or show that it requires time m^{k-o(1)} under the hypothesis that MAX-3-SAT has no O((2-epsilon)^n)-time algorithm. More precisely, we define a hardness parameter h = H(psi) such that psi can be decided in time O(m^{k-epsilon}) if h = 3 unless the h-uniform HyperClique hypothesis fails. This unveils a natural hardness hierarchy within first-order properties: for any h >= 3, we show that there exists a exists^k-forall-quantified graph property psi with hardness H(psi)=h that is solvable in time O(m^{k-epsilon}) if and only if the h-uniform HyperClique hypothesis fails. Finally, we give more precise upper and lower bounds for an exemplary class of formulas with k=3 and extend our classification to a counting dichotomy
Approximability of the Discrete Fréchet Distance
Full text linkThe Fréchet distance is a popular and widespread distance measure for point sequences and for curves. About two years ago, Agarwal et al [SIAM J. Comput. 2014] presented a new (mildly) subquadratic algorithm for the discrete version of the problem. This spawned a flurry of activity that has led to several new algorithms and lower bounds.
In this paper, we study the approximability of the discrete Fréchet distance. Building on a recent result by Bringmann [FOCS 2014], we present a new conditional lower bound that strongly subquadratic algorithms for the discrete Fréchet distance are unlikely to exist, even in the one-dimensional case and even if the solution may be approximated up to a factor of 1.399.
This raises the question of how well we can approximate the Fréchet distance (of two given d-dimensional point sequences of length n) in strongly subquadratic time. Previously, no general results were known. We present the first such algorithm by analysing the approximation ratio of a simple, linear-time greedy algorithm to be 2^Theta(n). Moreover, we design an alpha-approximation algorithm that runs in time O(n log n + n^2 / alpha), for any alpha in [1, n]. Hence, an n^epsilon-approximation of the Fréchet distance can be computed in strongly subquadratic time, for any epsilon > 0
Fast n-Fold Boolean Convolution via Additive Combinatorics
Full text linkWe consider the problem of computing the Boolean convolution (with wraparound) of n vectors of dimension m, or, equivalently, the problem of computing the sumset A₁+A₂+…+A_n for A₁,…,A_n ⊆ ℤ_m. Boolean convolution formalizes the frequent task of combining two subproblems, where the whole problem has a solution of size k if for some i the first subproblem has a solution of size i and the second subproblem has a solution of size k-i. Our problem formalizes a natural generalization, namely combining solutions of n subproblems subject to a modular constraint. This simultaneously generalises Modular Subset Sum and Boolean Convolution (Sumset Computation). Although nearly optimal algorithms are known for special cases of this problem, not even tiny improvements are known for the general case.
We almost resolve the computational complexity of this problem, shaving essentially a factor of n from the running time of previous algorithms. Specifically, we present a deterministic algorithm running in almost linear time with respect to the input plus output size k. We also present a Las Vegas algorithm running in nearly linear expected time with respect to the input plus output size k. Previously, no deterministic or randomized o(nk) algorithm was known.
At the heart of our approach lies a careful usage of Kneser’s theorem from Additive Combinatorics, and a new deterministic almost linear output-sensitive algorithm for non-negative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest
Steven Johnson Author Talk Poster
No full textK-State Book NetworkA poster advertising an author talk by Steven Johnson at Kansas State University on September 3, 2014. Steven Johnson's book "The Ghost Map" was the 2014-2015 common book
A Linear-Time n^{0.4}-Approximation for Longest Common Subsequence
Full text linkWe consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length n. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and Künnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This major roadblock for getting faster exact algorithms has led the community to look for subquadratic approximation algorithms for the problem.
Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting (where we make no assumption on the length of the optimum solution or the alphabet size), only a naive O(n^{ε/2})-approximation algorithm with running time Õ(n^{2-ε}) has been known, for any constant 0 < ε ≤ 1. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a O(n^{0.497956})-approximation in expectation; improving upon the naive O(√n)-approximation for the first time.
In this paper, we provide an algorithm that in time O(n^{2-ε}) computes an Õ(n^{2ε/5})-approximation with high probability, for any 0 < ε ≤ 1. Our result (1) gives an Õ(n^{0.4})-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time O(n^{2-ε}), improving upon the naive bound of O(n^{ε/2}) for any ε, and (3) instead of only in expectation, succeeds with high probability
Ramanujan's mock theta functions and their applications (after Zwegers and Ono-Bringmann)
No full textThis is an important expository paper based on recent work of \\it K. Bringmann and \\it K. Ono [Ann. Math. (2) 171, No. 1, 419--449 (2010; Zbl 05712731)] and \\it S. P. Zwegers [Contemp. Math. 291, 269--277 (2001; Zbl 1044.11029), ``Mock theta functions.'' Utrecht: Universiteit Utrecht, Faculteit Wiskunde en Informatica (Thesis) (2002; Zbl 1194.11058), Ramanujan J. 20, No. 2, 207--214 (2009; Zbl 1207.11053), and Bull. Lond. Math. Soc. 42, No. 2, 301--311 (2010; Zbl 1198.11047)] on Ramanujan's mock theta functions. These are certain q-series which belong to at least one (and presumably to all) of the following three families of functions: Appell-Lerch sums, quotients of indefinite binary theta series by unary theta series, and Fourier coefficients of meromorphic Jacobi forms. After giving some background, the author briefly reviews Zwegers' study of the transformation properties of these three families of functions and his construction of non-holomorphic correction terms used to make these functions modular. Motivated by Zwegers' work, the author then introduces the notion of a mock modular form and its shadow, discusses the relation between mock modular forms and the harmonic weak Maass forms of Bruinier and Funke, and collects a number of new examples. Finally, the author touches on some of Bringmann and Ono's applications of these ideas to the study of ranks of partitions
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
Full text linkTree-adjoining grammars are a generalization of context-free grammars that are well suited to model human languages and are thus popular in computational linguistics. In the tree-adjoining grammar recognition problem, given a grammar G and a string s of length n, the task is to decide whether s can be obtained from G. Rajasekaran and Yooseph’s parser (JCSS’98) solves this problem in time O(n^2w), where w < 2.373 is the matrix multiplication exponent. The best algorithms avoiding fast matrix multiplication take time O(n^6). The first evidence for hardness was given by Satta (J. Comp. Linguist.’94): For a more general parsing problem, any algorithm that avoids fast matrix multiplication and is significantly faster than O(|G|·n^6) in the case of |G| = Theta(n^12) would imply a breakthrough for Boolean matrix multiplication. Following an approach by Abboud et al. (FOCS’15) for context-free grammar recognition, in this paper we resolve many of the disadvantages of the previous lower bound. We show that, even on constant-size grammars, any improvement on Rajasekaran and Yooseph’s parser would imply a breakthrough for the k-Clique problem. This establishes tree-adjoining grammar parsing as a practically relevant problem with the unusual running time of n^2w , up to lower order factors
Fine-Grained Complexity Theory (Tutorial)
No full textSuppose the fastest algorithm that we can design for some problem runs in time O(n^2). However, we want to solve the problem on big data inputs, for which quadratic time is impractically slow. We can keep searching for a faster algorithm, but maybe none exists. Is there any reasoning that provides evidence against significantly faster algorithms, and thus allows us to stop searching? In other words, is there an analogue of NP-hardness for polynomial-time problems?
In this tutorial, we will give an introduction to fine-grained complexity theory, which allows to rule out faster algorithms by proving conditional lower bounds via fine-grained reductions from certain key conjectures. We will define these terms and show exemplary lower bounds
- …
