Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dmitriy Kunisky and Xifan Yu. A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 30:1-30:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kunisky_et_al:LIPIcs.CCC.2023.30, author = {Kunisky, Dmitriy and Yu, Xifan}, title = {{A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {30:1--30:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.30}, URN = {urn:nbn:de:0030-drops-183008}, doi = {10.4230/LIPIcs.CCC.2023.30}, annote = {Keywords: convex optimization, sum of squares, Paley graph, derandomization} }
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.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 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational Hardness of Certifying Bounds on Constrained PCA Problems. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 78:1-78:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bandeira_et_al:LIPIcs.ITCS.2020.78, author = {Bandeira, Afonso S. and Kunisky, Dmitriy and Wein, Alexander S.}, title = {{Computational Hardness of Certifying Bounds on Constrained PCA Problems}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {78:1--78:29}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.78}, URN = {urn:nbn:de:0030-drops-117633}, doi = {10.4230/LIPIcs.ITCS.2020.78}, annote = {Keywords: Certification, Sherrington-Kirkpatrick model, spiked Wishart model, low-degree likelihood ratio} }
Feedback for Dagstuhl Publishing