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-dev.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 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Andrej Bogdanov and Alon Rosen. Nondeterministic Interactive Refutations for Nearest Boolean Vector. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bogdanov_et_al:LIPIcs.ICALP.2023.28, author = {Bogdanov, Andrej and Rosen, Alon}, title = {{Nondeterministic Interactive Refutations for Nearest Boolean Vector}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {28:1--28:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.28}, URN = {urn:nbn:de:0030-drops-180801}, doi = {10.4230/LIPIcs.ICALP.2023.28}, annote = {Keywords: average-case complexity, statistical zero-knowledge, nondeterministic refutation, Sherrington-Kirkpatrick Hamiltonian, complexity of statistical inference, lattice smoothing} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones. Exact Completeness of LP Hierarchies for Linear Codes. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{coregliano_et_al:LIPIcs.ITCS.2023.40, author = {Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris}, title = {{Exact Completeness of LP Hierarchies for Linear Codes}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {40:1--40:18}, 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.40}, URN = {urn:nbn:de:0030-drops-175433}, doi = {10.4230/LIPIcs.ITCS.2023.40}, annote = {Keywords: LP bound, linear codes, Delsarte’s LP, combinatorial polytopes, pseudoexpectation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 77:1-77:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jones_et_al:LIPIcs.ITCS.2023.77, author = {Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan}, title = {{Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {77:1--77:26}, 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.77}, URN = {urn:nbn:de:0030-drops-175804}, doi = {10.4230/LIPIcs.ITCS.2023.77}, annote = {Keywords: spin glass, overlap gap property, constraint satisfaction problem, Guerra-Toninelli interpolation} }
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Chris Barrett, Willem Heijltjes, and Guy McCusker. The Functional Machine Calculus II: Semantics. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{barrett_et_al:LIPIcs.CSL.2023.10, author = {Barrett, Chris and Heijltjes, Willem and McCusker, Guy}, title = {{The Functional Machine Calculus II: Semantics}}, booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-264-8}, ISSN = {1868-8969}, year = {2023}, volume = {252}, editor = {Klin, Bartek and Pimentel, Elaine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.10}, URN = {urn:nbn:de:0030-drops-174716}, doi = {10.4230/LIPIcs.CSL.2023.10}, annote = {Keywords: lambda-calculus, computational effects, denotational semantics, strong normalization} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones. A Complete Linear Programming Hierarchy for Linear Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{coregliano_et_al:LIPIcs.ITCS.2022.51, author = {Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris}, title = {{A Complete Linear Programming Hierarchy for Linear Codes}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {51:1--51:22}, 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.51}, URN = {urn:nbn:de:0030-drops-156474}, doi = {10.4230/LIPIcs.ITCS.2022.51}, annote = {Keywords: Coding theory, code bounds, convex programming, linear programming hierarchy} }
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} }
Feedback for Dagstuhl Publishing