LIPIcs, Volume 67
ITCS 2017, January 9-11, 2017, Berkeley, CA, USA
Editors: Christos H. Papadimitriou
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras. Wealth Inequality and the Price of Anarchy. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gemici_et_al:LIPIcs.STACS.2019.31, author = {Gemici, Kurtulu\c{s} and Koutsoupias, Elias and Monnot, Barnab\'{e} and Papadimitriou, Christos H. and Piliouras, Georgios}, title = {{Wealth Inequality and the Price of Anarchy}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {31:1--31: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.31}, URN = {urn:nbn:de:0030-drops-102707}, doi = {10.4230/LIPIcs.STACS.2019.31}, annote = {Keywords: congestion games, inequality} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{knop_et_al:LIPIcs.STACS.2019.44, author = {Knop, Du\v{s}an and Pilipczuk, Micha{\l} and Wrochna, Marcin}, title = {{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {44:1--44:15}, 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.44}, URN = {urn:nbn:de:0030-drops-102831}, doi = {10.4230/LIPIcs.STACS.2019.44}, annote = {Keywords: integer linear programming, fixed-parameter tractability, ETH} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Christos H. Papadimitriou and Santosh S. Vempala. Random Projection in the Brain and Computation with Assemblies of Neurons. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{papadimitriou_et_al:LIPIcs.ITCS.2019.57, author = {Papadimitriou, Christos H. and Vempala, Santosh S.}, title = {{Random Projection in the Brain and Computation with Assemblies of Neurons}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {57:1--57:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.57}, URN = {urn:nbn:de:0030-drops-101506}, doi = {10.4230/LIPIcs.ITCS.2019.57}, annote = {Keywords: Brain computation, random projection, assemblies, plasticity, memory, association} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Paul W. Goldberg and Christos H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{goldberg_et_al:LIPIcs.ITCS.2018.37, author = {Goldberg, Paul W. and Papadimitriou, Christos H.}, title = {{Towards a Unified Complexity Theory of Total Functions}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {37:1--37:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.37}, URN = {urn:nbn:de:0030-drops-83403}, doi = {10.4230/LIPIcs.ITCS.2018.37}, annote = {Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, and Santosh S. Vempala. Long Term Memory and the Densest K-Subgraph Problem. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{legenstein_et_al:LIPIcs.ITCS.2018.57, author = {Legenstein, Robert and Maass, Wolfgang and Papadimitriou, Christos H. and Vempala, Santosh S.}, title = {{Long Term Memory and the Densest K-Subgraph Problem}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.57}, URN = {urn:nbn:de:0030-drops-83593}, doi = {10.4230/LIPIcs.ITCS.2018.57}, annote = {Keywords: Brain computation, long term memory, assemblies, association} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Proceedings{papadimitriou:LIPIcs.ITCS.2017, title = {{LIPIcs, Volume 67, ITCS'17, Complete Volume}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017}, URN = {urn:nbn:de:0030-drops-82066}, doi = {10.4230/LIPIcs.ITCS.2017}, annote = {Keywords: Theory of Computation, Mathematics of Computing} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{papadimitriou:LIPIcs.ITCS.2017.0, author = {Papadimitriou, Christos H.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {0:i--0:x}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.0}, URN = {urn:nbn:de:0030-drops-82025}, doi = {10.4230/LIPIcs.ITCS.2017.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
James R. Lee. Separators in Region Intersection Graphs. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{lee:LIPIcs.ITCS.2017.1, author = {Lee, James R.}, title = {{Separators in Region Intersection Graphs}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {1:1--1:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.1}, URN = {urn:nbn:de:0030-drops-81970}, doi = {10.4230/LIPIcs.ITCS.2017.1}, annote = {Keywords: Graph separators, planar graphs, spectral partitioning} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Ioannis Panageas and Georgios Piliouras. Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{panageas_et_al:LIPIcs.ITCS.2017.2, author = {Panageas, Ioannis and Piliouras, Georgios}, title = {{Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {2:1--2:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.2}, URN = {urn:nbn:de:0030-drops-81640}, doi = {10.4230/LIPIcs.ITCS.2017.2}, annote = {Keywords: Gradient Descent, Center-stable manifold, Saddle points, Hessian} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{allenzhu_et_al:LIPIcs.ITCS.2017.3, author = {Allen-Zhu, Zeyuan and Orecchia, Lorenzo}, title = {{Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {3:1--3:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.3}, URN = {urn:nbn:de:0030-drops-81850}, doi = {10.4230/LIPIcs.ITCS.2017.3}, annote = {Keywords: linear coupling, gradient descent, mirror descent, acceleration} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Tali Kaufman and David Mass. High Dimensional Random Walks and Colorful Expansion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 4:1-4:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kaufman_et_al:LIPIcs.ITCS.2017.4, author = {Kaufman, Tali and Mass, David}, title = {{High Dimensional Random Walks and Colorful Expansion}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {4:1--4:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.4}, URN = {urn:nbn:de:0030-drops-81838}, doi = {10.4230/LIPIcs.ITCS.2017.4}, annote = {Keywords: High dimensional expanders, expander graphs, random walks} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Prasad Raghavendra, Nick Ryder, and Nikhil Srivastava. Real Stability Testing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{raghavendra_et_al:LIPIcs.ITCS.2017.5, author = {Raghavendra, Prasad and Ryder, Nick and Srivastava, Nikhil}, title = {{Real Stability Testing}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.5}, URN = {urn:nbn:de:0030-drops-81965}, doi = {10.4230/LIPIcs.ITCS.2017.5}, annote = {Keywords: real stable polynomials, hyperbolic polynomials, real rootedness, moment matrix, sturm sequence} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Silvio Micali. Very Simple and Efficient Byzantine Agreement. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, p. 6:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{micali:LIPIcs.ITCS.2017.6, author = {Micali, Silvio}, title = {{Very Simple and Efficient Byzantine Agreement}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {6:1--6:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.6}, URN = {urn:nbn:de:0030-drops-82011}, doi = {10.4230/LIPIcs.ITCS.2017.6}, annote = {Keywords: Byzantine Agreement} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Benny Applebaum, Naama Haramaty-Krasne, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan. Low-Complexity Cryptographic Hash Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 7:1-7:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2017.7, author = {Applebaum, Benny and Haramaty-Krasne, Naama and Ishai, Yuval and Kushilevitz, Eyal and Vaikuntanathan, Vinod}, title = {{Low-Complexity Cryptographic Hash Functions}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {7:1--7:31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.7}, URN = {urn:nbn:de:0030-drops-81901}, doi = {10.4230/LIPIcs.ITCS.2017.7}, annote = {Keywords: Cryptography, hash functions, complexity theory, coding theory} }
Feedback for Dagstuhl Publishing