LIPIcs, Volume 163
ITC 2020, June 17-19, 2020, Boston, MA, USA
Editors: Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., and Saeed Seddighin. On Complexity of 1-Center in Various Metrics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abboud_et_al:LIPIcs.APPROX/RANDOM.2023.1, author = {Abboud, Amir and Bateni, MohammadHossein and Cohen-Addad, Vincent and Karthik C. S. and Seddighin, Saeed}, title = {{On Complexity of 1-Center in Various Metrics}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {1:1--1:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.1}, URN = {urn:nbn:de:0030-drops-188260}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.1}, annote = {Keywords: Center, Clustering, Edit metric, Ulam metric, Hamming metric, Fine-grained Complexity, Approximation} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Lap Chi Lau, Robert Wang, and Hong Zhou. Experimental Design for Any p-Norm. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lau_et_al:LIPIcs.APPROX/RANDOM.2023.4, author = {Lau, Lap Chi and Wang, Robert and Zhou, Hong}, title = {{Experimental Design for Any p-Norm}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {4:1--4:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.4}, URN = {urn:nbn:de:0030-drops-188292}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.4}, annote = {Keywords: Approximation Algorithm, Optimal Experimental Design, Randomized Local Search} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Tanvi Bajpai and Chandra Chekuri. Bicriteria Approximation Algorithms for Priority Matroid Median. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2023.7, author = {Bajpai, Tanvi and Chekuri, Chandra}, title = {{Bicriteria Approximation Algorithms for Priority Matroid Median}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {7:1--7:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.7}, URN = {urn:nbn:de:0030-drops-188328}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.7}, annote = {Keywords: k-median, fair clustering, matroid} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz. The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2023.10, author = {Golovnev, Alexander and Guo, Siyao and Peters, Spencer and Stephens-Davidowitz, Noah}, title = {{The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {10:1--10:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.10}, URN = {urn:nbn:de:0030-drops-188351}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.10}, annote = {Keywords: search-to-decision reductions, oracles, constraint satisfaction, traveling salesman, discrete optimization} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Noah G. Singer. Oblivious Algorithms for the Max-kAND Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{singer:LIPIcs.APPROX/RANDOM.2023.15, author = {Singer, Noah G.}, title = {{Oblivious Algorithms for the Max-kAND Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {15:1--15:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.15}, URN = {urn:nbn:de:0030-drops-188409}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.15}, annote = {Keywords: streaming algorithm, approximation algorithm, constraint satisfaction problem (CSP), factor-revealing linear program} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Anita Dürr, Nicolas El Maalouly, and Lasse Wulf. An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{durr_et_al:LIPIcs.APPROX/RANDOM.2023.18, author = {D\"{u}rr, Anita and El Maalouly, Nicolas and Wulf, Lasse}, title = {{An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {18:1--18:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.18}, URN = {urn:nbn:de:0030-drops-188436}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.18}, annote = {Keywords: Perfect Matching, Exact Matching, Red-Blue Matching, Approximation Algorithms, Bounded Color Matching} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Mark de Berg, Arpan Sadhukhan, and Frits Spieksma. Stable Approximation Algorithms for Dominating Set and Independent Set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{deberg_et_al:LIPIcs.APPROX/RANDOM.2023.27, author = {de Berg, Mark and Sadhukhan, Arpan and Spieksma, Frits}, title = {{Stable Approximation Algorithms for Dominating Set and Independent Set}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {27:1--27:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.27}, URN = {urn:nbn:de:0030-drops-188527}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.27}, annote = {Keywords: Dynamic algorithms, approximation algorithms, stability, dominating set, independent set} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{filmus_et_al:LIPIcs.APPROX/RANDOM.2023.36, author = {Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry}, title = {{Sampling and Certifying Symmetric Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {36:1--36:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.36}, URN = {urn:nbn:de:0030-drops-188611}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.36}, annote = {Keywords: sampling, lower bounds, robust sunflowers, decision trees, switching networks} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Konrad Anand, Andreas Göbel, Marcus Pappik, and Will Perkins. Perfect Sampling for Hard Spheres from Strong Spatial Mixing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{anand_et_al:LIPIcs.APPROX/RANDOM.2023.38, author = {Anand, Konrad and G\"{o}bel, Andreas and Pappik, Marcus and Perkins, Will}, title = {{Perfect Sampling for Hard Spheres from Strong Spatial Mixing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {38:1--38:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.38}, URN = {urn:nbn:de:0030-drops-188638}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.38}, annote = {Keywords: perfect sampling, hard-sphere model, Gibbs point processes} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Prashanth Amireddy, Srikanth Srinivasan, and Madhu Sudan. Low-Degree Testing over Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2023.41, author = {Amireddy, Prashanth and Srinivasan, Srikanth and Sudan, Madhu}, title = {{Low-Degree Testing over Grids}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {41:1--41:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.41}, URN = {urn:nbn:de:0030-drops-188665}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.41}, annote = {Keywords: Property testing, Low-degree testing, Small-set expansion, Local testing} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Joshua Cook and Ron D. Rothblum. Efficient Interactive Proofs for Non-Deterministic Bounded Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cook_et_al:LIPIcs.APPROX/RANDOM.2023.47, author = {Cook, Joshua and Rothblum, Ron D.}, title = {{Efficient Interactive Proofs for Non-Deterministic Bounded Space}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {47:1--47:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.47}, URN = {urn:nbn:de:0030-drops-188727}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.47}, annote = {Keywords: Interactive Proofs, Alternating Algorithms, AC0\lbrack2\rbrack, Doubly Efficient Proofs} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Renato Ferreira Pinto Jr.. Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ferreirapintojr.:LIPIcs.APPROX/RANDOM.2023.61, author = {Ferreira Pinto Jr., Renato}, title = {{Directed Poincar\'{e} Inequalities and L¹ Monotonicity Testing of Lipschitz Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {61:1--61:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.61}, URN = {urn:nbn:de:0030-drops-188867}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.61}, annote = {Keywords: Monotonicity testing, property testing, isoperimetric inequalities, Poincar\'{e} inequalities} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 1-352, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Proceedings{taumankalai_et_al:LIPIcs.ITC.2020, title = {{LIPIcs, Volume 163, ITC 2020, Complete Volume}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {1--352}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020}, URN = {urn:nbn:de:0030-drops-121048}, doi = {10.4230/LIPIcs.ITC.2020}, annote = {Keywords: LIPIcs, Volume 163, ITC 2020, Complete Volume} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{taumankalai_et_al:LIPIcs.ITC.2020.0, author = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {0:i--0:xiv}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.0}, URN = {urn:nbn:de:0030-drops-121057}, doi = {10.4230/LIPIcs.ITC.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Feedback for Dagstuhl Publishing