Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Alexandr Andoni, Jarosław Błasiok, and Arnold Filtser. Communication Complexity of Inner Product in Symmetric Normed Spaces. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 4:1-4:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{andoni_et_al:LIPIcs.ITCS.2023.4, author = {Andoni, Alexandr and B{\l}asiok, Jaros{\l}aw and Filtser, Arnold}, title = {{Communication Complexity of Inner Product in Symmetric Normed Spaces}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {4:1--4:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.4}, URN = {urn:nbn:de:0030-drops-175077}, doi = {10.4230/LIPIcs.ITCS.2023.4}, annote = {Keywords: communication complexity, symmetric norms} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Louis Esperet, Nathaniel Harms, and Andrey Kupavskii. Sketching Distances in Monotone Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 18:1-18:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{esperet_et_al:LIPIcs.APPROX/RANDOM.2022.18, author = {Esperet, Louis and Harms, Nathaniel and Kupavskii, Andrey}, title = {{Sketching Distances in Monotone Graph Classes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {18:1--18:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.18}, URN = {urn:nbn:de:0030-drops-171406}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.18}, annote = {Keywords: adjacency labelling, informative labelling, distance sketching, adjacency sketching, communication complexity} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, and David P. Woodruff. Streaming Complexity of SVMs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 50:1-50:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{andoni_et_al:LIPIcs.APPROX/RANDOM.2020.50, author = {Andoni, Alexandr and Burns, Collin and Li, Yi and Mahabadi, Sepideh and Woodruff, David P.}, title = {{Streaming Complexity of SVMs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {50:1--50:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.50}, URN = {urn:nbn:de:0030-drops-126532}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.50}, annote = {Keywords: support vector machine, streaming algorithm, space lower bound, sketching algorithm, point estimation} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Arnold Filtser. Scattering and Sparse Partitions, and Their Applications. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 47:1-47:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{filtser:LIPIcs.ICALP.2020.47, author = {Filtser, Arnold}, title = {{Scattering and Sparse Partitions, and Their Applications}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {47:1--47:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.47}, URN = {urn:nbn:de:0030-drops-124547}, doi = {10.4230/LIPIcs.ICALP.2020.47}, annote = {Keywords: Scattering partitions, sparse partitions, sparse covers, Steiner point removal, Universal Steiner tree, Universal TSP} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 14:1-14:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{andoni_et_al:LIPIcs.ICALP.2019.14, author = {Andoni, Alexandr and Stein, Clifford and Zhong, Peilin}, title = {{Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.14}, URN = {urn:nbn:de:0030-drops-105906}, doi = {10.4230/LIPIcs.ICALP.2019.14}, annote = {Keywords: parallel algorithms, biconnectivity, 2-edge connectivity, the MPC model} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alexandr Andoni, Tal Malkin, and Negev Shekel Nosatzki. Two Party Distribution Testing: Communication and Security. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{andoni_et_al:LIPIcs.ICALP.2019.15, author = {Andoni, Alexandr and Malkin, Tal and Nosatzki, Negev Shekel}, title = {{Two Party Distribution Testing: Communication and Security}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {15:1--15:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.15}, URN = {urn:nbn:de:0030-drops-105916}, doi = {10.4230/LIPIcs.ICALP.2019.15}, annote = {Keywords: distribution testing, communication complexity, security} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow. On Solving Linear Systems in Sublinear Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 3:1-3:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{andoni_et_al:LIPIcs.ITCS.2019.3, author = {Andoni, Alexandr and Krauthgamer, Robert and Pogrow, Yosef}, title = {{On Solving Linear Systems in Sublinear Time}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.3}, URN = {urn:nbn:de:0030-drops-100966}, doi = {10.4230/LIPIcs.ITCS.2019.3}, annote = {Keywords: Linear systems, Laplacian solver, Sublinear time, Randomized linear algebra} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Alexandr Andoni, Assaf Naor, and Ofer Neiman. Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 83:1-83:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{andoni_et_al:LIPIcs.ICALP.2016.83, author = {Andoni, Alexandr and Naor, Assaf and Neiman, Ofer}, title = {{Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {83:1--83:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.83}, URN = {urn:nbn:de:0030-drops-62028}, doi = {10.4230/LIPIcs.ICALP.2016.83}, annote = {Keywords: Transportation metric, embedding, snowflake, sketching} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Alexandr Andoni and Ilya Razensteyn. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 9:1-9:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{andoni_et_al:LIPIcs.SoCG.2016.9, author = {Andoni, Alexandr and Razensteyn, Ilya}, title = {{Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {9:1--9:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.9}, URN = {urn:nbn:de:0030-drops-59014}, doi = {10.4230/LIPIcs.SoCG.2016.9}, annote = {Keywords: similarity search, high-dimensional geometry, LSH, data structures, lower bounds} }
Feedback for Dagstuhl Publishing