Moshe Lewenstein

142 papers A* 17A 8B 33C 12Journal 62Unranked 6

Year	Rank	Type	Title / Venue / Authors
2024	A	`conf`	Gapped String Indexing in Subquadratic Space and Sublinear Query Time. STACS Philip Bille, Inge Li Gørtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, Teresa Anna Steiner
2023	B	`conf`	String Factorization via Prefix Free Families. CPM Matan Kraus, Moshe Lewenstein, Alexandru Popa, Ely Porat, Yonathan Sadia
2022	J	`jnl`	Gapped String Indexing in Subquadratic Space and Sublinear Query Time. CoRR Philip Bille, Inge Li Gørtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, Teresa Anna Steiner
2019	J	`jnl`	Can We Recover the Cover? Algorithmica Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, Benny Porat
2019	B	`conf`	On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. ISAAC Isaac Goldstein, Moshe Lewenstein, Ely Porat
2019	J	`jnl`	On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. CoRR Isaac Goldstein, Moshe Lewenstein, Ely Porat
2018	A	`conf`	Improved Space-Time Tradeoffs for kSUM. ESA Isaac Goldstein, Moshe Lewenstein, Ely Porat
2018	J	`jnl`	Improved Space-Time Tradeoffs for kSUM. CoRR Isaac Goldstein, Moshe Lewenstein, Ely Porat
2017	B	`conf`	Can We Recover the Cover?. CPM Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, Benny Porat
2017	B	`conf`	Conditional Lower Bounds for Space/Time Tradeoffs. WADS Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat
2017	J	`jnl`	Conditional Lower Bounds for Space/Time Tradeoffs. CoRR Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat
2017	J	`jnl`	How Hard is it to Find (Honest) Witnesses? CoRR Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat
2017	J	`jnl`	On the Succinct Representation of Equivalence Classes. Algorithmica Hicham El-Zein, Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Timothy M. Chan
2017	B	`conf`	Orthogonal Vectors Indexing. ISAAC Isaac Goldstein, Moshe Lewenstein, Ely Porat
2017	J	`jnl`	Orthogonal Vectors Indexing. CoRR Isaac Goldstein, Moshe Lewenstein, Ely Porat
2016	B	`ed.`	27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, Tel Aviv, Israel, June 27-29, 2016 CPM Roberto Grossi, Moshe Lewenstein
2016	—	`ch.`	Dictionary Matching. Encyclopedia of Algorithms Moshe Lewenstein
2016	J	`jnl`	Document retrieval with one wildcard. Theor. Comput. Sci. Moshe Lewenstein, J. Ian Munro, Yakov Nekrich, Sharma V. Thankachan
2016	A	`conf`	How Hard is it to Find (Honest) Witnesses?. ESA Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat
2016	—	`ch.`	Parameterized Pattern Matching. Encyclopedia of Algorithms Moshe Lewenstein
2016	J	`jnl`	Special issue in honor of the 60th birthday of Amihood Amir. Theor. Comput. Sci. Gary Benson, Martin Farach-Colton, Moshe Lewenstein, Ely Porat
2016	J	`jnl`	Structure and Hardness in P (Dagstuhl Seminar 16451). Dagstuhl Reports Moshe Lewenstein, Seth Pettie, Virginia Vassilevska Williams
2016	J	`jnl`	Two dimensional range minimum queries and Fibonacci lattices. Theor. Comput. Sci. Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Srinivasa Rao Satti
2015	C	`conf`	Beyond the Runs Theorem. SPIRE Johannes Fischer, Stepan Holub, Tomohiro I, Moshe Lewenstein
2015	A*	`conf`	Clustered Integer 3SUM via Additive Combinatorics. STOC Timothy M. Chan, Moshe Lewenstein
2015	J	`jnl`	Clustered Integer 3SUM via Additive Combinatorics. CoRR Timothy M. Chan, Moshe Lewenstein
2015	B	`conf`	Fast String Dictionary Lookup with One Error. CPM Timothy M. Chan, Moshe Lewenstein
2015	B	`conf`	Longest Common Extensions in Sublinear Space. CPM Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, Hjalte Wedel Vildhøj
2015	J	`jnl`	Longest Common Extensions in Sublinear Space. CoRR Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, Hjalte Wedel Vildhøj
2015	C	`conf`	Range LCP Queries Revisited. SPIRE Amihood Amir, Moshe Lewenstein, Sharma V. Thankachan
2015	B	`conf`	Range Minimum Query Indexes in Higher Dimensions. CPM Pooya Davoodi, John Iacono, Gad M. Landau, Moshe Lewenstein
2015	J	`jnl`	Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. Algorithmica Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein
2014	—	`conf`	Document Retrieval with One Wildcard. MFCS (2) Moshe Lewenstein, J. Ian Munro, Yakov Nekrich, Sharma V. Thankachan
2014	J	`jnl`	Generalized substring compression. Theor. Comput. Sci. Orgad Keller, Tsvi Kopelowitz, Shir Landau Feibish, Moshe Lewenstein
2014	—	`conf`	Hypertext Searching - A Survey. Language, Culture, Computation (1) Amihood Amir, Moshe Lewenstein, Noa Lewenstein
2014	A	`conf`	Improved Explicit Data Structures in the Bitprobe Model. ESA Moshe Lewenstein, J. Ian Munro, Patrick K. Nicholson, Venkatesh Raman
2014	J	`jnl`	Less space: Indexing for queries with wildcards. Theor. Comput. Sci. Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Sharma V. Thankachan
2014	J	`jnl`	Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing. SIAM J. Comput. Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein
2014	—	`conf`	On Hardness of Jumbled Indexing. ICALP (1) Amihood Amir, Timothy M. Chan, Moshe Lewenstein, Noa Lewenstein
2014	J	`jnl`	On Hardness of Jumbled Indexing. CoRR Amihood Amir, Timothy M. Chan, Moshe Lewenstein, Noa Lewenstein
2014	J	`jnl`	Quick greedy computation for minimum common string partition. Theor. Comput. Sci. Isaac Goldstein, Moshe Lewenstein
2014	J	`jnl`	Range LCP. J. Comput. Syst. Sci. Amihood Amir, Alberto Apostolico, Gad M. Landau, Avivit Levy, Moshe Lewenstein, Ely Porat
2014	A	`conf`	Space-Efficient String Indexing for Wildcard Pattern Matching. STACS Moshe Lewenstein, Yakov Nekrich, Jeffrey Scott Vitter
2014	J	`jnl`	Space-Efficient String Indexing for Wildcard Pattern Matching. CoRR Moshe Lewenstein, Yakov Nekrich, Jeffrey Scott Vitter
2014	J	`jnl`	Two-Dimensional Parameterized Matching. ACM Trans. Algorithms Richard Cole, Carmit Hazay, Moshe Lewenstein, Dekel Tsur
2014	A	`conf`	Weighted Ancestors in Suffix Trees. ESA Pawel Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson
2014	J	`jnl`	Weighted ancestors in suffix trees. CoRR Pawel Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson
2013	B	`conf`	Finding the Minimum-Weight k-Path. WADS Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty
2013	J	`jnl`	Finding the Minimum-Weight k-Path. CoRR Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty
2013	B	`conf`	LCP Magic. CPM Moshe Lewenstein
2013	B	`conf`	Less Space: Indexing for Queries with Wildcards. ISAAC Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Sharma V. Thankachan
2013	J	`jnl`	Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing. CoRR Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein
2013	—	`conf`	Orthogonal Range Searching for Text Indexing. Space-Efficient Data Structures, Streams, and Algorithms Moshe Lewenstein
2013	J	`jnl`	Orthogonal Range Searching for Text Indexing. CoRR Moshe Lewenstein
2013	C	`ed.`	String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Jerusalem, Israel, October 7-9, 2013, Proceedings SPIRE Oren Kurland, Moshe Lewenstein, Ely Porat
2013	B	`conf`	Succinct Data Structures for Representing Equivalence Classes. ISAAC Moshe Lewenstein, J. Ian Munro, Venkatesh Raman
2013	J	`jnl`	Succinct data structures for representing equivalence classes. CoRR Moshe Lewenstein, J. Ian Munro, Venkatesh Raman
2013	J	`jnl`	Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. CoRR Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein
2012	J	`jnl`	An efficient algorithm to test square-freeness of strings compressed by straight-line programs. Inf. Process. Lett. Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein
2012	J	`jnl`	Dotted interval graphs. ACM Trans. Algorithms Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini
2012	B	`conf`	Forbidden Patterns. LATIN Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, Niko Välimäki
2012	J	`jnl`	On demand string sorting over unbounded alphabets. Theor. Comput. Sci. Carmel Kent, Moshe Lewenstein, Dafna Sheinwald
2012	C	`conf`	Parikh Matching in the Streaming Model. SPIRE Lap-Kei Lee, Moshe Lewenstein, Qin Zhang
2012	A	`conf`	Two Dimensional Range Minimum Queries and Fibonacci Lattices. ESA Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, S. Srinivasa Rao
2011	J	`jnl`	CPM 2006. J. Discrete Algorithms Moshe Lewenstein, Gabriel Valiente
2011	A*	`conf`	Fast, precise and dynamic distance queries. SODA Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty
2011	J	`jnl`	Finding witnesses by peeling. ACM Trans. Algorithms Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur
2011	C	`conf`	Indexing with Gaps. SPIRE Moshe Lewenstein
2011	C	`conf`	Persistency in Suffix Trees with Applications to String Interval Problems. SPIRE Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat
2011	B	`conf`	Quick Greedy Computation for Minimum Common String Partitions. CPM Isaac Goldstein, Moshe Lewenstein
2011	B	`conf`	Range LCP. ISAAC Amihood Amir, Alberto Apostolico, Gad M. Landau, Avivit Levy, Moshe Lewenstein, Ely Porat
2011	B	`conf`	Restricted Common Superstring and Restricted Common Supersequence. CPM Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa
2010	J	`jnl`	Fast, precise and dynamic distance queries CoRR Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty
2010	C	`conf`	On Shortest Common Superstring and Swap Permutations. SPIRE Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa
2010	J	`jnl`	On the Longest Common Rigid Subsequence Problem. Algorithmica Nikhil Bansal, Moshe Lewenstein, Bin Ma, Kaizhong Zhang
2010	J	`jnl`	Optimization problems in multiple-interval graphs. ACM Trans. Algorithms Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz
2010	J	`jnl`	Permuted Common Supersequence CoRR Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa
2010	C	`conf`	Restricted LCS. SPIRE Zvi Gotthilf, Danny Hermelin, Gad M. Landau, Moshe Lewenstein
2009	B	`conf`	Generalized Substring Compression. CPM Orgad Keller, Tsvi Kopelowitz, Shir Landau, Moshe Lewenstein
2009	C	`conf`	Improved Approximation Results on the Shortest Common Supersequence Problem. SPIRE Zvi Gotthilf, Moshe Lewenstein
2009	J	`jnl`	Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett. Zvi Gotthilf, Moshe Lewenstein
2009	J	`jnl`	On the longest common parameterized subsequence. Theor. Comput. Sci. Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein
2009	J	`jnl`	Real Two Dimensional Scaled Matching. Algorithmica Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat
2008	B	`conf`	A Approximation Algorithm for the Minimum Maximal Matching Problem. WAOA Zvi Gotthilf, Moshe Lewenstein, Elad Rainshmidt
2008	B	`conf`	Constrained LCS: Hardness and Approximation. CPM Zvi Gotthilf, Danny Hermelin, Moshe Lewenstein
2008	—	`ch.`	Dictionary Matching and Indexing (Exact and with Errors). Encyclopedia of Algorithms Moshe Lewenstein
2008	B	`conf`	On the Longest Common Parameterized Subsequence. CPM Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein
2008	—	`ch.`	Parameterized Matching. Encyclopedia of Algorithms Moshe Lewenstein
2007	J	`jnl`	Approximate parameterized matching. ACM Trans. Algorithms Carmit Hazay, Moshe Lewenstein, Dina Sokol
2007	C	`conf`	Approximating Constrained LCS. SPIRE Zvi Gotthilf, Moshe Lewenstein
2007	J	`jnl`	Dynamic text and static pattern matching. ACM Trans. Algorithms Amihood Amir, Gad M. Landau, Moshe Lewenstein, Dina Sokol
2007	A*	`conf`	Dynamic weighted ancestors. SODA Tsvi Kopelowitz, Moshe Lewenstein
2007	J	`jnl`	Efficient one-dimensional real scaled matching. J. Discrete Algorithms Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur
2007	B	`conf`	Finding Witnesses by Peeling. CPM Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur
2007	B	`conf`	On Demand String Sorting over Unbounded Alphabets. CPM Carmel Kent, Moshe Lewenstein, Dafna Sheinwald
2007	A*	`conf`	Optimization problems in multiple-interval graphs. SODA Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz
2007	J	`jnl`	Parameterized matching with mismatches. J. Discrete Algorithms Alberto Apostolico, Péter L. Erdös, Moshe Lewenstein
2007	B	`conf`	Range Non-overlapping Indexing and Successive List Indexing. WADS Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein
2007	B	`conf`	Two-Dimensional Range Minimum Queries. CPM Amihood Amir, Johannes Fischer, Moshe Lewenstein
2006	B	`ed.`	Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006, Proceedings CPM Moshe Lewenstein, Gabriel Valiente
2006	J	`jnl`	Function Matching. SIAM J. Comput. Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat
2006	—	`conf`	Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. ICALP (1) Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein
2005	J	`jnl`	An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. David Gamarnik, Moshe Lewenstein, Maxim Sviridenko
2005	J	`jnl`	Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko
2005	J	`jnl`	Constructive Bounds on Ordered Factorizations. SIAM J. Discret. Math. Don Coppersmith, Moshe Lewenstein
2005	A*	`conf`	Dotted interval graphs and high throughput genotyping. SODA Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini
2005	B	`conf`	Tighter Approximations for Maximum Induced Matchings in Regular Graphs. WAOA Zvi Gotthilf, Moshe Lewenstein
2005	C	`conf`	Towards Real-Time Suffix Tree Construction. SPIRE Amihood Amir, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein
2005	B	`conf`	Two Dimensional Parameterized Matching. CPM Carmit Hazay, Moshe Lewenstein, Dekel Tsur
2004	A	`conf`	Approximate Parameterized Matching. ESA Carmit Hazay, Moshe Lewenstein, Dina Sokol
2004	A*	`conf`	Closest Pair Problems in Very High Dimensions. ICALP Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat
2004	A*	`conf`	Dictionary matching and indexing with errors and don't cares. STOC Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein
2004	C	`conf`	Efficient One Dimensional Real Scaled Matching. SPIRE Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur
2004	J	`jnl`	Faster algorithms for string matching with k mismatches. J. Algorithms Amihood Amir, Moshe Lewenstein, Ely Porat
2003	J	`jnl`	A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP. SIAM J. Discret. Math. Moshe Lewenstein, Maxim Sviridenko
2003	A*	`conf`	Approximating asymmetric maximum TSP. SODA Moshe Lewenstein, Maxim Sviridenko
2003	A*	`conf`	Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. FOCS Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko
2003	B	`conf`	Dynamic Text and Static Pattern Matching. WADS Amihood Amir, Gad M. Landau, Moshe Lewenstein, Dina Sokol
2003	A*	`conf`	Function Matching: Algorithms, Applications, and a Lower Bound. ICALP Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat
2003	A*	`conf`	Multidimensional matching and fast search in suffix trees. SODA Richard Cole, Moshe Lewenstein
2003	J	`jnl`	Overlap matching. Inf. Comput. Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
2003	B	`conf`	Real Two Dimensional Scaled Matching. WADS Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat
2002	J	`jnl`	Approximate swapped matching. Inf. Process. Lett. Amihood Amir, Moshe Lewenstein, Ely Porat
2001	A*	`conf`	A faster implementation of the Goemans-Williamson clustering algorithm. SODA Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
2001	A*	`conf`	Approximate subset matching with Don't Cares. SODA Amihood Amir, Ely Porat, Moshe Lewenstein
2001	A*	`conf`	Overlap matching. SODA Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
2001	J	`jnl`	Uniquely Restricted Matchings. Algorithmica Martin Charles Golumbic, Tirza Hirst, Moshe Lewenstein
2000	—	`conf`	Approximate Swapped Matching. FSTTCS Amihood Amir, Moshe Lewenstein, Ely Porat
2000	A*	`conf`	Faster algorithms for string matching with SODA Amihood Amir, Moshe Lewenstein, Ely Porat
2000	J	`jnl`	New results on induced matchings. Discret. Appl. Math. Martin Charles Golumbic, Moshe Lewenstein
2000	J	`jnl`	Pattern Matching in Hypertext. J. Algorithms Amihood Amir, Moshe Lewenstein, Noa Lewenstein
2000	J	`jnl`	Pattern Matching with Swaps. J. Algorithms Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein
2000	A*	`conf`	Real scaled matching. SODA Amihood Amir, Ayelet Butman, Moshe Lewenstein
2000	J	`jnl`	Text Indexing and Dictionary Matching with One Error. J. Algorithms Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Michael Rodeh
1999	J	`jnl`	Alternation and Bounded Concurrency Are Reverse Equivalent. Inf. Comput. Tirza Hirst, Moshe Lewenstein
1999	B	`conf`	Indexing and Dictionary Matching with One Error. WADS Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Michael Rodeh
1999	J	`jnl`	Real Scaled Matching. Inf. Process. Lett. Amihood Amir, Ayelet Butman, Moshe Lewenstein
1998	B	`conf`	Efficient Special Cases of Pattern Matching with Swaps. CPM Amihood Amir, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein
1998	J	`jnl`	Efficient Special Cases of Pattern Matching with Swaps. Inf. Process. Lett. Amihood Amir, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein
1997	J	`jnl`	Inverse Pattern Matching. J. Algorithms Amihood Amir, Alberto Apostolico, Moshe Lewenstein
1997	B	`conf`	Pattern Matching In Hypertext. WADS Amihood Amir, Moshe Lewenstein, Noa Lewenstein
1997	A*	`conf`	Pattern Matching with Swaps. FOCS Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein