Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Euiwoong Lee and Pasin Manurangsi. Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lee_et_al:LIPIcs.ITCS.2024.71, author = {Lee, Euiwoong and Manurangsi, Pasin}, title = {{Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {71:1--71:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.71}, URN = {urn:nbn:de:0030-drops-195996}, doi = {10.4230/LIPIcs.ITCS.2024.71}, annote = {Keywords: Hardness of Approximation, Bounded Degree, Constraint Satisfaction Problems, Independent Set} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26, author = {Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram}, title = {{Bounded Indistinguishability for Simple Sources}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {26:1--26:18}, 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.26}, URN = {urn:nbn:de:0030-drops-156223}, doi = {10.4230/LIPIcs.ITCS.2022.26}, annote = {Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
William Kretschmer. The Quantum Supremacy Tsirelson Inequality. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kretschmer:LIPIcs.ITCS.2021.13, author = {Kretschmer, William}, title = {{The Quantum Supremacy Tsirelson Inequality}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James 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.2021.13}, URN = {urn:nbn:de:0030-drops-135524}, doi = {10.4230/LIPIcs.ITCS.2021.13}, annote = {Keywords: quantum supremacy, quantum query complexity, random circuit sampling} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ofer Grossman and Justin Holmgren. Error Correcting Codes for Uncompressed Messages. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grossman_et_al:LIPIcs.ITCS.2021.43, author = {Grossman, Ofer and Holmgren, Justin}, title = {{Error Correcting Codes for Uncompressed Messages}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {43:1--43:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James 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.2021.43}, URN = {urn:nbn:de:0030-drops-135828}, doi = {10.4230/LIPIcs.ITCS.2021.43}, annote = {Keywords: Coding Theory, List Decoding} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Justin Holmgren and Alexander S. Wein. Counterexamples to the Low-Degree Conjecture. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 75:1-75:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{holmgren_et_al:LIPIcs.ITCS.2021.75, author = {Holmgren, Justin and Wein, Alexander S.}, title = {{Counterexamples to the Low-Degree Conjecture}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {75:1--75:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James 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.2021.75}, URN = {urn:nbn:de:0030-drops-136148}, doi = {10.4230/LIPIcs.ITCS.2021.75}, annote = {Keywords: Low-degree likelihood ratio, error-correcting codes} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Satyan L. Devadoss, Daniel D. Johnson, Justin Lee, and Jackson Warley. Geometric Realizations of the 3D Associahedron (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 75:1-75:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{devadoss_et_al:LIPIcs.SoCG.2018.75, author = {Devadoss, Satyan L. and Johnson, Daniel D. and Lee, Justin and Warley, Jackson}, title = {{Geometric Realizations of the 3D Associahedron}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {75:1--75:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.75}, URN = {urn:nbn:de:0030-drops-87886}, doi = {10.4230/LIPIcs.SoCG.2018.75}, annote = {Keywords: associahedron, secondary polytope, realization} }
Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)
Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, and Justin Thaler. A Framework for Estimating Stream Expression Cardinalities. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{dasgupta_et_al:LIPIcs.ICDT.2016.6, author = {Dasgupta, Anirban and Lang, Kevin J. and Rhodes, Lee and Thaler, Justin}, title = {{A Framework for Estimating Stream Expression Cardinalities}}, booktitle = {19th International Conference on Database Theory (ICDT 2016)}, pages = {6:1--6:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-002-6}, ISSN = {1868-8969}, year = {2016}, volume = {48}, editor = {Martens, Wim and Zeume, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.6}, URN = {urn:nbn:de:0030-drops-57754}, doi = {10.4230/LIPIcs.ICDT.2016.6}, annote = {Keywords: sketching, data stream algorithms, mergeability, distinct elements, set operations} }
Feedback for Dagstuhl Publishing