OASIcs, Volume 69
SOSA 2019, January 8-9, 2019, San Diego, CA, USA
Editors: Jeremy T. Fineman and Michael Mitzenmacher
LIPIcs, Volume 55
ICALP 2016, July 11-15, 2016, Rome, Italy
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. Uniform Bounds for Scheduling with Job Size Estimates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 114:1-114:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{scully_et_al:LIPIcs.ITCS.2022.114, author = {Scully, Ziv and Grosof, Isaac and Mitzenmacher, Michael}, title = {{Uniform Bounds for Scheduling with Job Size Estimates}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {114:1--114:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.114}, URN = {urn:nbn:de:0030-drops-157108}, doi = {10.4230/LIPIcs.ITCS.2022.114}, annote = {Keywords: Scheduling, queueing systems, algorithms with predictions, shortest remaining processing time (SRPT), preemptive shortest job first (PSJF), M/G/1 queue} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Ran Ben Basat, Michael Mitzenmacher, and Shay Vargaftik. How to Send a Real Number Using a Single Bit (And Some Shared Randomness). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{benbasat_et_al:LIPIcs.ICALP.2021.25, author = {Ben Basat, Ran and Mitzenmacher, Michael and Vargaftik, Shay}, title = {{How to Send a Real Number Using a Single Bit (And Some Shared Randomness)}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {25:1--25:20}, 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.25}, URN = {urn:nbn:de:0030-drops-140942}, doi = {10.4230/LIPIcs.ICALP.2021.25}, annote = {Keywords: Randomized Algorithms, Approximation Algorithms, Shared Randomness, Distributed Protocols, Estimation, Subtractive Dithering} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Michael Mitzenmacher. Scheduling with Predictions and the Price of Misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{mitzenmacher:LIPIcs.ITCS.2020.14, author = {Mitzenmacher, Michael}, title = {{Scheduling with Predictions and the Price of Misprediction}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.14}, URN = {urn:nbn:de:0030-drops-116996}, doi = {10.4230/LIPIcs.ITCS.2020.14}, annote = {Keywords: Queues, shortest remaining processing time, algorithms with predictions, scheduling} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{fineman_et_al:OASIcs.SOSA.2019, title = {{OASIcs, Volume 69, SOSA'19, Complete Volume}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019}, URN = {urn:nbn:de:0030-drops-101683}, doi = {10.4230/OASIcs.SOSA.2019}, annote = {Keywords: Theory of computation, Design and analysis of algorithms} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fineman_et_al:OASIcs.SOSA.2019.0, author = {Fineman, Jeremy T. and Mitzenmacher, Michael}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {0:i--0:x}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.0}, URN = {urn:nbn:de:0030-drops-100263}, doi = {10.4230/OASIcs.SOSA.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Günter Rote. Isotonic Regression by Dynamic Programming. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{rote:OASIcs.SOSA.2019.1, author = {Rote, G\"{u}nter}, title = {{Isotonic Regression by Dynamic Programming}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {1:1--1:18}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.1}, URN = {urn:nbn:de:0030-drops-100274}, doi = {10.4230/OASIcs.SOSA.2019.1}, annote = {Keywords: Convex functions, dynamic programming, convex hull, isotonic regression} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Josh Alman. An Illuminating Algorithm for the Light Bulb Problem. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 2:1-2:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alman:OASIcs.SOSA.2019.2, author = {Alman, Josh}, title = {{An Illuminating Algorithm for the Light Bulb Problem}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {2:1--2:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.2}, URN = {urn:nbn:de:0030-drops-100289}, doi = {10.4230/OASIcs.SOSA.2019.2}, annote = {Keywords: Light Bulb Problem, Polynomial Method, Finding Correlations} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Sixue Liu and Robert E. Tarjan. Simple Concurrent Labeling Algorithms for Connected Components. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{liu_et_al:OASIcs.SOSA.2019.3, author = {Liu, Sixue and Tarjan, Robert E.}, title = {{Simple Concurrent Labeling Algorithms for Connected Components}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {3:1--3:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.3}, URN = {urn:nbn:de:0030-drops-100292}, doi = {10.4230/OASIcs.SOSA.2019.3}, annote = {Keywords: Connected Components, Concurrent Algorithms} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, and Daniel Wolleb-Graf. A Framework for Searching in Graphs in the Presence of Errors. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dereniowski_et_al:OASIcs.SOSA.2019.4, author = {Dereniowski, Dariusz and Tiegel, Stefan and Uznanski, Przemyslaw and Wolleb-Graf, Daniel}, title = {{A Framework for Searching in Graphs in the Presence of Errors}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {4:1--4:17}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.4}, URN = {urn:nbn:de:0030-drops-100305}, doi = {10.4230/OASIcs.SOSA.2019.4}, annote = {Keywords: graph algorithms, noisy binary search, query complexity, reliability} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Haim Kaplan, László Kozma, Or Zamir, and Uri Zwick. Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kaplan_et_al:OASIcs.SOSA.2019.5, author = {Kaplan, Haim and Kozma, L\'{a}szl\'{o} and Zamir, Or and Zwick, Uri}, title = {{Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {5:1--5:21}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.5}, URN = {urn:nbn:de:0030-drops-100315}, doi = {10.4230/OASIcs.SOSA.2019.5}, annote = {Keywords: selection, soft heap} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Kent Quanrud. Approximating Optimal Transport With Linear Programs. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 6:1-6:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{quanrud:OASIcs.SOSA.2019.6, author = {Quanrud, Kent}, title = {{Approximating Optimal Transport With Linear Programs}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {6:1--6:9}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.6}, URN = {urn:nbn:de:0030-drops-100321}, doi = {10.4230/OASIcs.SOSA.2019.6}, annote = {Keywords: optimal transport, fast approximations, linear programming} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Chandra Chekuri, Kent Quanrud, and Chao Xu. LP Relaxation and Tree Packing for Minimum k-cuts. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chekuri_et_al:OASIcs.SOSA.2019.7, author = {Chekuri, Chandra and Quanrud, Kent and Xu, Chao}, title = {{LP Relaxation and Tree Packing for Minimum k-cuts}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {7:1--7:18}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.7}, URN = {urn:nbn:de:0030-drops-100335}, doi = {10.4230/OASIcs.SOSA.2019.7}, annote = {Keywords: k-cut, LP relaxation, tree packing} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Stefan Felsner and Günter Rote. On Primal-Dual Circle Representations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{felsner_et_al:OASIcs.SOSA.2019.8, author = {Felsner, Stefan and Rote, G\"{u}nter}, title = {{On Primal-Dual Circle Representations}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {8:1--8:18}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.8}, URN = {urn:nbn:de:0030-drops-100349}, doi = {10.4230/OASIcs.SOSA.2019.8}, annote = {Keywords: Disk packing, planar graphs, contact representation} }
Feedback for Dagstuhl Publishing