Barna Saha

SODA Conference 2025 Conference Paper

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More

• Mina Dalirrooyfard
• Andrea Lincoln
• Barna Saha
• Virginia Vassilevska Williams

FOCS Conference 2025 Conference Paper

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance

• Debarati Das 0001
• Jacob Gilbert
• MohammadTaghi Hajiaghayi
• Tomasz Kociumaka
• Barna Saha

In this paper, we present the first dynamic algorithms for Dyck edit distance and tree edit distance that achieve subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a wellparenthesized expression (i. e. , the Dyck language), while tree edit distance quantifies the minimum number of node insertions, deletions, and substitutions required to transform one rooted, ordered, and labeled tree into another. These problems have been studied extensively since the 1970s, with recent advances in both algorithmic efficiency and fine-grained complexity lower bounds. Despite this progress, no prior work has addressed efficient dynamic algorithms for these problems, even though many real-world applications involve evolving structured data such as LaTeX, JSON, XML, HTML, hierarchical datasets, and RNA secondary structures. We take the first step in this direction by designing new approximation algorithms for Dyck and tree edit distances in the dynamic setting. Our key technical contribution is a set of novel reduction and decomposition techniques that transform instances of Dyck and tree edit distance into efficiently maintainable instances of string edit distance. Leveraging existing dynamic algorithms for string edit distance, we obtain an $n^{o(1)}$ approximation for Dyck edit distance with $n^{o(1)}$ update time. This builds upon and significantly extends prior work on Dyck language decomposition ([Saha, FOCS’14] and [Koucký & Saks; SODA’23]). For tree edit distance, we introduce a new static reduction that improves the best-known approximation bound from $O\left(n^{3 / 4}\right)$ [Akutsu, Fukagawa, and Takasu; Algorithmica, 2010] to $\tilde{O}(\sqrt{n})$. Moreover, while the previous result was restricted to constant-degree trees, ours holds for arbitrary trees. We then extend our reduction dynamically, yielding a dynamic tree edit distance algorithm with an approximation factor of $n^{1 / 2+o(1)}$ and update time $n^{o(1)}$. A core component of our approach is a new dynamic maintenance algorithm for heavy-light decomposition, a widely used technique in tree algorithms. Given its broad applicability, we believe this result is of independent interest. Finally, we introduce a novel static and dynamic decomposition method that achieves an $\tilde{O}(k)$-approximation for tree edit distance when the tree edit distance is at most k; combined with the trivial bound $k \leq n$, this yields a deterministic $\tilde{O}(\sqrt{n})$-approximation. While similar decompositions exist for strings, no prior work has successfully extended them to trees. Our approach breaks this barrier, improving the best-known approximations for tree edit distance both in the static and dynamic setting. In the static setting, our algorithm runs in $\tilde{O}(n)$ time; in the dynamic setting, it only requires a polylogarithmic worst-case update time. The state-of-the-art near-lineartime static algorithm for tree edit distance previously achieved an $O(\sqrt{n})$-approximation [Boroujeni, Ghodsi, Hajiaghayi, and Seddighin; STOC’19].

STOC Conference 2025 Conference Paper

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence

• Jakob Nogler
• Adam Polak 0001
• Barna Saha
• Virginia Vassilevska Williams
• Yinzhan Xu
• Christopher Ye 0001

The tree edit distance (TED) between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of valid operations consisting of insertions, deletions and relabeling of nodes. The tree edit distance is a well-known generalization of string edit distance and has been studied since the 1970s. Its running time has seen steady improvements starting with an O ( n 6 ) algorithm [Tai, J.ACM 1979], improved to O ( n 4 ) [Shasha, Zhang, SICOMP 1989] and to O ( n 3 log n ) [Klein, ESA 1998], and culminating in an O ( n 3 ) algorithm [Demaine, Mozes, Rossman, Weimann, ACM TALG 2010]. The latter is known to be optimal for any dynamic programming based algorithm that falls under a certain decomposition framework that captures all known sub- n 4 time algorithms. Fine-grained complexity casts further light onto this hardness showing that a truly subcubic time algorithm for TED implies a truly subcubic time algorithm for All-Pairs Shortest Paths (APSP) [Bringmann, Gawrychowski, Mozes, Weimann, ACM TALG 2020]. Therefore, under the popular APSP hypothesis, a truly subcubic time algorithm for TED cannot exist. However, unlike many problems in fine-grained complexity for which conditional hardness based on APSP also comes with equivalence to APSP, whether TED can be reduced to APSP has remained unknown. In this paper, we resolve this. Not only we show that TED is fine-grained equivalent to APSP, our reduction is tight enough, so that combined with the fastest APSP algorithm to-date [Williams, SICOMP 2018] it gives the first ever subcubic time algorithm for TED running in n 3 /2 Ω(√log n ) time. We also consider the unweighted tree edit distance problem in which the cost of each edit (insertion, deletion, and relabeling) is one. For unweighted TED, a truly subcubic algorithm is known due to Mao [Mao, FOCS 2022], and later improved slightly by Dürr [Dürr, IPL 2023] to run in O ( n 2.9148 ) time. Since their algorithm uses bounded monotone min-plus product as a crucial subroutine, and the best running time for this product is Õ( n 3+ω/2 )≤ O ( n 2.6857 ) (where ω is the exponent of fast matrix multiplication), the much higher running time of unweighted TED remained unsatisfactory. In this work, we close this gap and give an algorithm for unweighted TED that runs in Õ( n 3+ω/2 ) time.

SODA Conference 2025 Conference Paper

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More

• Barna Saha
• Virginia Vassilevska Williams
• Yinzhan Xu
• Christopher Ye 0001

NeurIPS Conference 2024 Conference Paper

Clustering with Non-adaptive Subset Queries

• Hadley Black
• Euiwoong Lee
• Arya Mazumdar
• Barna Saha

Recovering the underlying clustering of a set $U$ of $n$ points by asking pair-wise same-cluster queries has garnered significant interest in the last decade. Given a query $S \subset U$, $|S|=2$, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. We study a natural generalization of this problem to subset queries for $|S|>2$, where the oracle returns the number of clusters intersecting $S$. Our aim is to determine the minimum number of queries needed for exactly recovering an arbitrary $k$-clustering. We focus on non-adaptive schemes, where all the queries are asked in one round, thus allowing for the querying process to be parallelized, which is a highly desirable property. For adaptive algorithms with pair-wise queries, the complexity is known to be $\Theta(nk)$, where $k$ is the number of clusters. In contrast, non-adaptive pair-wise query algorithms are extremely limited: even for $k=3$, such algorithms require $\Omega(n^2)$ queries, which matches the trivial $O(n^2)$ upper bound attained by querying every pair of points. Allowing for subset queries of unbounded size, $O(n)$ queries is possible with an adaptive scheme. However, the realm of non-adaptive algorithms remains completely unknown. Is it possible to attain algorithms that are non-adaptive while still making a near-linear number of queries? In this paper, we give the first non-adaptive algorithms for clustering with subset queries. We provide, (i) a non-adaptive algorithm making $O(n \log^2 n \log k)$ queries which improves to $O(n \log k)$ when the cluster sizes are within any constant factor of each other, (ii) for constant $k$, a non-adaptive algorithm making $O(n \log{\log{n}})$ queries. In addition to non-adaptivity, we take into account other practical considerations, such as enforcing a bound on query size. For constant $k$, we give an algorithm making $\smash{\widetilde{O}(n^2/s^2)}$ queries on subsets of size at most $s \leq \sqrt{n}$, which is optimal among all non-adaptive algorithms within a $\log n$-factor. For arbitrary $k$, the dependence varies as $\tilde{O}(n^2/s)$.

SODA Conference 2024 Conference Paper

Faster Approximate All Pairs Shortest Paths

• Barna Saha
• Christopher Ye 0001

The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on n vertices, no truly sub-cubic algorithms exist to compute APSP exactly even for undirected graphs. This is popularly known as the APSP conjecture and has played a prominent role in developing the field of fine-grained complexity. The seminal results of Seidel and Zwick show that using fast matrix multiplication (FMM) it is possible to compute APSP on unweighted undirected graphs exactly in Õ ( n ω ) time, and can be approximated within (1 + ɛ ) factor in weighted undirected graphs in time Õ( n ω ) respectively. Here ω is the exponent of FMM, which currently stands at ω = 2. 37188. Moreover even for unweighted undirected graphs, it is not possible to obtain a (2 — ɛ )-multiplicative approximation of APSP for any ɛ > 0 in o ( n ω ) time. Since 2000, a result by Dor, Halperin, and Zwick gave the best 2 approximation algorithm for APSP in unweighted undirected graphs in time Õ( n 7/3 ). This result was recently improved by Deng, Kirkpatrick, Rong, Williams and Zhong to Õ( n 2. 2593 ) using fast min-plus product for bounded-difference matrices which uses FMM as a subroutine (the stated bound here uses new results for computing such min-plus products by Durr). In fact both these results obtain a +2-additive approximation. Recently, Roditty (STOC, 2023) improved the previous bounds for multiplicative 2-approximation of APSP in unweighted undirected graphs giving the best known bound of Õ ( n 2. 25 ). All these algorithms are deterministic. Roditty also considers estimating shortest paths for all paths of length ≥ k for k ≥ 4, and gives improved bounds when the underlying graph is sparse using randomization. Though for dense graphs, the best known bounds still remained at those provided by Dor et al. more than two decades back. In this paper, we provide a multitude of new results for multiplicative and additive approximations of APSP in undirected graphs for both unweighted and weighted cases. We provide new algorithms for multiplicative 2-approximation of unweighted graphs: a deterministic one that runs in Õ ( n 2. 072 ) time and a randomized one that runs in Õ ( n 2. 0318 ) on expectation improving upon the best known bound of Õ ( n 2. 25 ). The algorithm uses FMM as well as new combinatorial insights. For 2-approximating paths of length ≥ k, k ≥ 4, we provide the first improvement after Dor et al. for dense graphs even just using combinatorial methods, and then improve it further using FMM. We next consider additive approximations, and provide improved bounds for all additive β -approximations, β ≥ 4. For example, we achieve a running time of Õ ( n 2. 155 ) for +4 additive approximation improving over the previously known bound of Õ ( n 2. 2 ), and for a +6 additive approximation, our algorithm has a running time of Õ ( n 2. 103 ) as opposed to the Õ ( n 2. 125 ) time that was previously known. For weighted graphs, we show that by allowing small additive errors along with an (1 + ɛ )-multiplicative approximation, it is possible to improve upon Zwick's Õ ( n ω ) algorithm. For example, it is possible to obtain a bi-criteria (1 + ɛ, 2 w u, v ) approximation in Õ ( n 2. 152 ) time for the shortest path distance between all vertex pairs u, v where w u, v is the highest weight edge on the u-v shortest path. Additionally, we provide a landscape of such bi-criteria approximations for weighted and unweighted graphs. Our results point out the crucial role that FMM can play even on approximating APSP on unweighted undirected graphs, and reveal new bottlenecks towards achieving a quadratic running time to approximate APSP.

ICML Conference 2024 Conference Paper

I/O Complexity of Attention, or How Optimal is FlashAttention?

• Barna Saha
• Christopher Ye 0001

Attention is at the heart of the popular Transformer architecture, yet suffers from quadratic time and memory complexity. In a recent significant development, FlashAttention shows that the I/O complexity of attention is the true bottleneck in scaling Transformers. Given two levels of memory hierarchy, a fast cache (e. g. GPU on-chip SRAM) where computation happens and a slow memory (e. g. GPU high-bandwidth memory) where the data resides, the I/O complexity measures the number of accesses to the slow memory. FlashAttention is an I/O-aware algorithm for self-attention that requires $\frac{N^2d^2}{M}$ I/O operations where $N$ is the dimension of the attention matrix, $d$ is the head-dimension and $M$ is the size of cache. Naturally, to further reduce the computational costs of Attention, the authors ask the question: is FlashAttention’s I/O complexity optimal for every value of $M$? We resolve the above question in its full generality by showing an I/O complexity lower bound that matches the upper bound provided by FlashAttention for any values of $M \geq d^2$ within any constant factors. Moreover, our lower bounds do not rely on using combinatorial matrix multiplication for computing the attention matrix: even if one uses fast matrix multiplication, the above I/O complexity bounds cannot be improved. Further, we give a better algorithm with lower I/O complexity for $M < d^2$, and show that it is optimal for combinatorial algorithms. We do so by introducing a new communication complexity protocol for matrix compression, and connecting communication complexity to I/O complexity. We believe this connection could be of independent interest and will find more applications in proving I/O complexity lower bounds in future.

FOCS Conference 2023 Conference Paper

Approximating Edit Distance in the Fully Dynamic Model

• Tomasz Kociumaka
• Anish Mukherjee 0001
• Barna Saha

The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. Given two strings of length at most n, a simple dynamic programming computes their edit distance exactly in $\mathcal{O}\left(n^{2}\right)$ time, which is also the best possible (up to subpolynomial factors) assuming the Strong Exponential Time Hypothesis (SETH). The last few decades have seen tremendous progress in edit distance approximation, where the runtime has been brought down to subquadratic, to near-linear, and even to sublinear at the cost of approximation. In this paper, we study the dynamic edit distance problem where the strings change dynamically as the characters are substituted, inserted, or deleted over time. Each change may happen at any location of either of the two strings. The goal is to maintain the (exact or approximate) edit distance of such dynamic strings while minimizing the update time. The exact edit distance can be maintained in $\mathcal{O}\left(n \log ^{2} n\right)$ time per update (Charalampopoulos, Kociumaka, Mozes; 2020), which is again tight assuming SETH. Unfortunately, even with the unprecedented progress in edit distance approximation in the static setting, strikingly little is known regarding dynamic edit distance approximation. Utilizing the best near-linear-time (Andoni, Nosatzki; 2020) and sublinear-time (Goldenberg, Kociumaka, Krauthgamer, Saha; 2022) approximation algorithm, an old exact algorithm (Landau and Vishkin; 1988), and a generic dynamic strings implementation (Mehlhorn, Sundar, Uhrig; 1996), it is possible to achieve an $\mathcal{O}\left(n^{c}\right)$-approximation in $n^{0. 5-c+o(1)}$ update time for any constant $c \in\left[0, \frac{1}{6}\right]$. Improving upon this trade-off, characterized by the approximation-ratio and update-time product $n^{0. 5+o(1)}$, remains wide open. The contribution of this work is a dynamic $n^{o(1)}$-approximation algorithm with amortized expected update time of $n^{o(1)}$. In other words, we bring the approximation-ratio and update-time product down to $n^{o(1)}$, which is also the best possible with the current state of the art in static algorithms. Our solution utilizes an elegant framework of precision sampling trees for edit distance approximation (Andoni, Krauthgamer, Onak; 2010). We show how to dynamically maintain precision sampling trees, which comes with significant nontriviality and can be an independent tool of interest for further development in dynamic string algorithms.

JMLR Journal 2023 Journal Article

Community Recovery in the Geometric Block Model

• Sainyam Galhotra
• Arya Mazumdar
• Soumyabrata Pal
• Barna Saha

To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The geometric block model builds on the random geometric graphs (Gilbert, 1961), one of the basic models of random graphs for spatial networks, in the same way that the well-studied stochastic block model builds on the Erdos-Renyi random graphs. It is also a natural extension of random community models inspired by the recent theoretical and practical advancements in community detection. To analyze the geometric block model, we first provide new connectivity results for random annulus graphs which are generalizations of random geometric graphs. The connectivity properties of geometric graphs have been studied since their introduction, and analyzing them has been more difficult than their Erdos-Renyi counterparts, due to correlated edge formation. We then use the connectivity results of random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities for the geometric block model. We show that a simple triangle-counting algorithm to detect communities in the geometric block model is near-optimal. For this, we consider the following two regimes of graph density. In the regime where the average degree of the graph grows logarithmically with the number of vertices, we show that our algorithm performs extremely well, both theoretically and practically. In contrast, the triangle-counting algorithm is far from being optimum for the stochastic block model in the logarithmic degree regime. We simulate our results on both real and synthetic datasets to show superior performance of both the new model as well as our algorithm. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

STOC Conference 2023 Conference Paper

Weighted Edit Distance Computation: Strings, Trees, and Dyck

• Debarati Das 0001
• Jacob Gilbert
• MohammadTaghi Hajiaghayi
• Tomasz Kociumaka
• Barna Saha

Given two strings of length n over alphabet Σ, and an upper bound k on their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance in O ( n + k 2 ) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ( n + poly ( k ))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.

SODA Conference 2022 Conference Paper

An Upper Bound and Linear-Space Queries on the LZ-End Parsing

• Dominik Kempa
• Barna Saha

Lempel–Ziv (LZ77) compression is the most commonly used lossless compression algorithm. The basic idea is to greedily break the input string into blocks (called “phrases”), every time forming as a phrase the longest prefix of the unprocessed part that has an earlier occurrence. In 2010, Kreft and Navarro introduced a variant of LZ77 called LZ-End, that additionally requires the previous occurrence of each phrase to end at the boundary of an already existing phrase. Due to its excellent practical performance as a compression algorithm and a compressed index, they conjectured that it achieves a compression that can be provably upper-bounded in terms of the LZ77 size. Despite the recent progress in understanding such relation for other compression algorithms (e. g. , the run-length encoded Burrows–Wheeler transform), no such result is known for LZ-End. We prove that for any string of length n, the number z e of phrases in the LZ-End parsing satisfies, where z is the number of phrases in the LZ77 parsing. This puts LZ-End among the strongest dictionary compressors and solves a decade-old open problem of Kreft and Navarro. Using our techniques we also derive bounds for other variants of LZ-End and with respect to other compression measures. Our second contribution is a data structure that implements random access queries to the text in space and time. This is the first linear-size structure on LZ-End that efficiently implements such queries. All previous data structures either incur a logarithmic penalty in the space or have slow queries. We also show how to extend these techniques to support longest-common-extension (LCE) queries.

FOCS Conference 2022 Conference Paper

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal

• Elazar Goldenberg
• Tomasz Kociumaka
• Robert Krauthgamer
• Barna Saha

We study the problem of approximating edit distance in sublinear time. This is formalized as the $(k, \ k^{\mathrm{c}})$-GAP EDIT DISTANCE problem, where the input is a pair of strings $X, \mathrm{Y}$ and parameters $k, c\gt 1$, and the goal is to return YES if ED(X, Y) $\leq k$, NO if ED(X, Y) $\gt k^{\mathrm{c}}$, and an arbitrary answer when $k\lt $ ED(X, Y) $\leq k^{\mathrm{c}}$. Recent years have witnessed significant interest in designing sublinear-time algorithms for GAP EDIT DISTANCE. In this work, we resolve the non-adaptive query complexity of GAP EDIT DISTANCE for the entire range of parameters, improving over a sequence of previous results. Specifically, we design a non-adaptive algorithm with query complexity $\tilde{O}(n/k^{\mathrm{c}-\mathrm{O}. 5})$, and we further prove that this bound is optimal up to polylogarithmic factors. Our algorithm also achieves optimal time complexity $\tilde{O}(n/k^{\mathrm{c}-\mathrm{O}. 5})$ whenever $ c\geq$ 1. 5. For $1 \lt c\lt $ 1. 5, the running time of our algorithm is $\tilde{O}(n/k^{2\mathrm{c}-2})$. In the restricted case of $k^{\mathrm{c}}=\Omega(n)$, this matches a known result [Batu, Ergün, Kilian, Magen, Raskhodnikova, Rubinfeld, and Sami; STOC 2003], and in all other (nontrivial) cases, our running time is strictly better than all previous algorithms, including the adaptive ones. However, independent work of Bringmann, Cassis, Fischer, and Nakos [STOC 2022] provides an adaptive algorithm that bypasses the non-adaptive lower bound, but only for small enough k and c.

SODA Conference 2022 Conference Paper

How Compression and Approximation Affect Efficiency in String Distance Measures

• Arun Ganesh
• Tomasz Kociumaka
• Andrea Lincoln
• Barna Saha

Real-world data often comes in compressed form. Analyzing compressed data directly (without first decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is highly compressible. We consider grammar compression, which unifies many practically relevant compression schemes such as the Lempel–Ziv family, dictionary methods, and others. For two strings of total length N and total compressed size n, it is known that the edit distance and a longest common subsequence (LCS) can be computed exactly in time Õ(nN ), as opposed to O(N 2 ) for the uncompressed setting. Many real-world applications need to align multiple sequences simultaneously, and the fastest known exact algorithms for median edit distance and LCS of k strings run in O ( N k ) time, whereas the one for center edit distance has a time complexity of O(N 2 k ). This naturally raises the question if compression can help to reduce the running time significantly for k ≥ 3, perhaps to O ( N k /2 n k /2 ) or, more optimistically, to O ( Nn k –1 ). 1 Unfortunately, we show new lower bounds that rule out any improvement beyond Ω ( N k –1 n ) time for any of these problems assuming the Strong Exponential Time Hypothesis (SETH), where again N and n represent the total length and the total compressed size, respectively. This answers an open question of Abboud, Backurs, Bringmann, and Künnemann (FOCS'17). In presence of such negative results, we ask if allowing approximation can help, and we show that approximation and compression together can be surprisingly effective for both multiple and two strings. We develop an Õ ( N k /2 n k /2 )-time FPTAS for the median edit distance of k sequences, leading to a saving of nearly half the dimensions for highly-compressible sequences. In comparison, no O ( N k – Ω (1) )-time PTAS is known for the median edit distance problem in the uncompressed setting. We obtain an improvement from for the center edit distance problem. For two strings, we get an -time FPTAS for both edit distance and LCS; note that this running time is o(N ) whenever n ≪ N 1/4. In contrast, for uncompressed strings, there is not even a subquadratic algorithm for LCS that has less than polynomial gap in the approximation factor. Building on the insight from our approximation algorithms, we also obtain several new and improved results for many fundamental distance measures including the edit, Hamming, and shift distances.

SODA Conference 2022 Conference Paper

The Complexity of Average-Case Dynamic Subgraph Counting

• Monika Henzinger
• Andrea Lincoln
• Barna Saha

Statistics of small subgraph counts such as triangles, four-cycles, and s-t paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most of these problems become hard in the dynamic setting when considering the worst case. In this paper, we ask whether the question of small subgraph counting over dynamic graphs is hard also in the average case. We consider the simplest possible average case model where the updates follow an Erdős-Rényi graph: each update selects a pair of vertices ( u, v ) uniformly at random and flips the existence of the edge ( u, v ). We develop new lower bounds and matching algorithms in this model for counting four-cycles, counting triangles through a specified point s, or a random queried point, and st paths of length 3, 4 and 5. Our results indicate while computing st paths of length 3, and 4 are easy in the average case with O (1) update time (note that they are hard in the worst case), it becomes hard when considering st paths of length 5. We introduce new techniques which allow us to get average-case hardness for these graph problems from the worst-case hardness of the Online Matrix vector problem (OMv). Our techniques rely on recent advances in fine-grained average-case complexity. Our techniques advance this literature, giving the ability to prove new lower bounds on average-case dynamic algorithms.

FOCS Conference 2022 Conference Paper

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

• Debarati Das 0001
• Jacob Gilbert
• MohammadTaghi Hajiaghayi
• Tomasz Kociumaka
• Barna Saha
• Hamed Saleh

Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of edit distance in which the task is to compute a measure of dissimilarity between two (unweighted) rooted trees with node labels. Perhaps the most notable recent application of tree edit distance is in NoSQL big databases, such as MongoDB, where each row of the database is a JSON document represented as a labeled rooted tree and finding dissimilarity between two rows is a basic operation. Until recently, the fastest algorithm for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann; TALG’10); however, Mao (FOCS’21) broke the cubic barrier for the tree edit distance problem using fast matrix multiplication. Given a parameter k as an upper bound on the distance, an $\mathcal{O}(n+k^{2})$-time algorithm for edit distance has been known since the 1980s due to works of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88). The existence of an $\tilde{\mathcal{O}}(n+poly(k))$-time algorithm for tree edit distance has been posed as open question, e. g. , by Akmal and Jin (ICALP’21), who give a stateof-the-art $O(nk^{2})$-time algorithm. In this paper, we answer this question positively.

MFCS Conference 2021 Conference Paper

Sublinear Algorithms for Edit Distance (Invited Talk)

• Barna Saha

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. A simple dynamic programming computes the edit distance between two strings of length n in O(n²) time, and a more sophisticated algorithm runs in time O(n+t²) where t is the distance (Landau, Myers and Schmidt, SICOMP 1998). In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time (Andoni, Krauthgamer and Onak, FOCS 2010), and a constant-factor approximation in subquadratic time (Chakrabarty, Das, Goldenberg, Koucký and Saks, FOCS 2018). In this talk, we will discuss recent progress that goes beyond linear time, and studies sublinear time algorithms for edit distance. We will also discuss the role preprocessing might play in designing fast algorithms. This is a joint work with Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Aviad Rubinstein.

STOC Conference 2020 Conference Paper

Does preprocessing help in fast sequence comparisons?

• Elazar Goldenberg
• Aviad Rubinstein
• Barna Saha

We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed strings. This model is inspired by scenarios where we would like to compute edit distance between many pairs in the same pool of strings.

FOCS Conference 2020 Conference Paper

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance

• Tomasz Kociumaka
• Barna Saha

In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we give a greedy algorithm that distinguishes in time $\tilde{\mathcal{O}}(\frac{n}{k}+k^{2})$ between length-n input strings with edit distance at most $k$ and those with edit distance more than $4k^{2}$. This is an improvement and a simplification upon the main result of [Goldenberg, Krauthgamer, Saha, FOCS 2019], where the $k$ vs $\Theta(k^{2})$ gap edit distance problem is solved in $\tilde{\mathcal{O}}(\frac{n}{k}+k^{3})$ time. We further generalize our result to solve the $k$ vs $\alpha k$ gap edit distance problem in time $\tilde{\mathcal{O}}(\frac{n}{\alpha}+k^{2}+\frac{k}{\alpha}\sqrt{nk})$, strictly improving upon the previously known bound $\tilde{\mathcal{O}}(\frac{n}{\alpha}+k^{3})$. Finally, we show that if the input strings do not have long highly periodic substrings, then the gap edit distance problem can be solved in sublinear time within any factor $\alpha > 1$. Specifically, if the strings contain no substring of length $\ell$ with the shortest period of length at most $2k$, then the $k$ vs $(1+\varepsilon)k$ gap edit distance problem can be solved in time $\tilde{\mathcal{O}}(\frac{n}{\varepsilon^{2}k}+k^{2}\ell)$. We further give the first sublinear-time algorithm for the probabilistic embedding of edit distance to Hamming distance. Our $\tilde{\mathcal{O}}(\frac{n}{p})$ -time procedure yields an embedding with distortion $k^{2}p$, where $k$ is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between $\frac{k-p+1}{p}$ and $k^{2}$ with good probability. This generalizes the linear-time embedding of [Chakraborty, Goldenberg, Koucký, STOC 2016], where the resultant Hamming distance is between $k$ and $k^{2}$. Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.

STOC Conference 2019 Conference Paper

Dynamic set cover: improved algorithms and lower bounds

• Amir Abboud
• Raghavendra Addanki
• Fabrizio Grandoni 0001
• Debmalya Panigrahi
• Barna Saha

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1+є) f -approximation for fully dynamic set cover in O ( f 2 log n /є 5 ) (amortized) update time, for any є > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O ( f 2 /є 5 ), while still obtaining an (1+є) f -approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O ( f 2 ) in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on f is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of O ( f 1−є ) must have an approximation factor that is Ω( n δ ) for some constant δ>0 under the Strong Exponential Time Hypothesis.

FOCS Conference 2019 Conference Paper

Sublinear Algorithms for Gap Edit Distance

• Elazar Goldenberg
• Robert Krauthgamer
• Barna Saha

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. A simple dynamic programming computes the edit distance between two strings of length n in O(n2) time, and a more sophisticated algorithm runs in time O(n + t2) when the edit distance is t [Landau, Myers and Schmidt, SICOMP 1998]. In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time [Andoni, Krauthgamer and Onak, FOCS 2010], and a constant-factor approximation in subquadratic time [Chakrabarty, Das, Goldenberg, Kouck´y and Saks, FOCS 2018]. We study sublinear-time algorithms for small edit distance, which was investigated extensively because of its numerous applications. Our main result is an algorithm for distinguishing whether the edit distance is at most t or at least t^2 (the quadratic gap problem) in time Õ(n/t+t^3). This time bound is sublinear roughly for all t in [ω(1), o(n^1/3)], which was not known before. The best previous algorithms solve this problem in sublinear time only for t=ω(n^1/3) [Andoni and Onak, STOC 2009]. Our algorithm is based on a new approach that adaptively switches between uniform sampling and reading contiguous blocks of the input strings. In contrast, all previous algorithms choose which coordinates to query non-adaptively. Moreover, it can be extended to solve the t vs t^2-ε gap problem in time Õ(n/t^1-ε+t^3).

AAAI Conference 2018 Conference Paper

The Geometric Block Model

• Sainyam Galhotra
• Arya Mazumdar
• Soumyabrata Pal
• Barna Saha

To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The geometric block model generalizes the random geometric graphs in the same way that the well-studied stochastic block model generalizes the Erdös-Renyi random graphs. It is also a natural extension of random community models inspired by the recent theoretical and practical advancement in community detection. While being a topic of fundamental theoretical interest, our main contribution is to show that many practical community structures are better explained by the geometric block model. We also show that a simple triangle-counting algorithm to detect communities in the geometric block model is near-optimal. Indeed, even in the regime where the average degree of the graph grows only logarithmically with the number of vertices (sparse-graph), we show that this algorithm performs extremely well, both theoretically and practically. In contrast, the triangle-counting algorithm is far from being optimum for the stochastic block model. We simulate our results on both real and synthetic datasets to show superior performance of both the new model as well as our algorithm.

AAAI Conference 2017 Conference Paper

A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution

• Arya Mazumdar
• Barna Saha

Entity resolution (ER) is the task of identifying all records in a database that refer to the same underlying entity, and are therefore duplicates of each other. Due to inherent ambiguity of data representation and poor data quality, ER is a challenging task for any automated process. As a remedy, human-powered ER via crowdsourcing has become popular in recent years. Using crowd to answer queries is costly and time consuming. Furthermore, crowd-answers can often be faulty. Therefore, crowd-based ER methods aim to minimize human participation without sacrificing the quality and use a computer generated similarity matrix actively. While, some of these methods perform well in practice, no theoretical analysis exists for them, and further their worst case performances do not reflect the experimental findings. This creates a disparity in the understanding of the popular heuristics for this problem. In this paper, we make the first attempt to close this gap. We provide a thorough analysis of the prominent heuristic algorithms for crowd-based ER. We justify experimental observations with our analysis and information theoretic lower bounds.

NeurIPS Conference 2017 Conference Paper

Clustering with Noisy Queries

• Arya Mazumdar
• Barna Saha

In this paper, we provide a rigorous theoretical study of clustering with noisy queries. Given a set of $n$ elements, our goal is to recover the true clustering by asking minimum number of pairwise queries to an oracle. Oracle can answer queries of the form ``do elements $u$ and $v$ belong to the same cluster? ''-the queries can be asked interactively (adaptive queries), or non-adaptively up-front, but its answer can be erroneous with probability $p$. In this paper, we provide the first information theoretic lower bound on the number of queries for clustering with noisy oracle in both situations. We design novel algorithms that closely match this query complexity lower bound, even when the number of clusters is unknown. Moreover, we design computationally efficient algorithms both for the adaptive and non-adaptive settings. The problem captures/generalizes multiple application scenarios. It is directly motivated by the growing body of work that use crowdsourcing for {\em entity resolution}, a fundamental and challenging data mining task aimed to identify all records in a database referring to the same entity. Here crowd represents the noisy oracle, and the number of queries directly relates to the cost of crowdsourcing. Another application comes from the problem of sign edge prediction in social network, where social interactions can be both positive and negative, and one must identify the sign of all pair-wise interactions by querying a few pairs. Furthermore, clustering with noisy oracle is intimately connected to correlation clustering, leading to improvement therein. Finally, it introduces a new direction of study in the popular stochastic block model where one has an incomplete stochastic block model matrix to recover the clusters.

FOCS Conference 2017 Conference Paper

Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach

• Barna Saha

Dynamic programming is a basic, and one of the most systematic techniques for developing polynomial time algorithms with overwhelming applications. However, it often suffers from having high running time and space complexity due to (a) maintaining a table of solutions for a large number of sub-instances, and (b) combining/comparing these solutions to successively solve larger sub-instances. In this paper, we consider a canonical cubic time and quadratic space dynamic programming, and show how improvements in both its time and space uses are possible. As a result, we obtain fast small-space approximation algorithms for the fundamental problems of context free grammar recognition (the basic computer science problem of parsing), the language edit distance (a significant generalization of string edit distance and parsing), and RNA folding (a classical problem in bioinformatics). For these problems, ours are the first algorithms that break the cubic-time barrier of any combinatorial algorithm, and quadratic-space barrier of “any” algorithm significantly improving upon their long-standing space and time complexities. Our technique applies to many other problems as well including string edit distance computation, and finding longest increasing subsequence. Our improvements come from directly grinding the dynamic programming and looking through the lens of language edit distance which generalizes both context free grammar recognition, and RNA folding. From known conditional lower bound results, neither of these problems can have an exact combinatorial algorithm (one that does not use fast matrix multiplication) running in truly subcubic time. Moreover, for language edit distance such an algorithm cannot exist even when nontrivial multiplicative approximation is allowed. We overcome this hurdle by designing an additive-approximation algorithm that for any parameter k > 0, uses O(nk log n) space and O(n 2 k log n) time and provides an additive O(nk log n)approximation. In particular, in Õ(n) 1 space and Õ(n 2 ) time it can solve deterministically whether a string belongs to a context free grammar, or ϵ-far from it for any constant ϵ > 0. We also improve the above results to obtain an algorithm that outputs an ϵ · n-additive approximation to the above problems with space complexity O(n2/3 log n). The space complexity remains sublinear in n, as long as ϵ = o(n -1 / 4 ). Moreover, we provide the first MapReduce and streaming algorithms for them with multiple passes and sublinear space complexity.

NeurIPS Conference 2017 Conference Paper

Query Complexity of Clustering with Side Information

• Arya Mazumdar
• Barna Saha

Suppose, we are given a set of $n$ elements to be clustered into $k$ (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, ``do two elements $u$ and $v$ belong to the same cluster? ''. The goal is to recover the optimum clustering by asking the minimum number of queries. In this paper, we provide a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and give strong information theoretic lower bounds, as well as nearly matching upper bounds. Most clustering problems come with a similarity matrix, which is used by an automated process to cluster similar points together. To improve accuracy of clustering, a fruitful approach in recent years has been to ask a domain expert or crowd to obtain labeled data interactively. Many heuristics have been proposed, and all of these use a similarity function to come up with a querying strategy. Even so, there is a lack systematic theoretical study. Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering. A similarity matrix represents noisy pair-wise relationships such as one computed by some function on attributes of the elements. A natural noisy model is where similarity values are drawn independently from some arbitrary probability distribution $f_+$ when the underlying pair of elements belong to the same cluster, and from some $f_-$ otherwise. We show that given such a similarity matrix, the query complexity reduces drastically from $\Theta(nk)$ (no similarity matrix) to $O(\frac{k^2\log{n}}{\cH^2(f_+\|f_-)})$ where $\cH^2$ denotes the squared Hellinger divergence. Moreover, this is also information-theoretic optimal within an $O(\log{n})$ factor. Our algorithms are all efficient, and parameter free, i. e. , they work without any knowledge of $k, f_+$ and $f_-$, and only depend logarithmically with $n$.

FOCS Conference 2016 Conference Paper

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product

• Karl Bringmann
• Fabrizio Grandoni 0001
• Barna Saha
• Virginia Vassilevska Williams

It is a major open problem whether the (min, +)-product of two n by n matrices has a truly sub-cubic time algorithm, as it is equivalent to the famous All-Pairs-Shortest-Paths problem (APSP) in n-vertex graphs. There are some restrictions of the (min, +)-product to special types of matrices that admit truly sub-cubic algorithms, each giving rise to a special case of APSP that can be solved faster. In this paper we consider a new, different and powerful restriction in which one matrix can be arbitrary, as long as the other matrix has "bounded differences" in either its columns or rows, i. e. any two consecutive entries differ by only a small amount. We obtain the first truly sub-cubic algorithm for this Bounded Differences (min, +)-product (answering an open problem of Chan and Lewenstein). Our new algorithm, combined with a strengthening of an approach of L. Valiant for solving context-free grammar parsing with matrix multiplication, yields the first truly sub-cubic algorithms for the following problems: Language Edit Distance (a major problem in the parsing community), RNA-folding (a major problem in bioinformatics) and Optimum Stack Generation (answering an open problem of Tarjan).

FOCS Conference 2015 Conference Paper

Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems

• Barna Saha

Given a context free language G over alphabet Σ and a string s ∈ Σ*, the language edit distance problem seeks the minimum number of edits (insertions, deletions and substitutions) required to convert s into a valid member of the language £(G). The well-known dynamic programming algorithm solves this problem in O(n 3 ) time (ignoring grammar size) where n is the string length [Aho, Peterson 1972, Myers 1985]. Despite its numerous applications, to date there exists no algorithm that computes the exact or approximate language edit distance problem in true subcubic time. In this paper we give the first such algorithm that computes language edit distance almost optimally. For any arbitrary ε > 0, our algorithm runs in Õ(nω/poly(∈)) time and returns an estimate within a multiplicative approximation factor of (1 + ∈) with high probability, where w is the exponent of ordinary matrix multiplication of n dimensional square matrices. It also computes the actual edits required. We further solve the local alignment problem; for all substrings of s, we can estimate their language edit distance within (1 ± ε) factor in Õ(n ω /poly(∈)) time with high probability. Next, we design the very first subcubic (Õ(n ω )) algorithm that given an arbitrary stochastic context free grammar, and a string returns a nearly-optimal maximum likelihood parsing of that string. Stochastic context free grammars significantly generalize hidden Markov models; they lie at the foundation of statistical natural language processing, and have found widespread applications in many other fields. To complement our upper bound result, we show that exact computation of maximum likelihood parsing of stochastic grammars or language edit distance in true subcubic time will imply a truly subcubic algorithm for all-pairs shortest paths, a long-standing open question. This will result in a breakthrough for a large range of problems in graphs and matrices due to subcubic equivalence. By a known lower bound result [Lee 2002], and a recent development [Abboud et al. 2015] even the much simpler problem of parsing a context free grammar requires Ω(n ω ) time. Therefore any nontrivial multiplicative approximation algorithms for either of the two problems in time o(n ω ) are unlikely to exist.

SODA Conference 2014 Conference Paper

A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median

• MohammadTaghi Hajiaghayi
• Wei Hu
• Jian Li 0015
• Shi Li 0001
• Barna Saha

In this paper, we consider the fault-tolerant k -median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of classical k -median problem, each client j needs to be assigned to at least r j ≥ 1 distinct open facilities. The service cost of j is the sum of its distances to the r j facilities, and the k -median constraint restricts the number of open facilities to at most k. Previously, a constant factor was known only for the special case when all r j s are the same, and a logarithmic approximation ratio was known for the general case. In addition, we present the first polynomial time algorithm for the fault-tolerant k -median problem on a path or a HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, where the service cost of j can be a weighted sum of its distance to the r j facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.

FOCS Conference 2014 Conference Paper

The Dyck Language Edit Distance Problem in Near-Linear Time

• Barna Saha

Given a string σ over alphabet Σ and a grammar G defined over the same alphabet, how many minimum number of repairs (insertions, deletions and substitutions) are required to map σ into a valid member of G? The seminal work of Aho and Peterson in 1972 initiated the study of this language edit distance problem providing a dynamic programming algorithm for context free languages that runs in O(|G| 2 n 3 ) time, where n is the string length and G is the grammar size. While later improvements reduced the running time to O(G n 3 ), the cubic time complexity on the input length held a major bottleneck for applying these algorithms to their multitude of applications. In this paper, we study the language edit distance problem for a fundamental context free language, DYCK(s) representing the language of well-balanced parentheses of s different types, that has been pivotal in the development of formal language theory. We provide the very first near-linear time algorithm to tightly approximate the DYCK(s) language edit distance problem for any arbitrary s. DYCK(s) language edit distance significantly generalizes the well-studied string edit distance problem, and appears in most applications of language edit distance ranging from data quality in databases, generating automated error-correcting parsers in compiler optimization to structure prediction problems in biological sequences. Its nondeterministic counterpart is known as the hardest context free language. Our main result is an algorithm for edit distance computation to DYCK(s) for any positive integer s that runs in O(n 1+ϵ polylog(n)) time and achieves an approximation factor of O(1/ϵβ(n) log |OPT|), for any ϵ > 0. Here OPT is the optimal edit distance to DYCK(s) and β(n) is the best approximation factor known for the simpler problem of string edit distance running in analogous time. If we allow O(n 1+ϵ + |OPT| 2 n ϵ ) time, then the approximation factor can be reduced to O(1/ϵ log |OPT|). Since the best known near-linear time algorithm for the string edit distance problem has β(n) = polylog(n), under near-linear time computation model both DYCK(s) language and string edit distance problems have polylog(n) approximation factors. This comes as a surprise since the former is a significant generalization of the latter and their exact computations via dynamic programming show a stark difference in time complexity. Rather less surprisingly, we show that the framework for efficiently approximating edit distance to DYCK(s) can be utilized for many other languages. We illustrate this by considering various memory checking languages (studied extensively under distributed verification) such as STACK, QUEUE, PQ and DEQUE which comprise of valid transcripts of stacks, queues, priority queues and double-ended queues respectively. Therefore, any language that can be recognized by these data structures, can also be repaired efficiently by our algorithm.

SODA Conference 2011 Conference Paper

The Matroid Median Problem

• Ravishankar Krishnaswamy
• Amit Kumar 0001
• Viswanath Nagarajan
• Yogish Sabharwal
• Barna Saha

In the classical k -median problem, we are given a metric space and would like to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper, we consider the following generalization of the problem: instead of opening at most k centers, what if each center belongs to one of T different types, and we are allowed to open at most k i centers of type i (for each i = 1, 2, …, T ). The case T = 1 is the classical k -median, and the case of T = 2 is the red-blue median problem for which Hajiaghayi et al. [ESA 2010] recently gave a constant-factor approximation algorithm. Even more generally, what if the set of open centers had to form an independent set from a matroid? In this paper, we give a constant factor approximation algorithm for such matroid median problems. Our algorithm is based on rounding a natural LP relaxation in two stages: in the first step, we sparsify the structure of the fractional solution while increasing the objective function value by only a constant factor. This enables us to write another LP in the second phase, for which the sparsified LP solution is feasible. We then show that this second phase LP is in fact integral; the integrality proof is based on a connection to matroid intersection. We also consider the penalty version (alternately, the so-called prize collecting version) of the matroid median problem and obtain a constant factor approximation algorithm for it. Finally, we look at the Knapsack Median problem (in which the facilities have costs and the set of open facilities need to fit into a Knapsack) and get a bicriteria approximation algorithm which violates the Knapsack bound by a small additive amount.

SODA Conference 2010 Conference Paper

Energy Efficient Scheduling via Partial Shutdown

• Samir Khuller
• Jian Li 0015
• Barna Saha

Motivated by issues of saving energy in data centers we define a collection of new problems referred to as “machine activation” problems. The central framework we introduce considers a collection of m machines (unrelated or related) with each machine i having an activation cost of a i. There is also a collection of n jobs that need to be performed, and p i, j is the processing time of job j on machine i. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of A – we would like to select a subset S of the machines to activate with total cost a ( S ) ≤ A and find a schedule for the n jobs on the machines in S minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine i has activation cost a i and speed s i, and the processing time of job j on machine i is, where p j is the processing requirement of job j. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan T and activation cost A then we can obtain a schedule with makespan (2 + ε) T and activation cost, for any ε > 0. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. In addition, we present a greedy algorithm which only works for the basic version and yields a makespan of 2 T and an activation cost A (1 + ln n ). For the uniformly related parallel machine scheduling problem, we develop a polynomial time approximation scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most A and the makespan is at most (1 + ε) T for any ε > 0. For the special case of m identical speed machines, the machine activation problem is trivial, since the cheapest subset of k machines is always the best choice if the optimal solution activates k machines. In addition, we consider the case when some jobs can be dropped (and are treated as outliers).

FOCS Conference 2010 Conference Paper

New Constructive Aspects of the Lovasz Local Lemma

• Bernhard Haeupler
• Barna Saha
• Aravind Srinivasan

The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of "bad" events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the conditional LLL-distribution - the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized "core" subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX k-SAT is an example of this.