LIPIcs, Volume 94
ITCS 2018, January 11, 2018, Cambridge, MA, USA
Editors: Anna R. Karlin
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{karlin:LIPIcs.ICALP.2023.1, author = {Karlin, Anna R.}, title = {{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.1}, URN = {urn:nbn:de:0030-drops-180531}, doi = {10.4230/LIPIcs.ICALP.2023.1}, annote = {Keywords: Traveling Salesperson Problem, approximation algorithm} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2, author = {Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan}, title = {{Matroid Partition Property and the Secretary Problem}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2}, URN = {urn:nbn:de:0030-drops-175051}, doi = {10.4230/LIPIcs.ITCS.2023.2}, annote = {Keywords: Online algorithms, Matroids, Matroid secretary problem} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Anna R. Karlin. LIPIcs, Volume 94, ITCS'18, Complete Volume. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Proceedings{karlin:LIPIcs.ITCS.2018, title = {{LIPIcs, Volume 94, ITCS'18, Complete Volume}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, 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}, URN = {urn:nbn:de:0030-drops-84419}, doi = {10.4230/LIPIcs.ITCS.2018}, annote = {Keywords: Theory of Computation, Mathematics of Computing} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Anna R. Karlin. Front Matter, Table of Contents, Preface, Conference Organization. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 0:i-0:xii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{karlin:LIPIcs.ITCS.2018.0, author = {Karlin, Anna R.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {0:i--0:xii}, 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.0}, URN = {urn:nbn:de:0030-drops-83104}, doi = {10.4230/LIPIcs.ITCS.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 1:1-1:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2018.1, author = {Efremenko, Klim and Garg, Ankit and Oliveira, Rafael and Wigderson, Avi}, title = {{Barriers for Rank Methods in Arithmetic Complexity}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {1:1--1:19}, 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.1}, URN = {urn:nbn:de:0030-drops-83506}, doi = {10.4230/LIPIcs.ITCS.2018.1}, annote = {Keywords: Lower Bounds, Barriers, Partial Derivatives, Flattenings, Algebraic Complexity} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, and Michael Kowalczyk. A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 2:1-2:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{cai_et_al:LIPIcs.ITCS.2018.2, author = {Cai, Jin-Yi and Fu, Zhiguo and Girstmair, Kurt and Kowalczyk, Michael}, title = {{A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {2:1--2:22}, 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.2}, URN = {urn:nbn:de:0030-drops-83251}, doi = {10.4230/LIPIcs.ITCS.2018.2}, annote = {Keywords: Spin Systems, Holant Problems, Number Theory, Characters, Cyclotomic Fields} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum Query Algorithms are Completely Bounded Forms. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 3:1-3:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2018.3, author = {Arunachalam, Srinivasan and Bri\"{e}t, Jop and Palazuelos, Carlos}, title = {{Quantum Query Algorithms are Completely Bounded Forms}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {3:1--3:21}, 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.3}, URN = {urn:nbn:de:0030-drops-83383}, doi = {10.4230/LIPIcs.ITCS.2018.3}, annote = {Keywords: Quantum query algorithms, operator space theory, polynomial method, approximate degree.} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Bill Fefferman and Cedric Yen-Yu Lin. A Complete Characterization of Unitary Quantum Space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 4:1-4:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{fefferman_et_al:LIPIcs.ITCS.2018.4, author = {Fefferman, Bill and Lin, Cedric Yen-Yu}, title = {{A Complete Characterization of Unitary Quantum Space}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {4:1--4:21}, 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.4}, URN = {urn:nbn:de:0030-drops-83242}, doi = {10.4230/LIPIcs.ITCS.2018.4}, annote = {Keywords: Quantum complexity, space complexity, complete problems, QMA} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, and Hongyang Zhang. Matrix Completion and Related Problems via Strong Duality. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 5:1-5:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{balcan_et_al:LIPIcs.ITCS.2018.5, author = {Balcan, Maria-Florina and Liang, Yingyu and Woodruff, David P. and Zhang, Hongyang}, title = {{Matrix Completion and Related Problems via Strong Duality}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {5:1--5:22}, 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.5}, URN = {urn:nbn:de:0030-drops-83583}, doi = {10.4230/LIPIcs.ITCS.2018.5}, annote = {Keywords: Non-Convex Optimization, Strong Duality, Matrix Completion, Robust PCA, Sample Complexity} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Michael Ben-Or and Lior Eldar. A Quasi-Random Approach to Matrix Spectral Analysis. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{benor_et_al:LIPIcs.ITCS.2018.6, author = {Ben-Or, Michael and Eldar, Lior}, title = {{A Quasi-Random Approach to Matrix Spectral Analysis}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {6:1--6:22}, 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.6}, URN = {urn:nbn:de:0030-drops-83288}, doi = {10.4230/LIPIcs.ITCS.2018.6}, annote = {Keywords: linear algebra, eigenvalues, eigenvectors, low-discrepancy sequence} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Aditya Bhaskara and Silvio Lattanzi. Non-Negative Sparse Regression and Column Subset Selection with L1 Error. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{bhaskara_et_al:LIPIcs.ITCS.2018.7, author = {Bhaskara, Aditya and Lattanzi, Silvio}, title = {{Non-Negative Sparse Regression and Column Subset Selection with L1 Error}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {7:1--7: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.7}, URN = {urn:nbn:de:0030-drops-83548}, doi = {10.4230/LIPIcs.ITCS.2018.7}, annote = {Keywords: Sparse regression, L1 error optimization, Column subset selection} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 8:1-8:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{musco_et_al:LIPIcs.ITCS.2018.8, author = {Musco, Cameron and Netrapalli, Praneeth and Sidford, Aaron and Ubaru, Shashanka and Woodruff, David P.}, title = {{Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {8:1--8:21}, 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.8}, URN = {urn:nbn:de:0030-drops-83397}, doi = {10.4230/LIPIcs.ITCS.2018.8}, annote = {Keywords: spectrum approximation, matrix norm computation, fine-grained complexity, linear algebra} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Olaf Beyersdorff, Joshua Blinkhorn, and Luke Hinde. Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 9:1-9:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{beyersdorff_et_al:LIPIcs.ITCS.2018.9, author = {Beyersdorff, Olaf and Blinkhorn, Joshua and Hinde, Luke}, title = {{Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {9:1--9:18}, 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.9}, URN = {urn:nbn:de:0030-drops-83228}, doi = {10.4230/LIPIcs.ITCS.2018.9}, annote = {Keywords: quantified Boolean formulas, proof complexity, lower bounds} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, and Robert Robere. Stabbing Planes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{beame_et_al:LIPIcs.ITCS.2018.10, author = {Beame, Paul and Fleming, Noah and Impagliazzo, Russell and Kolokolova, Antonina and Pankratov, Denis and Pitassi, Toniann and Robere, Robert}, title = {{Stabbing Planes}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-83418}, doi = {10.4230/LIPIcs.ITCS.2018.10}, annote = {Keywords: Complexity Theory, Proof Complexity, Communication Complexity, Cutting Planes, Semi-Algebraic Proof Systems, Pseudo Boolean Solvers, SAT solvers, Inte} }
Feedback for Dagstuhl Publishing