Workshop of Summer School on Algorithms and Lower Bounds
Satellite workshop of ICALP 2018
Prague, Czech Republic
Monday 9 July 2018
The workshop is devoted to presentations of own research by selected participants of the Summer School on
Algorithms and Lower Bounds. The focus of the workshop is on problems related fine-grained complexity.
Everyone is welcome to register and attend.
Every presentation is given 30 minutes in total, which is expected to be 25 minutes of talk and 5 minutes of questions. Details of the schedule can be found below.
Workshop Schedule (tentative)
Abstracts
14:00-14:30 Diptarka Chakraborty (Charles University)
Tight cell probe bounds for succinct Boolean matrix-vector multiplication
Abstract: The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems, see Henzinger et al. [STOC'15]. In this talk, we discuss the cell probe complexity (that is, we only charge for memory accesses, while computation is free) of Boolean matrix-vector multiplication. In a recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure. Their cell probe data structure answers queries in ~O(n^7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional ~O(n^7/4) bits on the side. In this talk we present a lower bound showing that any data structure storing r bits on the side, with n < r < n^2 must have query time t satisfying tr = Omega(n^3). For r ≤ n, any data structure must have t = ~Omega(n^2). Since lower bounds in the cell probe model also apply to classic word-RAM data structures, the lower bounds naturally carry over. We complement the lower bound with a new succinct cell probe data structure with query time ~O(n^3/2) storing just ~O(n^3/2) bits on the side.
Based on a joint work with Lior Kamma and Kasper Green Larsen.
14:30-15:00 Burno Loff (University of Porto)
Simulation beats richness: New data-structure lower bounds
Abstract:
We develop a technique for proving lower bounds in the setting of asymmetric communication,
a model that was introduced in the famous works of Miltersen (STOC’94) and Miltersen, Nisan,
Safra and Wigderson (STOC’95). At the core of our technique is a novel asymmetric simulation theorem.
As applications of this technique, we obtain the following results:
Joint work with Arkadev Chattopadhyay, Michal Koucký and Sagnik Mukhopadhyay.
15:00-15:30 Ludmila Glinskih (St. Petersburg Department of V. A. Steklov Institute of Mathematics)
Lower bound for read-once nondeterministic branching program for satisfiable Tseitin formula using tree-width
Abstract: In this talk, we present a proof that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an n by n grid graph has size at least 2^{Omega(n)}. Then using the Excluded Grid Theorem of Robertson and Seymour we show that for an arbitrary graph G(V,E) any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on G has size at least 2^{Omega(tw(G)^delta)} for all delta < 1/36 , where tw(G) is the treewidth of G. We will also show an upper bound O(|E| 2^{pw(G)}), where pw(G) is the pathwidth of G. This is a joint work with Dmitry Itsykson.
16:00-16:30 Danil Sagunov (Saint Petersburg Academic University)
Lower bounds and exact exponential algorithms for the Target Set Selection problem.
Abstract: We consider the Target Set Selection problem. The problem naturally arises in many fields like economy, sociology, medicine. In the Target Set Selection problem one is given a graph G with a function thr from V (G) to non-negative integers and integers k and m. The goal of the problem is to activate at most k vertices initially so that at the end of the activation process there is at least m activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) vertex v becomes activated if at least thr(v) of its neighbours are activated. The problem and its different special cases were extensively studied from approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others.
Despite the extensive study of the problem it is still unknown whether the problem can be solved in (2-eps)^n time for some eps > 0. We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by m is W [1]-hard even when all thresholds or all dual thresholds are constant.
Joint work with Ivan Bliznets.
16:30-17:00 Thatchaphol Saranurak (KTH)
Dynamic minimum spanning tree in sub-polynomial worst-case update time
Abstract: I will present our recent progress on the question "is there a dynamic algorithm with small worst-case update time" for the spanning forest problem, which is among central problems in dynamic algorithms on graphs. Our result guarantees an n^o(1) worst-case update time with high probability, where n is the number of nodes. The best worst-case bounds prior to our work are (i) the long-standing O(sqrt n) bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] (which is slightly improved by a O(sqrt log n) factor by [Kejlberg-Rasmussen, Kopelowitz, Pettie, Thorup ESA'16]) and (ii) the polylogarithmic bound of [Kapron, King and Mountjoy SODA'13] which works under an oblivious adversary assumption (our result does not make such assumption). The crucial techniques are about expanders: 1) an algorithm for decomposing a graph into a collection of expanders in near-linear time, and 2) an algorithm for "repairing" the expansion property of an expander after deleting some edges of it. These techniques can be of independent interest.
This talk is based on results by [Nanongkai, Saranurak and Wulff-Nilsen, FOCS'17], [Nanongkai and Saranurak, STOC'17] and [Wulff-Nilsen, STOC'17].
17:10-17:40 Petr Ryšavý (Czech Technical University)
Estimating Levenshtein distance from sequencing data
Abstract: In bioinformatics, a typical task is clustering of sequences using hierarchical clustering algorithms. Those algorithms produce dendrograms which represent evolutionary trees. In an ideal case, the input consists of DNA sequences of several organisms. Unfortunately, current sequencing technology does not allow reading the whole sequence. Instead, only short substrings, called reads, are sequenced. As more and more data are published only on read-level, algorithms that can work with those incomplete data are needed. In our work, we estimate the Levenshtein distance, one of the possible measures of the evolutionary distance, between sequences from read-data. We proposed several approaches how to estimate the Levenshtein distance. The first one is based on a read-to-read comparison and the Monge-Elkan distance. The second one uses contigs, which are parts of the sequence that can be easily assembled. Moreover, we proposed a combination of the latter. The experimental results show that the proposed methods have a high correlation with the Levenshtein distance.
17:40-18:10 Debarati Das (Charles University)
Approximating edit distance within constant factor in truly sub-quadratic time
Abstract: The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. In this paper we study the computational problem of approximating the edit distance between a pair of strings.
The problem of computing the exact edit distance can be solved using a classical dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) show that one can compute an approximation to the edit distance within approximation factor poly(log n) in nearly linear time. Recently, Abboud and Backurs (ITCS'17) showed that approximating edit distance within (1+o(1))-factor in truly sub-quadratic time implies circuit lower bounds. This raises the question whether edit distance can be approximated within constant factor in truly sub-quadratic time.
In this talk we affirmatively answer this question: We provide an algorithm whose running time is bounded by O(n^{2-2/7}) that approximates the edit distance up-to constant factor. Our approximation algorithm is based on a new yet simple paradigm.
Joint work with Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký and Mike Saks.
Michal Koucký (Charles University)
This workshop receives funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616787.