Tsvi Kopelowitz
    Email: kopelot [at] gmail [dot] com

Description: Description: Description: Description: Description: Description: image001.gif

Brief Biogrophy

I am currently a Postdoctoral Fellow in the Department of Electrical Engineering and Computer Science in University of Michigan, hosted by Seth Pettie. Before that I was a Postdoctoral Fellow in the Faculty of Mathematics and Computer Science in The Weizmann Institute of Science, hosted by Robert Krauthgamer. I completed my PhD in the Computer Science Department of Bar Ilan University, under the supervision of Moshe Lewenstein.

Description: Description: Description: Description: Description: Description: image001.gif

Current Research Interesets

I am interested in the analysis of algorithms and data structures at large, with a special focus on dynamic problems. Some of my recent research has focused on:

-         Advanced data structures, with an emphasis on indexing data structures and dynamizing static data structures.

-         (Dynamic) graph problems.

-         Conditional lower bounds (for example under the 3SUM conjecture).

-         Pattern Matching algorithms and stringology.

-         Algorithms for distributed computing.

Description: Description: Description: Description: Description: Description: image001.gif

Program Committees

         CPM 2016

         CPM 2015

         SPIRE 2014

         CPM 2013

         SPIRE 2013

Description: Description: Description: Description: Description: Description: image001.gif

Teaching

Past (Bar Ilan University, and Weizmann Institute):

        Data Structures (Spring 2012, Spring 2010)

        Algorithms 1 (Fall 2013 (lectured), Fall 2012, Fall 2011, Fall 2010, Fall 2009, Fall 2006,Summer 2005 (lectured), Spring 2005 - for Engineering students (lectured), Summer 2004 (lectured), Fall 2004)

        Algorithms 2 (Spring 2013,Spring 2012,Spring 2011, Spring 2005,)

        Advanced Data Structures (Spring 2011)

        Object Oriented Programming (Spring 2006)

         Programming Languages (Spring 2004)

Description: Description: Description: Description: Description: Description: image001.gif

Manuscripts

[5] Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. Manuscript. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[4] Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup: Deterministic Worst Case Dynamic Connectivity: Simpler and Faster. Manuscript. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[3] Amihood Amir, Tsvi Kopelowitz, Avivit Levi, Seth Pettie, Ely Porat, B. Riva Shalom: Mind the Gap . Manuscript. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[2] Amihood Amir, Oren Kapah, Tsvi Kopelowitz, Moni Naor, Ely Porat: The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets. Manuscript. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[1] Tsvi Kopelowitz, Robert Krauthgamer: Faster Clustering Via Preprocessing. Manuscript . Description: Description: Description: Description: Description: Description: paper-pdf.gif

Description: Description: Description: Description: Description: Description: image001.gif

Publications

[22] Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young : Contention Resolution with Log-Logstar Channel Accesses. Accepted to STOC 2016. Manuscript - coming soon. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[21] Tsvi Kopelowitz, Seth Pettie, Ely Porat : Higher Lower Bounds from the 3SUM Conjecture. Accepted to SODA 2016. Manuscript. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[20] Tsvi Kopelowitz, Ely Porat: Breaking the Variance: Approximating the Hamming Distance in O~(1/epsilon) Time Per Alignment. Accepted to FOCS 2015. Manuscript. Description: Description: Description: Description: Description: Description: paper-pdf.gif

[19] Tsvi Kopelowitz, Seth Pettie, Ely Porat: Dynamic Set Intersection . Accepted to WADS 2015. A preliminary version appears as part of the following manuscript.Description: Description: Description: Description: Description: Description: paper-pdf.gif

[18] Tsvi Kopelwoitz, Robert Krauthgamer, Ely Porat, Shay Solomon: Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of International Colloquium on Automata, Languages and Programming (ICALP), 2014.

[17] Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein: Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Accepted to SICOMP, 2014.
Part of this work appeared in Amihood Amir, Tsvi Kopelowitz, Moshe Lewnestein, Noa Lewenstein. Toward Real-Time Suffix Tree Construction.

Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2005.

[16] Tsvi Kopelowitz, Gregory Kucherov, Yakov Nekrich, Tatiana A. Starikovskaya: Cross-document pattern matching. Description: Description: Description: Description: Description: Description: paper-pdf.gif
J. Discrete Algorithms 24, 2014.

[15] Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj: Sparse Suffix Tree Construction with Small Space. Description: Description: Description: Description: Description: Description: paper-pdf.gif  
Proc. of International Colloquium on Automata, Languages and Programming (ICALP), 2013.

[14] Tsvi Kopelowitz, Nimrod Talmon: Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc of The 23rd International Symposium on. Algorithms and Computation (ISAAC), 2012.

[13] Tsvi Kopelowitz: On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012.

[12] Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, Niko Välimäki: Forbidden Patterns. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of Latin American Symposium (LATIN), 2012.

[11] Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat: Persistency in Suffix Trees with Applications to String Interval Problems. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2011.

[10] Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty: Fast, precise and dynamic distance queries. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of Symposium on Discrete Algorithms (SODA), 2011.

[9] Tsvi Kopelowitz. The Property Suffix Tree with Dynamic Properties. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of Combinatorial Pattern Matching (CPM) 2010.

[8] Orgad Keller, Tsvi Kopelowitz, Shir Landau, Moshe Lewenstein. Faster Algorithms for Substring Compression Problems. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Also in Theor. Comput. Sci. 525, 2014. Also appeared in Proc. of Combinatorial Pattern Matching (CPM) 2009.

[7] Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein. On the Longest Common Parameterized Subsequence. Description: Description: Description: Description: Description: Description: paper-pdf.gif
In Theoretical Computer Science, November 2009. Also appeared in Proc.of Combinatorial Pattern Matching (CPM) 2008.

[5] Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein. Range Non-Overlapping Indexing and Successive List Indexing. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of Workshop on Algorithms and Data Structures (WADS), 2007.

[4] Tsvi Kopelowitz, Moshe Lewenstein. Dynamic Weighted Ancestors. Full version coming soon.
Proc. of Symposium on Discrete Algorithms (SODA), 2007.

[3] Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein. Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Accepted to Algorithmica, 2014. Also appeared in Proc. of International Colloquium on Automata, Languages and Programming (ICALP), 2006.

[2] Amihood Amir, Eran Chencinski, Costas S. Iliopoulos, Tsvi Kopelowitz, Hui Zhang. Property Matching and Weighted Matching. Description: Description: Description: Description: Description: Description: paper-pdf.gif
Proc. of Combinatorial Pattern Matching (CPM), 2006.

[1] Tsvi Kopelowitz, Ely Porat. Improved Algorithms for Polynomial Time-Decay and Time-Decay with Additive error.
In Theory Comput. Syst., 2008. Also appeared in Proc. Of the Ninth Italian Conference on Theoretical Computer Science (ICTCS), 2005.