Moshe Lewenstein

According to our database, Moshe Lewenstein authored at least 101 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Gapped String Indexing in Subquadratic Space and Sublinear Query Time.

Philip Bille, Inge Li Gørtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, Teresa Anna Steiner

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

String Factorization via Prefix Free Families.

Matan Kraus, Moshe Lewenstein, Alexandru Popa, Ely Porat, Yonathan Sadia

Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, 2023

2019

Can We Recover the Cover?

Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, Benny Porat

Algorithmica, 2019

On the Hardness of Set Disjointness and Set Intersection with Bounded Universe.

Isaac Goldstein, Moshe Lewenstein, Ely Porat

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

2018

Improved Space-Time Tradeoffs for kSUM.

Isaac Goldstein, Moshe Lewenstein, Ely Porat

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

On the Succinct Representation of Equivalence Classes.

Hicham El-Zein, Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Timothy M. Chan

Algorithmica, 2017

Conditional Lower Bounds for Space/Time Tradeoffs.

Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Orthogonal Vectors Indexing.

Isaac Goldstein, Moshe Lewenstein, Ely Porat

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

2016

Parameterized Pattern Matching.

Moshe Lewenstein

Encyclopedia of Algorithms, 2016

Dictionary Matching.

Moshe Lewenstein

Encyclopedia of Algorithms, 2016

Document retrieval with one wildcard.

Moshe Lewenstein, J. Ian Munro, Yakov Nekrich, Sharma V. Thankachan

Theor. Comput. Sci., 2016

Two dimensional range minimum queries and Fibonacci lattices.

Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Srinivasa Rao Satti

Theor. Comput. Sci., 2016

Special issue in honor of the 60th birthday of Amihood Amir.

Gary Benson, Martin Farach-Colton, Moshe Lewenstein, Ely Porat

Theor. Comput. Sci., 2016

Structure and Hardness in P (Dagstuhl Seminar 16451).

Moshe Lewenstein, Seth Pettie, Virginia Vassilevska Williams

Dagstuhl Reports, 2016

How Hard is it to Find (Honest) Witnesses?.

Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Suffix Trays and Suffix Trists: Structures for Faster Text Indexing.

Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein

Algorithmica, 2015

Clustered Integer 3SUM via Additive Combinatorics.

Timothy M. Chan, Moshe Lewenstein

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Range LCP Queries Revisited.

Amihood Amir, Moshe Lewenstein, Sharma V. Thankachan

Proceedings of the String Processing and Information Retrieval, 2015

Beyond the Runs Theorem.

Johannes Fischer, Stepan Holub, Tomohiro I, Moshe Lewenstein

Proceedings of the String Processing and Information Retrieval, 2015

Range Minimum Query Indexes in Higher Dimensions.

Pooya Davoodi, John Iacono, Gad M. Landau, Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Fast String Dictionary Lookup with One Error.

Timothy M. Chan, Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Longest Common Extensions in Sublinear Space.

Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, Hjalte Wedel Vildhøj

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014

Less space: Indexing for queries with wildcards.

Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Sharma V. Thankachan

Theor. Comput. Sci., 2014

Generalized substring compression.

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

Theor. Comput. Sci., 2014

Quick greedy computation for minimum common string partition.

Isaac Goldstein, Moshe Lewenstein

Theor. Comput. Sci., 2014

Two-Dimensional Parameterized Matching.

Richard Cole, Carmit Hazay, Moshe Lewenstein, Dekel Tsur

ACM Trans. Algorithms, 2014

Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing.

Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein

SIAM J. Comput., 2014

Range LCP.

Amihood Amir, Alberto Apostolico, Gad M. Landau, Avivit Levy, Moshe Lewenstein, Ely Porat

J. Comput. Syst. Sci., 2014

Space-Efficient String Indexing for Wildcard Pattern Matching.

Moshe Lewenstein, Yakov Nekrich, Jeffrey Scott Vitter

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

On Hardness of Jumbled Indexing.

Amihood Amir, Timothy M. Chan, Moshe Lewenstein, Noa Lewenstein

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Improved Explicit Data Structures in the Bitprobe Model.

Moshe Lewenstein, J. Ian Munro, Patrick K. Nicholson, Venkatesh Raman

Proceedings of the Algorithms - ESA 2014, 2014

Weighted Ancestors in Suffix Trees.

Pawel Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson

Proceedings of the Algorithms - ESA 2014, 2014

Hypertext Searching - A Survey.

Amihood Amir, Moshe Lewenstein, Noa Lewenstein

Proceedings of the Language, Culture, Computation. Computing - Theory and Technology, 2014

2013

Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing.

Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein

CoRR, 2013

Finding the Minimum-Weight k-Path.

Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Succinct Data Structures for Representing Equivalence Classes.

Moshe Lewenstein, J. Ian Munro, Venkatesh Raman

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

LCP Magic.

Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Orthogonal Range Searching for Text Indexing.

Moshe Lewenstein

Proceedings of the Space-Efficient Data Structures, 2013

2012

On demand string sorting over unbounded alphabets.

Carmel Kent, Moshe Lewenstein, Dafna Sheinwald

Theor. Comput. Sci., 2012

Dotted interval graphs.

Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini

ACM Trans. Algorithms, 2012

An efficient algorithm to test square-freeness of strings compressed by straight-line programs.

Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein

Inf. Process. Lett., 2012

Parikh Matching in the Streaming Model.

Lap-Kei Lee, Moshe Lewenstein, Qin Zhang

Proceedings of the String Processing and Information Retrieval, 2012

Forbidden Patterns.

Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, Niko Välimäki

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

2011

Finding witnesses by peeling.

Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur

ACM Trans. Algorithms, 2011

CPM 2006.

Moshe Lewenstein, Gabriel Valiente

J. Discrete Algorithms, 2011

Indexing with Gaps.

Moshe Lewenstein

Proceedings of the String Processing and Information Retrieval, 2011

Persistency in Suffix Trees with Applications to String Interval Problems.

Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat

Proceedings of the String Processing and Information Retrieval, 2011

Fast, precise and dynamic distance queries.

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

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Quick Greedy Computation for Minimum Common String Partitions.

Isaac Goldstein, Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

Restricted Common Superstring and Restricted Common Supersequence.

Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa

Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

2010

Optimization problems in multiple-interval graphs.

Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz

ACM Trans. Algorithms, 2010

Permuted Common Supersequence

Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa

CoRR, 2010

On the Longest Common Rigid Subsequence Problem.

Nikhil Bansal, Moshe Lewenstein, Bin Ma, Kaizhong Zhang

Algorithmica, 2010

On Shortest Common Superstring and Swap Permutations.

Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa

Proceedings of the String Processing and Information Retrieval, 2010

Restricted LCS.

Zvi Gotthilf, Danny Hermelin, Gad M. Landau, Moshe Lewenstein

Proceedings of the String Processing and Information Retrieval, 2010

2009

On the longest common parameterized subsequence.

Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein

Theor. Comput. Sci., 2009

Improved algorithms for the k simple shortest paths and the replacement paths problems.

Zvi Gotthilf, Moshe Lewenstein

Inf. Process. Lett., 2009

Real Two Dimensional Scaled Matching.

Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat

Algorithmica, 2009

Improved Approximation Results on the Shortest Common Supersequence Problem.

Zvi Gotthilf, Moshe Lewenstein

Proceedings of the String Processing and Information Retrieval, 2009

2008

Parameterized Matching.

Moshe Lewenstein

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Dictionary Matching and Indexing (Exact and with Errors).

Moshe Lewenstein

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

A Approximation Algorithm for the Minimum Maximal Matching Problem.

Zvi Gotthilf, Moshe Lewenstein, Elad Rainshmidt

Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

Constrained LCS: Hardness and Approximation.

Zvi Gotthilf, Danny Hermelin, Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2007

Approximate parameterized matching.

Carmit Hazay, Moshe Lewenstein, Dina Sokol

ACM Trans. Algorithms, 2007

Dynamic text and static pattern matching.

Amihood Amir, Gad M. Landau, Moshe Lewenstein, Dina Sokol

ACM Trans. Algorithms, 2007

Parameterized matching with mismatches.

Alberto Apostolico, Péter L. Erdös, Moshe Lewenstein

J. Discrete Algorithms, 2007

Efficient one-dimensional real scaled matching.

Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur

J. Discrete Algorithms, 2007

Range Non-overlapping Indexing and Successive List Indexing.

Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Approximating Constrained LCS.

Zvi Gotthilf, Moshe Lewenstein

Proceedings of the String Processing and Information Retrieval, 2007

Dynamic weighted ancestors.

Tsvi Kopelowitz, Moshe Lewenstein

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Two-Dimensional Range Minimum Queries.

Amihood Amir, Johannes Fischer, Moshe Lewenstein

Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006

Function Matching.

Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat

SIAM J. Comput., 2006

2005

Constructive Bounds on Ordered Factorizations.

Don Coppersmith, Moshe Lewenstein

SIAM J. Discret. Math., 2005

An improved upper bound for the TSP in cubic 3-edge-connected graphs.

David Gamarnik, Moshe Lewenstein, Maxim Sviridenko

Oper. Res. Lett., 2005

Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs.

Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko

J. ACM, 2005

Tighter Approximations for Maximum Induced Matchings in Regular Graphs.

Zvi Gotthilf, Moshe Lewenstein

Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Towards Real-Time Suffix Tree Construction.

Amihood Amir, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein

Proceedings of the String Processing and Information Retrieval, 2005

Dotted interval graphs and high throughput genotyping.

Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Two Dimensional Parameterized Matching.

Carmit Hazay, Moshe Lewenstein, Dekel Tsur

Proceedings of the Combinatorial Pattern Matching, 16th Annual Symposium, 2005

2004

Faster algorithms for string matching with k mismatches.

Amihood Amir, Moshe Lewenstein, Ely Porat

J. Algorithms, 2004

Dictionary matching and indexing with errors and don't cares.

Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Closest Pair Problems in Very High Dimensions.

Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP.

Moshe Lewenstein, Maxim Sviridenko

SIAM J. Discret. Math., 2003

Overlap matching.

Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

Inf. Comput., 2003

Approximating asymmetric maximum TSP.

Moshe Lewenstein, Maxim Sviridenko

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Multidimensional matching and fast search in suffix trees.

Richard Cole, Moshe Lewenstein

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Function Matching: Algorithms, Applications, and a Lower Bound.

Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

Approximate swapped matching.

Amihood Amir, Moshe Lewenstein, Ely Porat

Inf. Process. Lett., 2002

2001

Uniquely Restricted Matchings.

Martin Charles Golumbic, Tirza Hirst, Moshe Lewenstein

Algorithmica, 2001

A faster implementation of the Goemans-Williamson clustering algorithm.

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Approximate subset matching with Don't Cares.

Amihood Amir, Ely Porat, Moshe Lewenstein

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

Pattern Matching in Hypertext.

Amihood Amir, Moshe Lewenstein, Noa Lewenstein

J. Algorithms, 2000

Text Indexing and Dictionary Matching with One Error.

Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Michael Rodeh

J. Algorithms, 2000

Pattern Matching with Swaps.

Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein

J. Algorithms, 2000

New results on induced matchings.

Martin Charles Golumbic, Moshe Lewenstein

Discret. Appl. Math., 2000

Faster algorithms for string matching with <i>k</i> mismatches.

Amihood Amir, Moshe Lewenstein, Ely Porat

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

Real Scaled Matching.

Amihood Amir, Ayelet Butman, Moshe Lewenstein

Inf. Process. Lett., 1999

Alternation and Bounded Concurrency Are Reverse Equivalent.

Tirza Hirst, Moshe Lewenstein

Inf. Comput., 1999

Indexing and Dictionary Matching with One Error.

Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Michael Rodeh

Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

1998

Efficient Special Cases of Pattern Matching with Swaps.

Amihood Amir, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein

Inf. Process. Lett., 1998

1997

Inverse Pattern Matching.

Amihood Amir, Alberto Apostolico, Moshe Lewenstein

J. Algorithms, 1997