Publications

 

Refereed papers in Journals

 

  1. A. Amir, A. Apostolico and M. Lewenstein, Inverse Pattern Matching, J. of Algorithms, 24:325-339, 1997.
  2. A. Amir, G. Landau, M. Lewenstein and N. Lewenstein, Efficient Special Cases of Pattern Matching with Swaps, Information Processing Letters, 68(3):125-132, 1998.
  3. T. Hirst and M. Lewenstein, Alternation and Bounded Concurrency are Reverse Equivalent, Information and Computation, 152(2):173-187, 1999.
  4. A. Amir, A. Butman and M. Lewenstein, Real Scaled Matching, Information Processing Letters, 70(4):185-190, 1999.
  5. M.C. Golumbic and M. Lewenstein, New Results on Strong Matchings, Discrete Applied Math, 101(1-3):157-165, 2000.
  6. A. Amir, M. Lewenstein and N. Lewenstein, Pattern Matching in Hypertext, J. of Algorithms, 35(1):82-99, 2000.
  7. A. Amir, D. Kesselman, G. Landau, M. Lewenstein, N. Lewenstein and M. Rodeh, Indexing and Dictionary Matching with One Error, J. of Algorithms, 37(2):309-325, 2000.
  8. A. Amir, Y. Aumann, G. Landau, M. Lewenstein and N. Lewenstein, Pattern Matching with Swaps, J. of Algorithms, 37(2):247-266, 2000.
  9. M.C. Golumbic, T. Hirst and M. Lewenstein, Uniquely Restricted Matchings, Algorithmica, 31(2):139-154, 2001.
  10. A. Amir, M. Lewenstein and E. Porat, Approximate Swapped Matching, Information Processing Letters, 83(1):33-39, 2002.
  11. A. Amir, R. Cole, R. Hariharan, M. Lewenstein and E. Porat, Overlap Matching, Information and Computation, 181(1):57-74, 2003.
  12. M. Lewenstein and M. Sviridenko, A 5/8 Approximation Algorithm for the Asymmetric Maximum TSP, SIAM J. on Discrete Math, 17(2):237-248, 2003.
  13. A. Amir, M. Lewenstein and E. Porat, Faster Algorithms for String Matching with k Mismatches, J. of Algorithms, 50(2):257-275, 2004. (Special issue of SODA 2000.)
  14. D. Gamarnik, M. Lewenstein and M. Sviridenko, An Improved Upper Bound for TSP in Cubic 3-Connected Graphs, Operations Research Letters, 33(5):467-474, 2005.
  15. H. Kaplan, M. Lewenstein, N. Shafrir and M. Sviridenko, Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs, J. of the ACM, 52(4):602-626, 2005.
  16. D. Coppersmith and M. Lewenstein, Constructive Bounds on Ordered Factorizations, SIAM J. on Discrete Math, 19(2):301-303, 2006.
  17. A. Amir, A. Aumann, M. Lewenstein and E. Porat, Function Matching, SIAM J. on Computing, 35(5):1007-1022, 2006.
  18. A. Apostolico, P. Erdos and M. Lewenstein, Parameterized Matching with Mismatches, Journal on Discrete Algorithms, 5(1):135-140, 2007.
  19. A. Amir, A. Butman, M. Lewenstein, E. Porat and D. Tsur, One Dimensional Real Scaled Matching, Journal on Discrete Algorithms, 5(2):205-211, 2007.
  20. C. Hazay, M. Lewenstein and D. Sokol, Approximate Parameterized Matching, ACM Trans. of Algorithms, 3(3), 2007.
  21. A. Amir, G. Landau, M. Lewenstein and D. Sokol, Static Pattern and Dynamic Text Pattern Matching, ACM Trans. of Algorithms, 3(2), 2007.
  22. A. Amir, A. Butman, M. Lewenstein and E. Porat, Real Two Dimensional Scaled Matching, Algorithmica, 53(3):314-336, 2009.
  23. O. Keller, T. Kopelowitz, and M. Lewenstein, On the longest common parameterized subsequence, Theor. Comput. Sci. 410(51):5347-5353, 2009.
  24. Z. Gotthilf and M. Lewenstein, Improved algorithms for the k simple shortest paths and the replacement paths problems, Inf. Process. Lett., 109(7):352-355, 2009.
  25. N. Bansal, M. Lewenstein, B. Ma and K. Zhang, On the Longest Common Rigid Subsequence Problem, Algorithmica, 86(2), 270-280, 2010.
  26. A. Butman and D. Hermelin and M. Lewenstein and D. Rawitz, Optimization problems in multiple-interval graphs, ACM Trans. of Algorithms, 6(2):2010.
  27. Y. Aumann, M. Lewenstein, N. Lewenstein and D. Tsur, Finding Witnesses by Peeling, ACM Trans. of Algorithms, 7(2):2011.
  28. Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter and Z. Yakhini, Dotted Interval Graphs, ACM Transactions on Algorithms, 8(2): 9, 2012.
  29. C. Kent, M. Lewenstein and D. Sheinwald, On Demand Sorting over Unbounded Alphabets, Theoretical Computer Science (TCS), 426:66-74, 2012.
  30. H. Bannai, T. Gagie, Tomohiro I, S. Inenaga, G.M. Landau, M. Lewenstein. An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Straight-Line Programs, Information Processing Letters, 112(19):711-714, 2012.
  31. O. Keller, T. Kopelowitz, S. Landau and M. Lewenstein, Generalized Substring Compression, Theoretical Computer Science, 525:42-54, 2014.
  32. R. Cole, C. Hazay, M. Lewenstein and D. Tsur, Two Dimensional Parameterized Matching, ACM Transactions on Algorithms, 11(2):12, 2014.
  33. A. Amir, G. Franceschini, R. Grossi, T. Kopelowitz, M. Lewenstein and N. Lewenstein, Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing, SIAM Journal on Computing, 43(4):1396-1416, 2014.
  34. I. Goldstein and M. Lewenstein, Quick Greedy Computation for Minimum Common String Partitions, Theoretical Computer Science, 542:98-107, 2014.
  35. A. Amir, A. Apostolico, G.M. Landau, A. Levy, M. Lewenstein and E. Porat, Range LCP, Journal of Computer and System Sciences, 80(7):1245-1253, 2014.
  36. M. Lewenstein, J. Ian Munro, V. Raman, S.V. Thankachan, Less Space: Indexing for queries with Wildcards, Theoretical Computer Science, 557:120-127, 2014.
  37. R. Cole, T. Kopelowitz and M. Lewenstein, Suffix Trays and Suffix Trists: Structures for Faster Text Indexing, Algorithmica, 72(2):450-466, 2015.
  38. G.S. Brodal, P. Davoodi, M. Lewenstein, R. Raman, S. Srinivasa Rao. Two Dimensional Range Minimum Queries and Fibonacci Lattices. Theoretical Computer Science,

638: 33-43, 2016.

  1. M. Lewenstein, J.I. Munro, Y. Nekrich, S.V. Thankachan. Document Retrieval with One Wildcard. Theoretical Computer Science, 635:94-101, 2016.
  2. T.M. Chan, H. El-Zein, M. Lewenstein, J.I. Munro, V. Raman. Algorithmica, 78(3): 1020-1040, 2017.
  3. A. Amir, A. Levy, M. Lewenstein, R. Lubin, B. Porat. Can We Recover the Cover? Algorithmica, 81(7):2857-2875, 2019.

 

    

Refereed papers in conference proceedings

 

  1. A. Amir, N. Lewenstein and M. Lewenstein, Pattern Matching in Hypertext, Proceedings, 5th Workshop on Algorithms and Data Structures (WADS), Halifax, Canada, August 1997, pp. 160-173.
  2. 2. A. Amir, Y. Aumann, G. Landau, N. Lewenstein and M. Lewenstein, Pattern Matching with Swaps, Proceedings, 39th Conference on Foundations of Computer Science (FOCS), Miami, Florida, October 1997, 148-153.
  3. A. Amir, G. Landau, M. Lewenstein and N. Lewenstein, Efficient Special Cases of Pattern Matching with Swaps, Proceedings, 8th Annual Symposium on Combinatorial Pattern Matching (CPM), New Jersey, USA, July 1998, 209-220.
  4. A. Amir, D. Kesselman, G. Landau, M. Lewenstein, N. Lewenstein and M. Rodeh, Indexing and Dictionary Matching with One Error, Proceedings of the Workshop of Algorithms and Data Structures (WADS), Vancouver, Canada, August 1999, 181-192.
  5. A. Amir, M. Lewenstein and E. Porat, Faster Algorithms for String Matching with k Mismatches, Proceedings of the Symposium of Discrete Algorithms (SODA), San Francisco, 2000, 794-803.
  6. A. Amir, A. Butman and M. Lewenstein, Real Scaled Matching, Proceedings of the Symposium of Discrete Algorithms (SODA), San Francisco, 2000, 815-816.
  7. A. Amir, R. Cole, R. Hariharan, M. Lewenstein, and E. Porat, Overlap Matching, Proceedings of Symposium of Discrete Algorithms (SODA), Washington DC, 2001, 279-288.
  8. A. Amir, M. Lewenstein and E. Porat, Approximate Subset Matching with Don't Cares, Proceedings of Symposium of Discrete Algorithms (SODA), Washington DC, 2001, 305-306.
  9. R. Cole, R. Hariharan, M. Lewenstein, and E. Porat, A Faster Implementation of the Goemans-Williamson Clustering Algorithm, Proceedings of Symposium of Discrete Algorithms (SODA), Washington DC, 2001, 17-25.
  10. A. Amir, M. Lewenstein and E. Porat, Approximate Swapped Matching, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), New Delhi, India, 2000, 302-311.
  11. R. Cole and M. Lewenstein, Multidimensional Matching and Fast Search in Suffix Trees. Proc. of Symposium on Discrete Algorithms (SODA), 2003, 851-852.
  12. M. Lewenstein and M. Sviridenko, A 5/8 Approximation Algorithm for the Asymmetric Maximum TSP. Proc. of Symposium on Discrete Algorithms (SODA), 2003, 646-654.
  13. A. Amir, A. Aumann, R. Cole, M. Lewenstein and E. Porat, Function Matching: Algorithms, Applications and a Lower Bound. Proc. of International Colloquium on Automata, Languages and Programming (ICALP), 2003, 929-942.
  14. A. Amir, A. Butman, M. Lewenstein and E. Porat, Two Dimensional Scaled Matching. Proc. of Workshop on Algorithms and Data Structures (WADS), 2003, 353-364.
  15. A. Amir, G. Landau, M. Lewenstein and D. Sokol, Static Pattern and Dynamic Text Pattern Matching. Proc. of Workshop on Algorithms and Data Structures (WADS), 2003, 340-352.
  16.  H. Kaplan, M. Lewenstein, N. Shafrir and M. Sviridenko, A 2/3 Approximation for Maximum Asymmetric TSP by Decomposing Directed Regular Multigraphs. Proc. of Symposium on Foundations of Computer Science (FOCS), 2003, 56-65.
  17. R. Cole, L. Gottlieb and M. Lewenstein, Indexing and Dictionary Matching with k mismatches, Proc. of Symposium on the Theory of Computing (STOC), 2004, 91-100.
  18. P. Indyk, O. Lipsky, M. Lewenstein, and E. Porat, Closest Pair in Very High Dimensions. Proc. of International Colloquium on Automata, Languages and Programming (ICALP), 2004, 782-792.
  19. C. Hazay, M. Lewenstein and D. Sokol, Approximate Parameterized Matching. Proc. Of European Symposium on Algorithms (ESA), 2004, 414-425.
  20. A. Amir, A. Butman, M. Lewenstein, E. Porat and D. Tsur, One Dimensional Real Scaled Matching, Proc. of String Processing and Information Retrieval (SPIRE), 2004, 1-9.
  21. Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter and Z. Yakhini, Dotted Interval Graphs, Proc. of Symposium on Discrete Algorithms (SODA), 2005, 339-348.
  22. C. Hazay, M. Lewenstein and D. Tsur, Two Dimensional Parameterized Matching, Proc. Of Combinatorial Pattern Matching (CPM), 2005, 266-279.
  23. A. Amir, T. Kopelowitz, M. Lewenstein and N. Lewenstein, Towards Real Time Indexing, Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2005, 67-78.
  24. Z. Gothilf and M. Lewenstein, Faster Greedy Approximations for Maximum Induced Matchings in Regular Graphs, Proc. of Workshop on Approximation and Online Algorithms (WAOA), 2005, 270-281.
  25. R. Cole, T. Kopelowitz and M. Lewenstein, Suffix Trays and Suffix Trists: Structures for Faster Text Indexing, Proc. of International Colloquium on Automata, Languages and Programming (ICALP), 2006, 358-369.
  26. A. Butman and D. Hermelin and M. Lewenstein and D. Rawitz, Optimization problems in multiple-interval graphs, Proc. of Symposium on Discrete Algorithms (SODA), 2007, 268-277.
  27. T. Kopelowitz and M. Lewenstein, Dynamic Weighted Ancestors, Proc. of Symposium on Discrete Algorithms (SODA), 2007, 565-574.
  28. C. Kent, M. Lewenstein and D. Sheinwald, On Demand Sorting over Unbounded Alphabets, Proc. of Combinatorial Pattern Matching (CPM), 2007, 16-27.
  29. Y. Aumann, M. Lewenstein, N. Lewenstein, D. Tsur, Finding Witnesses by Peeling, Proc. Of Combinatorial Pattern Matching (CPM), 2007, 28-39.
  30. A. Amir, J. Fischer and M. Lewenstein, Two-Dimensional Minimum Range Queries, Proc. Of Combinatorial Pattern Matching (CPM), 2007, 286-294.
  31. O. Keller, T. Kopelowitz and M. Lewenstein, Range Non-overlapping Indexing and Successive List Indexing, Workshop on Algorithms and Data Structures (WADS), 2007, 625-636.
  32. Z. Gotthilf and M. Lewenstein, Approximating Constrained LCS, Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2007, 164-172.
  33. Z. Gotthilf, D. Hermelin and M. Lewenstein, Constrained LCS: Hardness and Approximation, Combinatorial Pattern Matching (CPM), 2008, 255-262.
  34. O. Keller, T. Kopelowitz and M. Lewenstein, On the Longest Common Parameterized Subsequence, Combinatorial Pattern Matching (CPM), 2008, 303-315.
  35. Z. Gotthilf, M. Lewenstein and E. Rainshmidt, A (2􀀀c log n n ) Approximation Algorithm for the Minimum Maximal Matching Problem, Proc. of Workshop on Approximation and Online Algorithms (WAOA), 2008, 267-278.
  36. O. Keller, T. Kopelowitz, S. Landau and M. Lewenstein, Generalized Substring Compression, Proc. of Symposium on Combinatorial Pattern Matching (CPM), 2009, 26-38.
  37. Z. Gotthilf, M. Lewenstein: Improved Approximation Results on the Shortest Common Supersequence Problem. Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2009, 277-284.
  38. Z. Gotthilf, M. Lewenstein, A. Popa: On Shortest Common Superstring and Swap Permutations, Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2010, 270-278.
  39. Z. Gotthilf, D. Hermelin, G.M. Landau, M. Lewenstein: Restricted LCS, Proc. of Symposium on String Processing and Information Retrieval (SPIRE), 2010, 250-257.
  40. Y. Bartal, L. Gottlieb, T. Kopelowitz, M. Lewenstein and L. Roditty, Fast, precise and dynamic distance queries, Proc. of Symposium on Discrete Algorithms (SODA), 2011, 840-853.
  41. I. Goldstein and M. Lewenstein, Quick Greedy Computation for Minimum Common String Partitions, Proc. of Symposium on Combinatorial Pattern Matching (CPM), 2011, 273-284.
  42. R. Clifford, Z. Gotthilf, M. Lewenstein and A. Popa, Restricted Common Superstring and Restricted Common Supersequence, Proc. of Symposium on Combinatorial Pattern Matching (CPM), 2011, 467-478.
  43. T. Kopelowitz, M. Lewenstein and E. Porat, Persistency in Suffix Trees with Applications to String Interval Problems, Proc. of String Processing and Information Retrieval (SPIRE), 2011, 67-80.
  44. M. Lewenstein, Indexing with Gaps, Proc. of Workshop on String Processing and Information Retrieval (SPIRE), 2011, 135-143.
  45. A. Amir, A. Apostolico, G.M. Landau, A. Levy, M. Lewenstein and E. Porat, Range LCP, Proc. of the International Symposium on Algorithms and Computation (ISAAC), 2011, 683-692.
  46. J. Fischer, T. Gagie, T. Kopelowitz, M. Lewenstein, V. Makinen, L. Salmela, and N. Valimaki, Forbidden Patterns, Proc. of Latin American Theoretical INformatics Symposium (LATIN), 2012.
  47. G.S. Brodal, P. Davoodi, M. Lewenstein, R. Raman, S. Srinivasa Rao. Two Dimensional Range Minimum Queries and Fibonacci Lattices. ESA 2012, 217-228.
  48. L.K. Lee, M. Lewenstein, Q. Zhang: Parikh Matching in the Streaming Model. SPIRE 2012, 336-341.
  49. A. Hasidim, O. Keller, M. Lewenstein and L. Roditty, Proc. of Workshop on Algorithms and Data Structures (WADS) 2013, 390-401.
  50. M. Lewenstein, I. Munro, V. Raman and S. Thankachan.  Less Space: Indexing for Queries with Wildcards. Proc. of International Symposium on Algorithms and Computation (ISAAC) 2013: 89-99.
  51. M. Lewenstein,  I. Munro and V. Raman. Succinct Data Structures for Representing Equivalence Classes. Proc. of International Symposium on Algorithms and Computation (ISAAC) 2013: 502-512.
  52. M. Lewenstein, Orthogonal Range Searching for Text Indexing, Proc. of Space Efficient Data Structures, Streams and Algorithms, 2013, 267-302.
  53. M. Lewenstein, Y. Nekrich and J. Vitter. Space-Efficient String Indexing for Wildcard Pattern Matching, STACS 2014, 506-517.
  54. P. Gawrychowski, M. Lewenstein, P. Nicholson. Weighted Ancestors in Suffix Trees, ESA 2014, 455-466.
  55. M. Lewenstein, I. Munro, P. Nicholson, and V. Raman. Improved Explicit Data Structures in the Bitprobe Model, ESA 2014, 630-641.
  56. A. Amir, T. Chan, M. Lewenstein, and N. Lewenstein. On the Hardness of Jumbled Indexing, ICALP 2014, 114-125.
  57. Moshe Lewenstein, J.I. Munro, Y. Nekrich, S.V. Thankachan. Document Retrieval with One Wildcard. MFCS (2) 2014, 529-540.
  58. T. Chan and M. Lewenstein. Clustered Integer 3SUM via Additive Combinatorics, STOC 2015, 31-40.
  59. P. Bille, I. Gortz, M.B.T. Knudsen, M. Lewenstein, H. Vildhoj, Longest Common Extension: Tight Space-Time Tradeoffs.  CPM 2015, 65-76.
  60. P. Davoodi, G.M. Landau and M. Lewenstein, Range Minimum Query Indexes in Higher Dimensions, CPM 2015, 149-159.
  61. T. Chan and M. Lewenstein, Fast String Dictionary Lookup with One Error, CPM 2015, 114-123.
  62. A. Amir, M. Lewenstein, S.V. Thankachan. Range LCP Queries Revisited, SPIRE 2015: 350-361.
  63. J. Fischer, S. Holub, Tomohiro I, M. Lewenstein. Beyond the Runs Theorem. SPIRE 2015: 277-286.
  64. I. Goldstein, T. Kopelowitz, M. Lewenstein and E. Porat, How Hard is it to Find Honest Witnesses?, ESA 2016: 45:1-16.
  65. A. Amir, A. Levy, M. Lewenstein, R. Lubin, B. Porat. Can We Recover the Cover? CPM 2017: 25:1-25:15.
  66. I. Goldstein, M. Lewenstein, E. Porat. Orthongonal Vector Indexing. ISAAC 2017: 40:1-40:12.
  67. I. Goldstein, T. Kopelowitz, M. Lewenstein, E. Porat. Conditional Lower Bounds for Space/Time Tradeoffs. WADS 2017: 421-436.
  68. I. Goldstein, M. Lewenstein, E. Porat. Improved Space-Time Tradeoffs for kSUM. ESA 2018: 37:1-14.
  69. I. Goldstein, M. Lewenstein, E. Porat. On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. ISAAC 2019: 7:1-7:22.

 

Surveys

 

  1. M. Lewenstein, Dictionary Matching and Indexing (Exact and with Errors). Encyclopedia of Algorithms, 2008.
  2. M. Lewenstein, Parameterized Matching. Encyclopedia of Algorithms, 2008.
  3. A. Amir, M. Lewenstein, N. Lewenstein: Hypertext Searching - A Survey. Language, Culture, Computation (1) 2014, 364-381.