Arrow Research search

Author name cluster

Tsvi Kopelowitz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers
2 author rows

Possible papers

17

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.

Details

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.

Details

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.

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details