Tsvi Kopelowitz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Tsvi Kopelowitz has a total of 40 co-authors. Here are the top co-authors by number of shared publications:
- Ely Porat
Bar-Ilan University
11 shared publications - Seth Pettie
University of Michigan, Ann Arbor, USA
5 shared publications - Shay Golan
Department of Computer Science, University of Haifa , Haifa 3498838
5 shared publications - Tomasz Kociumaka
Saarland Informatics Campus, Max Planck Institute for Informatics, Saarbrücken, Germany
3 shared publications Ely Porat
Bar-Ilan University
2 shared publicationsIsaac Goldstein
Bar-Ilan University
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 823-834
Contention Resolution, with and without a Global Clock
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 823-834
Open AccessContention Resolution, with and without a Global Clock
- Open Access
- 21 June 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (3) , 1-25
An Improved Algorithm for The k -Dyck Edit Distance Problem
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.544184 ) 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.
- 21 June 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (3) , 1-25
Open AccessAn Improved Algorithm for The k -Dyck Edit Distance Problem
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.544184 ) 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.
- Open AccessAn $O(\log^{3/2}n)$ Parallel Time Population Protocol for Majority with $O(\log n)$ StatesIn population protocols, the underlying distributed network consists of $n$ nodes (or agents), denoted by $V$, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by $n$. In this paper we consider the majority problem, where each node receives as input a color that is either black or white, and the goal is to have all of the nodes output the color that is the majority of the input colors. We design a population protocol that solves the majority problem in $O(\log^{3/2}n)$ parallel time, both with high probability and in expectation, while using $O(\log n)$ states. Our protocol improves on a recent protocol of Berenbrink et al. that runs in $O(\log^{5/3}n)$ parallel time, both with high probability and in expectation, using $O(\log n)$ states.Open AccessAn $O(\log^{3/2}n)$ Parallel Time Population Protocol for Majority with $O(\log n)$ StatesIn population protocols, the underlying distributed network consists of $n$ nodes (or agents), denoted by $V$, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by $n$. In this paper we consider the majority problem, where each node receives as input a color that is either black or white, and the goal is to have all of the nodes output the color that is the majority of the input colors. We design a population protocol that solves the majority problem in $O(\log^{3/2}n)$ parallel time, both with high probability and in expectation, while using $O(\log n)$ states. Our protocol improves on a recent protocol of Berenbrink et al. that runs in $O(\log^{5/3}n)$ parallel time, both with high probability and in expectation, using $O(\log n)$ states.
- Open Access
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
We revisit the $k$-mismatch problem in the streaming model on a pattern of length $m$ and a streaming text of length $n$, both over a size-$\sigma$ alphabet. The current state-of-the-art algorithm for the streaming $k$-mismatch problem, by Clifford et al. [SODA 2019], uses $\tilde O(k)$ space and $\tilde O\big(\sqrt k\big)$ worst-case time per character. The space complexity is known to be (unconditionally) optimal, and the worst-case time per character matches a conditional lower bound. However, there is a gap between the total time cost of the algorithm, which is $\tilde O(n\sqrt k)$, and the fastest known offline algorithm, which costs $\tilde O\big(n + \min\big(\frac{nk}{\sqrt m},\sigma n\big)\big)$ time. Moreover, it is not known whether improvements over the $\tilde O(n\sqrt k)$ total time are possible when using more than $O(k)$ space. We address these gaps by designing a randomized streaming algorithm for the $k$-mismatch problem that, given an integer parameter $k\le s \le m$, uses $\tilde O(s)$ space and costs $\tilde O\big(n+\min\big(\frac {nk^2}m,\frac{nk}{\sqrt s},\frac{\sigma nm}s\big)\big)$ total time. For $s=m$, the total runtime becomes $\tilde O\big(n + \min\big(\frac{nk}{\sqrt m},\sigma n\big)\big)$, which matches the time cost of the fastest offline algorithm. Moreover, the worst-case time cost per character is still $\tilde O\big(\sqrt k\big)$.Open AccessThe Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
We revisit the $k$-mismatch problem in the streaming model on a pattern of length $m$ and a streaming text of length $n$, both over a size-$\sigma$ alphabet. The current state-of-the-art algorithm for the streaming $k$-mismatch problem, by Clifford et al. [SODA 2019], uses $\tilde O(k)$ space and $\tilde O\big(\sqrt k\big)$ worst-case time per character. The space complexity is known to be (unconditionally) optimal, and the worst-case time per character matches a conditional lower bound. However, there is a gap between the total time cost of the algorithm, which is $\tilde O(n\sqrt k)$, and the fastest known offline algorithm, which costs $\tilde O\big(n + \min\big(\frac{nk}{\sqrt m},\sigma n\big)\big)$ time. Moreover, it is not known whether improvements over the $\tilde O(n\sqrt k)$ total time are possible when using more than $O(k)$ space. We address these gaps by designing a randomized streaming algorithm for the $k$-mismatch problem that, given an integer parameter $k\le s \le m$, uses $\tilde O(s)$ space and costs $\tilde O\big(n+\min\big(\frac {nk^2}m,\frac{nk}{\sqrt s},\frac{\sigma nm}s\big)\big)$ total time. For $s=m$, the total runtime becomes $\tilde O\big(n + \min\big(\frac{nk}{\sqrt m},\sigma n\big)\big)$, which matches the time cost of the fastest offline algorithm. Moreover, the worst-case time cost per character is still $\tilde O\big(\sqrt k\big)$. - Open Access
Approximating Text-to-Pattern Hamming Distances
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 $\sigma$, compute the Hamming distance between the pattern and the text at every location. Several $(1+\epsilon)$-approximation algorithms have been proposed in the literature, with running time of the form $O(\epsilon^{-O(1)}n\log n\log m)$, all using fast Fourier transform (FFT). We describe a simple $(1+\epsilon)$-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results: - We obtain the first linear-time approximation algorithm; the running time is $O(\epsilon^{-2}n)$. - We obtain a faster exact algorithm computing all Hamming distances up to a given threshold k; its running time improves previous results by logarithmic factors and is linear if $k\le\sqrt m$. - We obtain approximation algorithms with better $\epsilon$-dependence using rectangular matrix multiplication. The time-bound is $\~O(n)$ when the pattern is sufficiently long: $m\ge \epsilon^{-28}$. Previous algorithms require $\~O(\epsilon^{-1}n)$ time. - When k is not too small, we obtain a truly sublinear-time algorithm to find all locations with Hamming distance approximately (up to a constant factor) less than k, in $O((n/k^{\Omega(1)}+occ)n^{o(1)})$ time, where occ is the output size. The algorithm leads to a property tester, returning true if an exact match exists and false if the Hamming distance is more than $\delta m$ at every location, running in $\~O(\delta^{-1/3}n^{2/3}+\delta^{-1}n/m)$ time. - We obtain a streaming algorithm to report all locations with Hamming distance approximately less than k, using $\~O(\epsilon^{-2}\sqrt k)$ space. Previously, streaming algorithms were known for the exact problem with \~O(k) space or for the approximate problem with $\~O(\epsilon^{-O(1)}\sqrt m)$ space.Open AccessApproximating Text-to-Pattern Hamming Distances
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 $\sigma$, compute the Hamming distance between the pattern and the text at every location. Several $(1+\epsilon)$-approximation algorithms have been proposed in the literature, with running time of the form $O(\epsilon^{-O(1)}n\log n\log m)$, all using fast Fourier transform (FFT). We describe a simple $(1+\epsilon)$-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results: - We obtain the first linear-time approximation algorithm; the running time is $O(\epsilon^{-2}n)$. - We obtain a faster exact algorithm computing all Hamming distances up to a given threshold k; its running time improves previous results by logarithmic factors and is linear if $k\le\sqrt m$. - We obtain approximation algorithms with better $\epsilon$-dependence using rectangular matrix multiplication. The time-bound is $\~O(n)$ when the pattern is sufficiently long: $m\ge \epsilon^{-28}$. Previous algorithms require $\~O(\epsilon^{-1}n)$ time. - When k is not too small, we obtain a truly sublinear-time algorithm to find all locations with Hamming distance approximately (up to a constant factor) less than k, in $O((n/k^{\Omega(1)}+occ)n^{o(1)})$ time, where occ is the output size. The algorithm leads to a property tester, returning true if an exact match exists and false if the Hamming distance is more than $\delta m$ at every location, running in $\~O(\delta^{-1/3}n^{2/3}+\delta^{-1}n/m)$ time. - We obtain a streaming algorithm to report all locations with Hamming distance approximately less than k, using $\~O(\epsilon^{-2}\sqrt k)$ space. Previously, streaming algorithms were known for the exact problem with \~O(k) space or for the approximate problem with $\~O(\epsilon^{-O(1)}\sqrt m)$ space. - Open Access
$\{-1,0,1\}$-APSP and (min,max)-Product Problems
In the $\{-1,0,1\}$-APSP problem the goal is to compute all-pairs shortest paths (APSP) on a directed graph whose edge weights are all from $\{-1,0,1\}$. In the (min,max)-product problem the input is two $n\times n$ matrices $A$ and $B$, and the goal is to output the (min,max)-product of $A$ and $B$. This paper provides a new algorithm for the $\{-1,0,1\}$-APSP problem via a simple reduction to the target-(min,max)-product problem where the input is three $n\times n$ matrices $A,B$, and $T$, and the goal is to output a Boolean $n\times n$ matrix $C$ such that the $(i,j)$ entry of $C$ is 1 if and only if the $(i,j)$ entry of the (min,max)-product of $A$ and $B$ is exactly the $(i,j)$ entry of the target matrix $T$. If (min,max)-product can be solved in $T_{MM}(n) = \Omega(n^2)$ time then it is straightforward to solve target-(min,max)-product in $O(T_{MM}(n))$ time. Thus, given the recent result of Bringmann, K\"unnemann, and Wegrzycki [STOC 2019], the $\{-1,0,1\}$-APSP problem can be solved in the same time needed for solving approximate APSP on graphs with positive weights. Moreover, we design a simple algorithm for target-(min,max)-product when the inputs are restricted to the family of inputs generated by our reduction. Using fast rectangular matrix multiplication, the new algorithm is faster than the current best known algorithm for (min,max)-product.Open Access$\{-1,0,1\}$-APSP and (min,max)-Product Problems
In the $\{-1,0,1\}$-APSP problem the goal is to compute all-pairs shortest paths (APSP) on a directed graph whose edge weights are all from $\{-1,0,1\}$. In the (min,max)-product problem the input is two $n\times n$ matrices $A$ and $B$, and the goal is to output the (min,max)-product of $A$ and $B$. This paper provides a new algorithm for the $\{-1,0,1\}$-APSP problem via a simple reduction to the target-(min,max)-product problem where the input is three $n\times n$ matrices $A,B$, and $T$, and the goal is to output a Boolean $n\times n$ matrix $C$ such that the $(i,j)$ entry of $C$ is 1 if and only if the $(i,j)$ entry of the (min,max)-product of $A$ and $B$ is exactly the $(i,j)$ entry of the target matrix $T$. If (min,max)-product can be solved in $T_{MM}(n) = \Omega(n^2)$ time then it is straightforward to solve target-(min,max)-product in $O(T_{MM}(n))$ time. Thus, given the recent result of Bringmann, K\"unnemann, and Wegrzycki [STOC 2019], the $\{-1,0,1\}$-APSP problem can be solved in the same time needed for solving approximate APSP on graphs with positive weights. Moreover, we design a simple algorithm for target-(min,max)-product when the inputs are restricted to the family of inputs generated by our reduction. Using fast rectangular matrix multiplication, the new algorithm is faster than the current best known algorithm for (min,max)-product. - Open Access
Higher Lower Bounds from the 3SUM Conjecture
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\v{a}tra\c{s}cu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by P\v{a}tra\c{s}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\v{a}tra\c{s}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\alpha)$-time algorithm (SICOMP 1985) for enumerating all triangles in a graph with arboricity/degeneracy $\alpha$ is essentially optimal, for any $\alpha$. - Bj{\o}rklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014) for listing $t$ triangles is essentially optimal (assuming the matrix multiplication exponent is $\omega=2$). - Any static data structure for SetDisjointness that answers queries in constant time must spend $\Omega(N^{2-o(1)})$ time in preprocessing, where $N$ is the size of the set system. These statements were unattainable via P\v{a}tra\c{s}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.Open AccessHigher Lower Bounds from the 3SUM Conjecture
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\v{a}tra\c{s}cu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by P\v{a}tra\c{s}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\v{a}tra\c{s}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\alpha)$-time algorithm (SICOMP 1985) for enumerating all triangles in a graph with arboricity/degeneracy $\alpha$ is essentially optimal, for any $\alpha$. - Bj{\o}rklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014) for listing $t$ triangles is essentially optimal (assuming the matrix multiplication exponent is $\omega=2$). - Any static data structure for SetDisjointness that answers queries in constant time must spend $\Omega(N^{2-o(1)})$ time in preprocessing, where $N$ is the size of the set system. These statements were unattainable via P\v{a}tra\c{s}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. - Open Access
Exponential Separations in the Energy Complexity of Leader Election
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 LeaderElection and ApproximateCounting 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.) The take-away message of our results is quite surprising. For randomized LeaderElection algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD, and for deterministic LeaderElection algorithms there is another exponential gap, but in the reverse direction. In particular, the randomized energy complexity of LeaderElection is $\Theta(\log^* n)$ in Sender-CD but $\Theta(\log(\log^* n))$ in Receiver-CD, where $n$ is the (unknown) number of devices. Its deterministic complexity is $\Theta(\log N)$ in Receiver-CD but $\Theta(\log\log N)$ in Sender-CD, where $N$ is the (known) size of the devices' ID space. There is a tradeoff between time and energy. We give a new upper bound on the time-energy tradeoff curve for randomized LeaderElection and ApproximateCounting. A critical component of this algorithm is a new deterministic LeaderElection algorithm for dense instances, when $n=\Theta(N)$, with inverse-Ackermann-type ($O(\alpha(N))$) energy complexity.Open AccessExponential Separations in the Energy Complexity of Leader Election
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 LeaderElection and ApproximateCounting 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.) The take-away message of our results is quite surprising. For randomized LeaderElection algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD, and for deterministic LeaderElection algorithms there is another exponential gap, but in the reverse direction. In particular, the randomized energy complexity of LeaderElection is $\Theta(\log^* n)$ in Sender-CD but $\Theta(\log(\log^* n))$ in Receiver-CD, where $n$ is the (unknown) number of devices. Its deterministic complexity is $\Theta(\log N)$ in Receiver-CD but $\Theta(\log\log N)$ in Sender-CD, where $N$ is the (known) size of the devices' ID space. There is a tradeoff between time and energy. We give a new upper bound on the time-energy tradeoff curve for randomized LeaderElection and ApproximateCounting. A critical component of this algorithm is a new deterministic LeaderElection algorithm for dense instances, when $n=\Theta(N)$, with inverse-Ackermann-type ($O(\alpha(N))$) energy complexity. - Open Access
Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with $n$ vertices and $m$ edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using $O(\sqrt n)$ processors and $O(\log n)$ worst-case update time, for a total of $O(\sqrt n \log n)$ work. This improves on the work of Ferragina [IPPS 1995] which costs $O(\log n)$ worst-case update time and $O(n^{2/3} \log{\frac{m}{n}})$ work.Open AccessImproved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with $n$ vertices and $m$ edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using $O(\sqrt n)$ processors and $O(\log n)$ worst-case update time, for a total of $O(\sqrt n \log n)$ work. This improves on the work of Ferragina [IPPS 1995] which costs $O(\log n)$ worst-case update time and $O(n^{2/3} \log{\frac{m}{n}})$ work.