LIPIcs, Volume 229
ICALP 2022, July 4-8, 2022, Paris, France
Editors: Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Morteza Monemizadeh. Facility Location in the Sublinear Geometric Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 6:1-6:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{monemizadeh:LIPIcs.APPROX/RANDOM.2023.6, author = {Monemizadeh, Morteza}, title = {{Facility Location in the Sublinear Geometric Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {6:1--6:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.6}, URN = {urn:nbn:de:0030-drops-188315}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.6}, annote = {Keywords: Facility Location, Sublinear Geometric Model, Range Counting Queries} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8, author = {Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim}, title = {{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {8:1--8:18}, 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.8}, URN = {urn:nbn:de:0030-drops-183585}, doi = {10.4230/LIPIcs.SEA.2023.8}, annote = {Keywords: sorting, algorithms, randomization, experimentation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, and Shufan Zhang. Recovery from Non-Decomposable Distance Oracles. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 73:1-73:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hu_et_al:LIPIcs.ITCS.2023.73, author = {Hu, Zhuangfei and Li, Xinda and Woodruff, David P. and Zhang, Hongyang and Zhang, Shufan}, title = {{Recovery from Non-Decomposable Distance Oracles}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {73:1--73: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.73}, URN = {urn:nbn:de:0030-drops-175767}, doi = {10.4230/LIPIcs.ITCS.2023.73}, annote = {Keywords: Sequence Recovery, Edit Distance, DTW Distance, Fr\'{e}chet Distance} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Yi Li, Honghao Lin, David P. Woodruff, and Yuheng Zhang. Streaming Algorithms with Large Approximation Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 13:1-13:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2022.13, author = {Li, Yi and Lin, Honghao and Woodruff, David P. and Zhang, Yuheng}, title = {{Streaming Algorithms with Large Approximation Factors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {13:1--13: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.13}, URN = {urn:nbn:de:0030-drops-171354}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.13}, annote = {Keywords: streaming algorithms, 𝓁\underlinep norm, heavy hitters, distinct elements} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Sepideh Mahabadi, David P. Woodruff, and Samson Zhou. Adaptive Sketches for Robust Regression with Importance Sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 31:1-31:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{mahabadi_et_al:LIPIcs.APPROX/RANDOM.2022.31, author = {Mahabadi, Sepideh and Woodruff, David P. and Zhou, Samson}, title = {{Adaptive Sketches for Robust Regression with Importance Sampling}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {31:1--31:21}, 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.31}, URN = {urn:nbn:de:0030-drops-171531}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.31}, annote = {Keywords: Streaming algorithms, stochastic optimization, importance sampling} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff. LIPIcs, Volume 229, ICALP 2022, Complete Volume. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 1-2516, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Proceedings{bojanczyk_et_al:LIPIcs.ICALP.2022, title = {{LIPIcs, Volume 229, ICALP 2022, Complete Volume}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {1--2516}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022}, URN = {urn:nbn:de:0030-drops-163400}, doi = {10.4230/LIPIcs.ICALP.2022}, annote = {Keywords: LIPIcs, Volume 229, ICALP 2022, Complete Volume} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff. Front Matter, Table of Contents, Preface, Conference Organization. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 0:i-0:xxxvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2022.0, author = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {0:i--0:xxxvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.0}, URN = {urn:nbn:de:0030-drops-163417}, doi = {10.4230/LIPIcs.ICALP.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Albert Atserias. Towards a Theory of Algorithmic Proof Complexity (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 1:1-1:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{atserias:LIPIcs.ICALP.2022.1, author = {Atserias, Albert}, title = {{Towards a Theory of Algorithmic Proof Complexity}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {1:1--1:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.1}, URN = {urn:nbn:de:0030-drops-163423}, doi = {10.4230/LIPIcs.ICALP.2022.1}, annote = {Keywords: proof complexity, logic, computational complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Constantinos Daskalakis. Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{daskalakis:LIPIcs.ICALP.2022.2, author = {Daskalakis, Constantinos}, title = {{Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.2}, URN = {urn:nbn:de:0030-drops-163431}, doi = {10.4230/LIPIcs.ICALP.2022.2}, annote = {Keywords: Deep Learning, Multi-Agent (Reinforcement) Learning, Game Theory, Nonconvex Optimization, PPAD} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Leslie Ann Goldberg. Some New (And Old) Results on Contention Resolution (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 3:1-3:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{goldberg:LIPIcs.ICALP.2022.3, author = {Goldberg, Leslie Ann}, title = {{Some New (And Old) Results on Contention Resolution}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {3:1--3:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.3}, URN = {urn:nbn:de:0030-drops-163444}, doi = {10.4230/LIPIcs.ICALP.2022.3}, annote = {Keywords: contention resolution, multiple access channel, randomised algorithms} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Yin Tat Lee and Santosh S. Vempala. The Manifold Joys of Sampling (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 4:1-4:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{lee_et_al:LIPIcs.ICALP.2022.4, author = {Lee, Yin Tat and Vempala, Santosh S.}, title = {{The Manifold Joys of Sampling}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {4:1--4:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.4}, URN = {urn:nbn:de:0030-drops-163459}, doi = {10.4230/LIPIcs.ICALP.2022.4}, annote = {Keywords: Sampling, Diffusion, Optimization, High Dimension} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Madhu Sudan. Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{sudan:LIPIcs.ICALP.2022.5, author = {Sudan, Madhu}, title = {{Streaming and Sketching Complexity of CSPs: A Survey}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.5}, URN = {urn:nbn:de:0030-drops-163460}, doi = {10.4230/LIPIcs.ICALP.2022.5}, annote = {Keywords: Streaming algorithms, Sketching algorithms, Dichotomy, Communication Complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Stéphan Thomassé. A Brief Tour in Twin-Width (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 6:1-6:5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{thomasse:LIPIcs.ICALP.2022.6, author = {Thomass\'{e}, St\'{e}phan}, title = {{A Brief Tour in Twin-Width}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {6:1--6:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.6}, URN = {urn:nbn:de:0030-drops-163473}, doi = {10.4230/LIPIcs.ICALP.2022.6}, annote = {Keywords: Twin-width, matrices, ordered graphs, enumerative combinatorics, model theory, algorithms, computational complexity, Ramsey theory} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi. Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2022.7, author = {Abboud, Amir and Cohen-Addad, Vincent and Lee, Euiwoong and Manurangsi, Pasin}, title = {{Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.7}, URN = {urn:nbn:de:0030-drops-163481}, doi = {10.4230/LIPIcs.ICALP.2022.7}, annote = {Keywords: Approximation Algorithms, Complexity, Data Mining, Diversification} }
Feedback for Dagstuhl Publishing