OASIcs, Volume 61
SOSA 2018, January 7-10, 2018, New Orleans, LA, USA
Editors: Raimund Seidel
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Markus Bläser and Anurag Pandey. Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blaser_et_al:LIPIcs.APPROX/RANDOM.2020.8, author = {Bl\"{a}ser, Markus and Pandey, Anurag}, title = {{Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {8:1--8:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.8}, URN = {urn:nbn:de:0030-drops-126112}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.8}, annote = {Keywords: Algebraic Complexity theory, Polynomial Identity Testing, Hitting Set, Pseudorandomness} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic Branching Programs, Border Complexity, and Tangent Spaces. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blaser_et_al:LIPIcs.CCC.2020.21, author = {Bl\"{a}ser, Markus and Ikenmeyer, Christian and Mahajan, Meena and Pandey, Anurag and Saurabh, Nitin}, title = {{Algebraic Branching Programs, Border Complexity, and Tangent Spaces}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {21:1--21:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.21}, URN = {urn:nbn:de:0030-drops-125733}, doi = {10.4230/LIPIcs.CCC.2020.21}, annote = {Keywords: Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Sandeep Sen. A Unified Approach to Tail Estimates for Randomized Incremental Construction. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sen:LIPIcs.STACS.2019.58, author = {Sen, Sandeep}, title = {{A Unified Approach to Tail Estimates for Randomized Incremental Construction}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {58:1--58:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.58}, URN = {urn:nbn:de:0030-drops-102977}, doi = {10.4230/LIPIcs.STACS.2019.58}, annote = {Keywords: ric, tail estimates, martingale, lower bound} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Proceedings{seidel:OASIcs.SOSA.2018, title = {{OASIcs, Volume 61, SOSA'18, Complete Volume}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018}, URN = {urn:nbn:de:0030-drops-84405}, doi = {10.4230/OASIcs.SOSA.2018}, annote = {Keywords: Algorithm design and analysis} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{seidel:OASIcs.SOSA.2018.0, author = {Seidel, Raimund}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {0:i--0:xii}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.0}, URN = {urn:nbn:de:0030-drops-82942}, doi = {10.4230/OASIcs.SOSA.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Yixin Cao. A Naive Algorithm for Feedback Vertex Set. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cao:OASIcs.SOSA.2018.1, author = {Cao, Yixin}, title = {{A Naive Algorithm for Feedback Vertex Set}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {1:1--1:9}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.1}, URN = {urn:nbn:de:0030-drops-82961}, doi = {10.4230/OASIcs.SOSA.2018.1}, annote = {Keywords: greedy algorithm, analysis of algorithms, branching algorithm, parameterized computation -- graph modification problem} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Chandra Chekuri and Thapanapong Rukkanchanunt. A Note on Iterated Rounding for the Survivable Network Design Problem. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chekuri_et_al:OASIcs.SOSA.2018.2, author = {Chekuri, Chandra and Rukkanchanunt, Thapanapong}, title = {{A Note on Iterated Rounding for the Survivable Network Design Problem}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {2:1--2:10}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.2}, URN = {urn:nbn:de:0030-drops-82976}, doi = {10.4230/OASIcs.SOSA.2018.2}, annote = {Keywords: survivable network design, iterated rounding, approximation, element connectivity} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Chandra Chekuri and Mark Idleman. Congestion Minimization for Multipath Routing via Multiroute Flows. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chekuri_et_al:OASIcs.SOSA.2018.3, author = {Chekuri, Chandra and Idleman, Mark}, title = {{Congestion Minimization for Multipath Routing via Multiroute Flows}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {3:1--3:12}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.3}, URN = {urn:nbn:de:0030-drops-82984}, doi = {10.4230/OASIcs.SOSA.2018.3}, annote = {Keywords: multipath routing, congestion minimization, multiroute flows} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Deeparnab Chakrabarty and Sanjeev Khanna. Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chakrabarty_et_al:OASIcs.SOSA.2018.4, author = {Chakrabarty, Deeparnab and Khanna, Sanjeev}, title = {{Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {4:1--4:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.4}, URN = {urn:nbn:de:0030-drops-83045}, doi = {10.4230/OASIcs.SOSA.2018.4}, annote = {Keywords: Matrix Scaling, Entropy Minimization, KL Divergence Inequalities} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Timothy M. Chan. Approximation Schemes for 0-1 Knapsack. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chan:OASIcs.SOSA.2018.5, author = {Chan, Timothy M.}, title = {{Approximation Schemes for 0-1 Knapsack}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {5:1--5:12}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.5}, URN = {urn:nbn:de:0030-drops-82994}, doi = {10.4230/OASIcs.SOSA.2018.5}, annote = {Keywords: knapsack problem, approximation algorithms, optimization, (min,+)-convolution} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
R. Ryan Williams. Counting Solutions to Polynomial Systems via Reductions. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{williams:OASIcs.SOSA.2018.6, author = {Williams, R. Ryan}, title = {{Counting Solutions to Polynomial Systems via Reductions}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {6:1--6:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.6}, URN = {urn:nbn:de:0030-drops-83078}, doi = {10.4230/OASIcs.SOSA.2018.6}, annote = {Keywords: counting complexity, polynomial equations, finite field, derandomization, strong exponential time hypothesis} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Talya Eden and Will Rosenbaum. On Sampling Edges Almost Uniformly. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 7:1-7:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{eden_et_al:OASIcs.SOSA.2018.7, author = {Eden, Talya and Rosenbaum, Will}, title = {{On Sampling Edges Almost Uniformly}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {7:1--7:9}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.7}, URN = {urn:nbn:de:0030-drops-83001}, doi = {10.4230/OASIcs.SOSA.2018.7}, annote = {Keywords: Sublinear Algorithms, Graph Algorithms, Sampling Edges, Query Complexity} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari. A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{borodin_et_al:OASIcs.SOSA.2018.8, author = {Borodin, Allan and Pankratov, Denis and Salehi-Abari, Amirali}, title = {{A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {8:1--8:12}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.8}, URN = {urn:nbn:de:0030-drops-83033}, doi = {10.4230/OASIcs.SOSA.2018.8}, annote = {Keywords: dual bin packing, PTAS, tape-advice complexity} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berenbrink_et_al:OASIcs.SOSA.2018.9, author = {Berenbrink, Petra and Kaaser, Dominik and Kling, Peter and Otterbach, Lena}, title = {{Simple and Efficient Leader Election}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {9:1--9:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9}, URN = {urn:nbn:de:0030-drops-83029}, doi = {10.4230/OASIcs.SOSA.2018.9}, annote = {Keywords: population protocols, leader election, distributed, randomized} }
Feedback for Dagstuhl Publishing