LIPIcs, Volume 145
APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA
Editors: Dimitris Achlioptas and László A. Végh
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Fotis Iliopoulos. Improved Bounds for Coloring Locally Sparse Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{iliopoulos:LIPIcs.APPROX/RANDOM.2021.39, author = {Iliopoulos, Fotis}, title = {{Improved Bounds for Coloring Locally Sparse Hypergraphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {39:1--39:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.39}, URN = {urn:nbn:de:0030-drops-147328}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.39}, annote = {Keywords: hypergaph coloring, semi-random method, locally sparse, random hypergraphs} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dimitris Achlioptas and Kostas Zampetakis. Local Approximations of the Independent Set Polynomial. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{achlioptas_et_al:LIPIcs.ICALP.2021.8, author = {Achlioptas, Dimitris and Zampetakis, Kostas}, title = {{Local Approximations of the Independent Set Polynomial}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.8}, URN = {urn:nbn:de:0030-drops-140773}, doi = {10.4230/LIPIcs.ICALP.2021.8}, annote = {Keywords: Independent Set Polynomial, Lov\'{a}sz Local Lemma, Self-avoiding Walks} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019, title = {{LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019}, URN = {urn:nbn:de:0030-drops-113014}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019}, annote = {Keywords: Mathematics of computing; Theory of computation} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019.0, author = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {0:i--0:xxii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.0}, URN = {urn:nbn:de:0030-drops-112155}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Manuel Fernández V, David P. Woodruff, and Taisuke Yasuda. The Query Complexity of Mastermind with l_p Distances. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 1:1-1:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fernandezv_et_al:LIPIcs.APPROX-RANDOM.2019.1, author = {Fern\'{a}ndez V, Manuel and Woodruff, David P. and Yasuda, Taisuke}, title = {{The Query Complexity of Mastermind with l\underlinep Distances}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {1:1--1:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.1}, URN = {urn:nbn:de:0030-drops-112165}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.1}, annote = {Keywords: Mastermind, Query Complexity, l\underlinep Distance} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran. Tracking the l_2 Norm with Constant Update Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chou_et_al:LIPIcs.APPROX-RANDOM.2019.2, author = {Chou, Chi-Ning and Lei, Zhixian and Nakkiran, Preetum}, title = {{Tracking the l\underline2 Norm with Constant Update Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {2:1--2:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.2}, URN = {urn:nbn:de:0030-drops-112175}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.2}, annote = {Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Benjamin Moseley and Maxim Sviridenko. Submodular Optimization with Contention Resolution Extensions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{moseley_et_al:LIPIcs.APPROX-RANDOM.2019.3, author = {Moseley, Benjamin and Sviridenko, Maxim}, title = {{Submodular Optimization with Contention Resolution Extensions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {3:1--3:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.3}, URN = {urn:nbn:de:0030-drops-112188}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.3}, annote = {Keywords: Submodular, Optimization, Approximation Algorithm, Interval Scheduling} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
David Ellis Hershkowitz, R. Ravi, and Sahil Singla. Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hershkowitz_et_al:LIPIcs.APPROX-RANDOM.2019.4, author = {Hershkowitz, David Ellis and Ravi, R. and Singla, Sahil}, title = {{Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.4}, URN = {urn:nbn:de:0030-drops-112196}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.4}, annote = {Keywords: Approximation Algorithms, Optimization Under Uncertainty, Two-Stage Optimization, Expected Max} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Venkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2019.5, author = {Guruswami, Venkatesan and Tao, Runzhou}, title = {{Streaming Hardness of Unique Games}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {5:1--5:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.5}, URN = {urn:nbn:de:0030-drops-112209}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.5}, annote = {Keywords: Communication complexity, CSP, Fourier Analysis, Lower bounds, Streaming algorithms, Unique Games} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Arnold Filtser. On Strong Diameter Padded Decompositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{filtser:LIPIcs.APPROX-RANDOM.2019.6, author = {Filtser, Arnold}, title = {{On Strong Diameter Padded Decompositions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {6:1--6:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.6}, URN = {urn:nbn:de:0030-drops-112217}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.6}, annote = {Keywords: Padded decomposition, Strong Diameter, Sparse Cover, Doubling Dimension, Minor free graphs, Unique Games, Spanners, Distance Oracles} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Alon Eden, Uriel Feige, and Michal Feldman. Max-Min Greedy Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{eden_et_al:LIPIcs.APPROX-RANDOM.2019.7, author = {Eden, Alon and Feige, Uriel and Feldman, Michal}, title = {{Max-Min Greedy Matching}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {7:1--7:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.7}, URN = {urn:nbn:de:0030-drops-112229}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.7}, annote = {Keywords: Online matching, Pricing mechanism, Markets} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Gary L. Miller, Noel J. Walkington, and Alex L. Wang. Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{miller_et_al:LIPIcs.APPROX-RANDOM.2019.8, author = {Miller, Gary L. and Walkington, Noel J. and Wang, Alex L.}, title = {{Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {8:1--8:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.8}, URN = {urn:nbn:de:0030-drops-112236}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.8}, annote = {Keywords: Hardy, Muckenhoupt, Laplacian, eigenvalue, effective resistance} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari. Improved 3LIN Hardness via Linear Label Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{harsha_et_al:LIPIcs.APPROX-RANDOM.2019.9, author = {Harsha, Prahladh and Khot, Subhash and Lee, Euiwoong and Thiruvenkatachari, Devanathan}, title = {{Improved 3LIN Hardness via Linear Label Cover}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.9}, URN = {urn:nbn:de:0030-drops-112245}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.9}, annote = {Keywords: probabilistically checkable proofs, PCP, composition, 3LIN, low soundness error} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż. Dynamic Pricing of Servers on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2019.10, author = {Cohen, Ilan Reuven and Eden, Alon and Fiat, Amos and Je\.{z}, {\L}ukasz}, title = {{Dynamic Pricing of Servers on Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {10:1--10:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, 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.2019.10}, URN = {urn:nbn:de:0030-drops-112252}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.10}, annote = {Keywords: Online algorithms, Online mechanisms, k-server problem, Online pricing} }
Feedback for Dagstuhl Publishing