LIPIcs, Volume 54
CPM 2016, June 27-29, 2016, Tel Aviv, Israel
Editors: Roberto Grossi and Moshe Lewenstein
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Jarno N. Alanko, Elena Biagi, Simon J. Puglisi, and Jaakko Vuohtoniemi. Subset Wavelet Trees. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 4:1-4:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{alanko_et_al:LIPIcs.SEA.2023.4, author = {Alanko, Jarno N. and Biagi, Elena and Puglisi, Simon J. and Vuohtoniemi, Jaakko}, title = {{Subset Wavelet Trees}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.4}, URN = {urn:nbn:de:0030-drops-183549}, doi = {10.4230/LIPIcs.SEA.2023.4}, annote = {Keywords: degenerate strings, compressed data structures, succinct data structures, string processing, data structures, efficient algorithms} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Matan Kraus, Moshe Lewenstein, Alexandru Popa, Ely Porat, and Yonathan Sadia. String Factorization via Prefix Free Families. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 19:1-19:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kraus_et_al:LIPIcs.CPM.2023.19, author = {Kraus, Matan and Lewenstein, Moshe and Popa, Alexandru and Porat, Ely and Sadia, Yonathan}, title = {{String Factorization via Prefix Free Families}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {19:1--19:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.19}, URN = {urn:nbn:de:0030-drops-179738}, doi = {10.4230/LIPIcs.CPM.2023.19}, annote = {Keywords: string factorization, NP-hard problem, approximation algorithm} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Isaac Goldstein, Moshe Lewenstein, and Ely Porat. On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 7:1-7:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{goldstein_et_al:LIPIcs.ISAAC.2019.7, author = {Goldstein, Isaac and Lewenstein, Moshe and Porat, Ely}, title = {{On the Hardness of Set Disjointness and Set Intersection with Bounded Universe}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {7:1--7:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.7}, URN = {urn:nbn:de:0030-drops-115036}, doi = {10.4230/LIPIcs.ISAAC.2019.7}, annote = {Keywords: set disjointness, set intersection, 3SUM, space-time tradeoff, conditional lower bounds} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Isaac Goldstein, Moshe Lewenstein, and Ely Porat. Improved Space-Time Tradeoffs for kSUM. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 37:1-37:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{goldstein_et_al:LIPIcs.ESA.2018.37, author = {Goldstein, Isaac and Lewenstein, Moshe and Porat, Ely}, title = {{Improved Space-Time Tradeoffs for kSUM}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {37:1--37:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.37}, URN = {urn:nbn:de:0030-drops-95000}, doi = {10.4230/LIPIcs.ESA.2018.37}, annote = {Keywords: kSUM, space-time tradeoff, self-reduction} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Isaac Goldstein, Moshe Lewenstein, and Ely Porat. Orthogonal Vectors Indexing. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 40:1-40:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{goldstein_et_al:LIPIcs.ISAAC.2017.40, author = {Goldstein, Isaac and Lewenstein, Moshe and Porat, Ely}, title = {{Orthogonal Vectors Indexing}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {40:1--40:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.40}, URN = {urn:nbn:de:0030-drops-82395}, doi = {10.4230/LIPIcs.ISAAC.2017.40}, annote = {Keywords: SETH, orthogonal vectors, space complexity} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, and Benny Porat. Can We Recover the Cover?. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 25:1-25:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{amir_et_al:LIPIcs.CPM.2017.25, author = {Amir, Amihood and Levy, Avivit and Lewenstein, Moshe and Lubin, Ronit and Porat, Benny}, title = {{Can We Recover the Cover?}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.25}, URN = {urn:nbn:de:0030-drops-73190}, doi = {10.4230/LIPIcs.CPM.2017.25}, annote = {Keywords: periodicity, quasi-periodicity, cover, approximate cover, data recovery} }
Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)
Moshe Lewenstein, Seth Pettie, and Virginia Vassilevska Williams. Structure and Hardness in P (Dagstuhl Seminar 16451). In Dagstuhl Reports, Volume 6, Issue 11, pp. 1-34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@Article{lewenstein_et_al:DagRep.6.11.1, author = {Lewenstein, Moshe and Pettie, Seth and Vassilevska Williams, Virginia}, title = {{Structure and Hardness in P (Dagstuhl Seminar 16451)}}, pages = {1--34}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {11}, editor = {Lewenstein, Moshe and Pettie, Seth and Vassilevska Williams, Virginia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.11.1}, URN = {urn:nbn:de:0030-drops-70373}, doi = {10.4230/DagRep.6.11.1}, annote = {Keywords: Algorithmic equivalences, Classifying P, Hardness assumptions, Lower bounds} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. How Hard is it to Find (Honest) Witnesses?. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 45:1-45:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{goldstein_et_al:LIPIcs.ESA.2016.45, author = {Goldstein, Isaac and Kopelowitz, Tsvi and Lewenstein, Moshe and Porat, Ely}, title = {{How Hard is it to Find (Honest) Witnesses?}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.45}, URN = {urn:nbn:de:0030-drops-63575}, doi = {10.4230/LIPIcs.ESA.2016.45}, annote = {Keywords: 3SUM, convolutions, matrix multiplication, histogram indexing} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Roberto Grossi and Moshe Lewenstein. LIPIcs, Volume 54, CPM'16, Complete Volume. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@Proceedings{grossi_et_al:LIPIcs.CPM.2016, title = {{LIPIcs, Volume 54, CPM'16, Complete Volume}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016}, URN = {urn:nbn:de:0030-drops-60935}, doi = {10.4230/LIPIcs.CPM.2016}, annote = {Keywords: Data Structures, Data Storage Representations, Coding and Information Theory, Theory of Computation Discrete Mathematics, Information Systems} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Roberto Grossi and Moshe Lewenstein. Front Matter, Table of Contents, Preface. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 0:i-0:x, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{grossi_et_al:LIPIcs.CPM.2016.0, author = {Grossi, Roberto and Lewenstein, Moshe}, title = {{Front Matter, Table of Contents, Preface}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {0:i--0:x}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.0}, URN = {urn:nbn:de:0030-drops-60916}, doi = {10.4230/LIPIcs.CPM.2016.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, List of Authors} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, and Masayuki Takeda. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 1:1-1:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{tanimura_et_al:LIPIcs.CPM.2016.1, author = {Tanimura, Yuka and I, Tomohiro and Bannai, Hideo and Inenaga, Shunsuke and Puglisi, Simon J. and Takeda, Masayuki}, title = {{Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {1:1--1:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.1}, URN = {urn:nbn:de:0030-drops-60655}, doi = {10.4230/LIPIcs.CPM.2016.1}, annote = {Keywords: longest common extension, longest common prefix, sparse suffix array} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Arnab Ganguly, Wing-Kai Hon, Kunihiko Sadakane, Rahul Shah, Sharma V. Thankachan, and Yilin Yang. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 2:1-2:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{ganguly_et_al:LIPIcs.CPM.2016.2, author = {Ganguly, Arnab and Hon, Wing-Kai and Sadakane, Kunihiko and Shah, Rahul and Thankachan, Sharma V. and Yang, Yilin}, title = {{Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {2:1--2:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.2}, URN = {urn:nbn:de:0030-drops-60736}, doi = {10.4230/LIPIcs.CPM.2016.2}, annote = {Keywords: Parameterized Matching, Order-preserving Matching, Dictionary Indexing, Aho-Corasick Automaton, Sparsification} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Seungbum Jo, Rahul Lingala, and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 3:1-3:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{jo_et_al:LIPIcs.CPM.2016.3, author = {Jo, Seungbum and Lingala, Rahul and Satti, Srinivasa Rao}, title = {{Encoding Two-Dimensional Range Top-k Queries}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {3:1--3:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.3}, URN = {urn:nbn:de:0030-drops-60704}, doi = {10.4230/LIPIcs.CPM.2016.3}, annote = {Keywords: Encoding model, top-k query, range minimum query} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Carl Barton, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Efficient Index for Weighted Sequences. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 4:1-4:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{barton_et_al:LIPIcs.CPM.2016.4, author = {Barton, Carl and Kociumaka, Tomasz and Pissis, Solon P. and Radoszewski, Jakub}, title = {{Efficient Index for Weighted Sequences}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {4:1--4:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.4}, URN = {urn:nbn:de:0030-drops-60807}, doi = {10.4230/LIPIcs.CPM.2016.4}, annote = {Keywords: weighted sequence, position weight matrix, indexing, weighted suffix tree} }
Feedback for Dagstuhl Publishing