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 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} }