Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Prayaag Venkat. Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 98:1-98:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{venkat:LIPIcs.ITCS.2023.98, author = {Venkat, Prayaag}, title = {{Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {98:1--98:12}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.98}, URN = {urn:nbn:de:0030-drops-176015}, doi = {10.4230/LIPIcs.ITCS.2023.98}, annote = {Keywords: Average-case discrepancy theory, lattices, shortest vector problem} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Chris Jones and Aaron Potechin. Almost-Orthogonal Bases for Inner Product Polynomials. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 89:1-89:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{jones_et_al:LIPIcs.ITCS.2022.89, author = {Jones, Chris and Potechin, Aaron}, title = {{Almost-Orthogonal Bases for Inner Product Polynomials}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {89:1--89:21}, 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.89}, URN = {urn:nbn:de:0030-drops-156853}, doi = {10.4230/LIPIcs.ITCS.2022.89}, annote = {Keywords: Orthogonal polynomials, Fourier analysis, combinatorics} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Pravesh K. Kothari and Peter Manohar. A Stress-Free Sum-Of-Squares Lower Bound for Coloring. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kothari_et_al:LIPIcs.CCC.2021.23, author = {Kothari, Pravesh K. and Manohar, Peter}, title = {{A Stress-Free Sum-Of-Squares Lower Bound for Coloring}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {23:1--23:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.23}, URN = {urn:nbn:de:0030-drops-142978}, doi = {10.4230/LIPIcs.CCC.2021.23}, annote = {Keywords: Sum-of-Squares, Graph Coloring, Independent Set, Lower Bounds} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan. Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{angelidakis_et_al:LIPIcs.ESA.2019.7, author = {Angelidakis, Haris and Awasthi, Pranjal and Blum, Avrim and Chatziafratis, Vaggos and Dan, Chen}, title = {{Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.7}, URN = {urn:nbn:de:0030-drops-111288}, doi = {10.4230/LIPIcs.ESA.2019.7}, annote = {Keywords: Bilu-Linial stability, perturbation resilience, beyond worst-case analysis, Independent Set, Vertex Cover, Multiway Cut} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Mrinalkanti Ghosh and Madhur Tulsiani. From Weak to Strong LP Gaps for All CSPs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 11:1-11:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ghosh_et_al:LIPIcs.CCC.2017.11, author = {Ghosh, Mrinalkanti and Tulsiani, Madhur}, title = {{From Weak to Strong LP Gaps for All CSPs}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {11:1--11:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.11}, URN = {urn:nbn:de:0030-drops-75370}, doi = {10.4230/LIPIcs.CCC.2017.11}, annote = {Keywords: Constraint Satisfaction Problem, Convex Programming, Linear Programming Hierarchy, Integrality Gap} }
Feedback for Dagstuhl Publishing