Tsvi Kopelowitz

SODA Conference 2022 Conference Paper

An Improved Algorithm for The k-Dyck Edit Distance Problem

• Dvir Fried
• Shay Golan 0001
• Tomasz Kociumaka
• Tsvi Kopelowitz
• Ely Porat
• Tatiana Starikovskaya

A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses S is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform S into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses S and a positive integer k, and the goal is to compute the Dyck edit distance of S only if the distance is at most k, and otherwise report that the distance is larger than k. Backurs and Onak [PODS'16] showed that the threshold Dyck edit distance problem can be solved in O(n + k 16 ) time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs O ( n + k 4. 782036 ) time with high probability or O ( n + k 4. 853059 ) deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast (min, +) matrix product, and a careful modification of ideas used in Valiant's parsing algorithm.

STOC Conference 2020 Conference Paper

Approximating text-to-pattern Hamming distances

• Timothy M. Chan
• Shay Golan 0001
• Tomasz Kociumaka
• Tsvi Kopelowitz
• Ely Porat

We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n , both over an alphabet of size σ, compute the Hamming distance (i.e., the number of mismatches) between the pattern and the text at every location. Several randomized (1+ε)-approximation algorithms have been proposed in the literature (e.g., by Karloff (Inf. Proc. Lett., 1993), Indyk (FOCS 1998), and Kopelowitz and Porat (SOSA 2018)), with running time of the form O (ε − O (1) n log n log m ), all using fast Fourier transform (FFT). We describe a simple randomized (1+ε)-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results (all Monte-Carlo randomized) in different settings:

STOC Conference 2020 Conference Paper

Contention resolution without collision detection

• Michael A. Bender
• Tsvi Kopelowitz
• William Kuszmaul
• Seth Pettie

This paper focuses on the contention resolution problem on a shared communication channel that does not support collision detection. A shared communication channel is a multiple access channel, which consists of a sequence of synchronized time slots. Players on the channel may attempt to broadcast a packet (message) in any time slot. A player's broadcast succeeds if no other player broadcasts during that slot. If two or more players broadcast in the same time slot, then the broadcasts collide and both broadcasts fail. The lack of collision detection means that a player monitoring the channel cannot differentiate between the case of two or more players broadcasting in the same slot (a collision) and zero players broadcasting. In the contention-resolution problem, players arrive on the channel over time, and each player has one packet to transmit. The goal is to coordinate the players so that each player is able to successfully transmit its packet within reasonable time. However, the players can only communicate via the shared channel by choosing to either broadcast or not. A contention-resolution protocol is measured in terms of its throughput (channel utilization). Previous work on contention resolution that achieved constant throughput assumed that either players could detect collisions, or the players' arrival pattern is generated by a memoryless (non-adversarial) process.

STOC Conference 2017 Conference Paper

Exponential separations in the energy complexity of leader election

• Yi-Jun Chang
• Tsvi Kopelowitz
• Seth Pettie
• Ruosong Wang
• Wei Zhan

Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), not on computation. In this paper we study the energy complexity of Leader Election and Approximate Counting in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions . We consider four collision-detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD and Receiver-CD (in which only transmitters or only listeners detect collisions), and No-CD (in which no one detects collisions.)

SODA Conference 2017 Conference Paper

File Maintenance: When in Doubt, Change the Layout!

• Michael A. Bender
• Jeremy T. Fineman
• Seth Gilbert
• Tsvi Kopelowitz
• Pablo Montes

This paper gives a new deamortized solution to the sequential-file-maintenance problem. The data structure uses several new tools for solving this historically complicated problem. These tools include an unbalanced ternary-tree layout embedded in the sparse table, one-way rebalancing, and extra structural properties to keep interaction among rebalances to a minimum.

SODA Conference 2017 Conference Paper

Fully Dynamic Connectivity in O (log n (log log n ) 2 ) Amortized Expected Time

• Shang-En Huang
• Dawei Huang
• Tsvi Kopelowitz
• Seth Pettie

Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O (log n (log log n ) 2 ) amortized expected update time and O (log n / log log log n ) query time, which comes within an O (log log n ) 2 ) factor of a lower bound due to Patrascu and Demaine. The new structure is based on a dynamic connectivity algorithm proposed by Thorup in an extended abstract at STOC 2000, which left out some important details.

FOCS Conference 2016 Conference Paper

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

• Yi-Jun Chang
• Tsvi Kopelowitz
• Seth Pettie

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. We prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message: 1) Building on the recent randomized lower bounds of Brandt et al. [1], we prove that the randomized complexity of Δ-coloring a tree with maximum degree Δ is O(log Δ log n + log*n), for any Δ > = 55, whereas its deterministic complexity is Ω(log Δ n) for any Δ > = 3. This also establishes a large separation between the deterministic complexity of Δ-coloring and (Δ+1)-coloring trees. 2) We prove that any deterministic algorithm for a natural class of problems that runs in O(1) + o(log Δ n) rounds can be transformed to run in O(log*n - log*Δ + 1) rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires Ω(log Δ n) time deterministically. This gives an alternate proof that deterministically Δ-coloring a tree with small Δ takes Ω(log Δ n) rounds. 3) We prove that the randomized complexity of any natural problem on instances of size n is at least its deterministic complexity on instances of size √log n. This shows that a deterministic Ω(log Δ n) lower bound for any problem (Δ-coloring a tree, for example) implies a randomized Ω(log Δ log n) lower bound. It also illustrates that the graph shattering technique employed in recent randomized symmetry breaking algorithms is absolutely essential to the LOCAL model. For example, it is provably impossible to improve the 2O(√log log n) term in the complexities of the best MIS and (Δ+1)-coloring algorithms without also improving the 2O(√log n)-round Panconesi-Srinivasan algorithm.

STOC Conference 2016 Conference Paper

Contention resolution with log-logstar channel accesses

• Michael A. Bender
• Tsvi Kopelowitz
• Seth Pettie
• Maxwell Young

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Surprisingly, despite this history, the performance of standard backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of N devices requires Omega(log N) access attempts before obtaining the resource.

SODA Conference 2016 Conference Paper

Higher Lower Bounds from the 3SUM Conjecture

• Tsvi Kopelowitz
• Seth Pettie
• Ely Porat

The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pâtraşcu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by Pâtraşcu suffers from several inefficiencies, making it difficult to obtain tight conditional lower bounds from the 3SUM conjecture. In this paper we address many of the deficiencies of Pâtraşcu's framework. We give new and efficient reductions from 3SUM to offline SetDisjointness and offline SetIntersection (the reporting version of SetDisjointness) which leads to polynomially higher lower bounds on several problems. Using our reductions, we are able to show the essential optimality of several algorithms, assuming the 3SUM conjecture. Chiba and Nishizeki's O ( mα )-time algorithm (SICOMP 1985) for enumerating all triangles in a graph with arboricity/degeneracy α is essentially optimal, for any α. Bjørklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014) for listing t triangles is essentially optimal (assuming the matrix multiplication exponent is ω = 2). Any static data structure for SetDisjointness that answers queries in constant time must spend Ω( N 2– o (1) ) time in preprocessing, where N is the size of the set system. These statements were unattainable via Pâtraşcu's reductions. We also introduce several new reductions from 3SUM to pattern matching problems and dynamic graph problems. Of particular interest are new conditional lower bounds for dynamic versions of Maximum Cardinality Matching, which introduce a new technique for obtaining amortized lower bounds.

TCS Journal 2016 Journal Article

The property suffix tree with dynamic properties

• Tsvi Kopelowitz

In the Property Indexing Problem the goal is to preprocess a text T of size n over a constant sized alphabet Σ and a set of intervals π over the text positions, such that given a query pattern P of size m we can report all of the occurrences of P in T which are completely contained within some interval from π. This type of matching is extremely helpful for scenarios in molecular biology where it has long been a practice to consider special areas in the genome by their structure. It is also helpful for solving pattern matching problems over weighted sequences. So far the focus has been on the static version of this problem where the intervals are given a priori and never changed. This paper focuses on several dynamic settings of π including an incremental version where new intervals are inserted into π, a decremental version where intervals are deleted from π, a fully dynamic version where intervals may be inserted into or deleted from π, and a batched insertions version where sets of intervals are inserted into π. In particular, the batched version provides a new (optimal) algorithm for the static case.

FOCS Conference 2015 Conference Paper

Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment

• Tsvi Kopelowitz
• Ely Porat

The algorithmic tasks of computing the Hamming distance between a given pattern of length m and each location in a text of length n is one of the most fundamental algorithmic tasks in string algorithms. Unfortunately, there is evidence that for a text T of sizen and a pattern P of size m, one cannot compute the exact Hamming distance for all locations in T in time which is less than O(n√m). However, Karloff [30] showed that if one is willing to suffer a 1 ± € approximation, then it is possible to solve the problem with high probability, in O(2/n) time. Due to related lower bounds for computing the Hamming distance of two strings in the one-way communication complexity model, it is strongly believed that obtaining an algorithm for solving the approximation version cannot be done much faster as a function of 1/ε. We show here that this belief is false by introducing a new O(n/ε ) time algorithm that succeeds with high probability. The main idea behind our algorithm, which is common in sparse recovery problems, is to reduce the variance of a specific randomized experiment by (approximately) separating heavy hitters from non-heavy hitters. However, while known sparse recovery techniques work very well on vectors, they do not seem to apply here, where we are dealing with mismatches between pairs of characters. We introduce two main algorithmic ingredients. The first is a new sparse recovery method that applies for pair inputs (such as in our setting). The second is a new construction of hash/projection functions, for which have which allows us to count the number of projections that induce mismatches between two characters exponentially faster than brute force. We expect that these algorithmic techniques will be of independent interest.

TCS Journal 2014 Journal Article

Generalized substring compression

• Orgad Keller
• Tsvi Kopelowitz
• Shir Landau Feibish
• Moshe Lewenstein

In substring compression one is given a text to preprocess so that, upon request, a compressed substring is returned. Generalized substring compression is the same with the following twist. The queries contain an additional context substring (or a collection of context substrings) and the answers are the substring in compressed format, where the context substring is used to make the compression more efficient. We focus our attention on generalized substring compression and present the first non-trivial correct algorithm for this problem. Inherent to our algorithm is a new method for finding the bounded longest common prefix of substrings, which may be of independent interest. In addition, we propose an efficient algorithm for substring compression which makes use of range successor queries. We present several tradeoffs for both problems. For compressing the substring S [ i. . j ] (possibly with the substring S [ α. . β ] as a context), the best query times we achieve are O ( C ) and O ( C log ( j − i C ) ) for substring compression query and generalized substring compression query, respectively, where C is the number of phrases encoded. A preliminary version of this paper has been presented in [21].

FOCS Conference 2012 Conference Paper

On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List

• Tsvi Kopelowitz

The problem of Text Indexing is a fundamental algorithmic problem in which one wishes to preprocess a text in order to quickly locate pattern queries within the text. In the ever evolving world of dynamic and on-line data, there is also a need for developing solutions to index texts which arrive online, i. e. a character at a time, and still be able to quickly locate said patterns. In this paper, a new solution for on-line indexing is presented by providing an on-line suffix tree construction in O(log log n + log log |Σ|) worst-case expected time per character, where n is the size of the string, and Σ is the alphabet. This improves upon all previously known on-line suffix tree constructions for general alphabets, at the cost of having the run time in expectation. The main idea is to reduce the problem of constructing a suffix tree on-line to an interesting variant of the order maintenance problem, which may be of independent interest. In the famous order maintenance problem, one wishes to maintain a dynamic list L of size n under insertions, deletions, and order queries. In an order query, one is given two nodes from L and must determine which node precedes the other in L. In an extension to this problem, named the Predecessor search on Dynamic Subsets of an Ordered Dynamic List problem (POLP for short), it is also necessary to maintain dynamic subsets S 1, · · ·, S k ⊆ L, such that given some u ∈ L it will be possible to quickly locate the predecessor of u in Si, for any integer 1 ≤ i ≤ k. This paper provides an efficient data structure capable of locating the predecessor of u in Si in O(log log n) worst-case time and answering order queries on L in O(1) worst-case time, while allowing updates to L in O(1) worst-case expected time and updates to the subsets in O(log log n) worst-case expected time. This improves over a previous data structure which may be implicitly obtained from Dietz [8], in which the updates to the sets and L are done in O(log log n) amortized expected time. In addition, the bounds shown here match the currently best known bounds for predecessor search in the RAM model. Furthermore, this paper improves or simplifies bounds for several additional applications, including fully-persistent arrays, the monotonic list labeling problem, and the Order-Maintenance Problem.

SODA Conference 2011 Conference Paper

Fast, precise and dynamic distance queries

• Yair Bartal
• Lee-Ad Gottlieb
• Tsvi Kopelowitz
• Moshe Lewenstein
• Liam Roditty

We present an approximate distance oracle for a point set S with n points and doubling dimension Λ. For every ε > 0, the oracle supports (1 + ε)-approximate distance queries in (universal) constant time, occupies space [ε − O (Λ) + 2 O (Λ log Λ) ] n, and can be constructed in [2 O (Λ) log 3 n + ε − O (Λ) + 2 O (Λ log Λ) ] n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel [13]. Furthermore, the oracle can be made fully dynamic with expected O (1) query time and only 2 O (Λ) log n + ε − O (Λ) + 2 O (Λ log Λ) update time. This is the first fully dynamic (1 + ε)-distance oracle.

TCS Journal 2009 Journal Article

On the longest common parameterized subsequence

• Orgad Keller
• Tsvi Kopelowitz
• Moshe Lewenstein

The well-known problem of the longest common subsequence (LCS), of two strings of lengths n and m respectively, is O ( n m ) -time solvable and is a classical distance measure for strings. Another well-studied string comparison measure is that of parameterized matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets such that one string matches the other under the bijection. All works associated with parameterized pattern matching present polynomial time algorithms. There have been several attempts to accommodate parameterized matching along with other distance measures, as these turn out to be natural problems, e. g. , Hamming distance, and a bounded version of edit-distance. Several algorithms have been proposed for these problems. In this paper we consider the longest common parameterized subsequence problem which combines the LCS measure with parameterized matching. We prove that the problem is NP -hard, and then show a couple of approximation algorithms for the problem.

TCS Journal 2008 Journal Article

Property matching and weighted matching

• Amihood Amir
• Eran Chencinski
• Costas Iliopoulos
• Tsvi Kopelowitz
• Hui Zhang

In many pattern matching applications the text has some properties attached to its various parts. Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property. Some immediate examples come from molecular biology where it has long been a practice to consider special areas in the genome by their structures. It is straightforward to do sequential matching in a text with properties. However, indexing in a text with properties becomes difficult if we desire the time to be output dependent. We present an algorithm for indexing a text with properties in O ( n log | Σ | + n log log n ) time for preprocessing and O ( | P | log | Σ | + tocc π ) per query, where n is the length of the text, P is the sought pattern, Σ is the alphabet, and tocc π is the number of occurrences of the pattern that satisfy some property π. As a practical use of Property Matching we show how to solve Weighted Matching problems using techniques from Property Matching. Weighted sequences have recently been introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is a “statistical image” of this set, where we are given the probability of every symbol’s occurrence at every text location. Weighted matching problems are pattern matching problems where the given text is weighted. We present a reduction from Weighted Matching to Property Matching that allows off-the-shelf solutions to numerous weighted matching problems including indexing, swapped matching, parameterized matching, approximate matching, and many more. Assuming that one seeks the occurrence of pattern P with probability ϵ in weighted text T of length n, we reduce the problem to a property matching problem of pattern P in text T ′ of length O ( n ( 1 ϵ ) 2 log 1 ϵ ).

SODA Conference 2007 Conference Paper

Dynamic weighted ancestors

• Tsvi Kopelowitz
• Moshe Lewenstein