LIPIcs, Volume 79
CCC 2017, July 6-9, 2017, Riga, Latvia
Editors: Ryan O'Donnell
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Emre Yolcu. Lower Bounds for Set-Blocked Clauses Proofs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{yolcu:LIPIcs.STACS.2024.59, author = {Yolcu, Emre}, title = {{Lower Bounds for Set-Blocked Clauses Proofs}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {59:1--59:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.59}, URN = {urn:nbn:de:0030-drops-197698}, doi = {10.4230/LIPIcs.STACS.2024.59}, annote = {Keywords: proof complexity, separations, resolution, extended resolution, blocked clauses} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, and Preetum Nakkiran. Loss Minimization Yields Multicalibration for Large Neural Networks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blasiok_et_al:LIPIcs.ITCS.2024.17, author = {B{\l}asiok, Jaros{\l}aw and Gopalan, Parikshit and Hu, Lunjia and Kalai, Adam Tauman and Nakkiran, Preetum}, title = {{Loss Minimization Yields Multicalibration for Large Neural Networks}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {17:1--17:21}, 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.17}, URN = {urn:nbn:de:0030-drops-195452}, doi = {10.4230/LIPIcs.ITCS.2024.17}, annote = {Keywords: Multi-group fairness, loss minimization, neural networks} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Kevin Pratt. On Generalized Corners and Matrix Multiplication. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{pratt:LIPIcs.ITCS.2024.89, author = {Pratt, Kevin}, title = {{On Generalized Corners and Matrix Multiplication}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {89:1--89: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.89}, URN = {urn:nbn:de:0030-drops-196174}, doi = {10.4230/LIPIcs.ITCS.2024.89}, annote = {Keywords: Algebraic computation, fast matrix multiplication, additive combinatorics} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle down Theorem for Partite Complexes. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.CCC.2023.10, author = {Abdolazimi, Dorna and Oveis Gharan, Shayan}, title = {{An Improved Trickle down Theorem for Partite Complexes}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {10:1--10:16}, 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.10}, URN = {urn:nbn:de:0030-drops-182807}, doi = {10.4230/LIPIcs.CCC.2023.10}, annote = {Keywords: Simplicial complexes, High dimensional expanders, Trickle down theorem, Bounded degree high dimensional expanders, Locally testable codes, Random walks} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7, author = {Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan}, title = {{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.7}, URN = {urn:nbn:de:0030-drops-165695}, doi = {10.4230/LIPIcs.CCC.2022.7}, annote = {Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Ryan O'Donnell and Kevin Pratt. High-Dimensional Expanders from Chevalley Groups. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 18:1-18:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{odonnell_et_al:LIPIcs.CCC.2022.18, author = {O'Donnell, Ryan and Pratt, Kevin}, title = {{High-Dimensional Expanders from Chevalley Groups}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {18:1--18:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.18}, URN = {urn:nbn:de:0030-drops-165802}, doi = {10.4230/LIPIcs.CCC.2022.18}, annote = {Keywords: High-dimensional expanders, simplicial complexes, group theory} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Zander Kelley and Raghu Meka. Random Restrictions and PRGs for PTFs in Gaussian Space. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kelley_et_al:LIPIcs.CCC.2022.21, author = {Kelley, Zander and Meka, Raghu}, title = {{Random Restrictions and PRGs for PTFs in Gaussian Space}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {21:1--21:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.21}, URN = {urn:nbn:de:0030-drops-165836}, doi = {10.4230/LIPIcs.CCC.2022.21}, annote = {Keywords: polynomial threshold function, pseudorandom generator, multivariate gaussian} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.CCC.2022.28, author = {Bansal, Nikhil and Sinha, Makrand and de Wolf, Ronald}, title = {{Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {28:1--28:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.28}, URN = {urn:nbn:de:0030-drops-165908}, doi = {10.4230/LIPIcs.CCC.2022.28}, annote = {Keywords: Aaronson-Ambainis conjecture, Quantum query complexity, Classical query complexity, Free probability, Completely bounded norm, Analysis of Boolean functions, Influence} }
Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Steven T. Flammia. Averaged Circuit Eigenvalue Sampling. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{flammia:LIPIcs.TQC.2022.4, author = {Flammia, Steven T.}, title = {{Averaged Circuit Eigenvalue Sampling}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {4:1--4:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-237-2}, ISSN = {1868-8969}, year = {2022}, volume = {232}, editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.4}, URN = {urn:nbn:de:0030-drops-165114}, doi = {10.4230/LIPIcs.TQC.2022.4}, annote = {Keywords: Quantum noise estimation, quantum benchmarking, QCVV} }
Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman. Memory Compression with Quantum Random-Access Gates. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{buhrman_et_al:LIPIcs.TQC.2022.10, author = {Buhrman, Harry and Loff, Bruno and Patro, Subhasree and Speelman, Florian}, title = {{Memory Compression with Quantum Random-Access Gates}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {10:1--10:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-237-2}, ISSN = {1868-8969}, year = {2022}, volume = {232}, editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.10}, URN = {urn:nbn:de:0030-drops-165177}, doi = {10.4230/LIPIcs.TQC.2022.10}, annote = {Keywords: complexity theory, data structures, algorithms, quantum walk} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, and Xinyu Wu. The SDP Value of Random 2CSPs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 97:1-97:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{musipatla_et_al:LIPIcs.ICALP.2022.97, author = {Musipatla, Amulya and O'Donnell, Ryan and Schramm, Tselil and Wu, Xinyu}, title = {{The SDP Value of Random 2CSPs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {97:1--97:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.97}, URN = {urn:nbn:de:0030-drops-164381}, doi = {10.4230/LIPIcs.ICALP.2022.97}, annote = {Keywords: Random constraint satisfaction problems} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Xinyu Wu. Analyzing XOR-Forrelation Through Stochastic Calculus. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 60:1-60:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{wu:LIPIcs.STACS.2022.60, author = {Wu, Xinyu}, title = {{Analyzing XOR-Forrelation Through Stochastic Calculus}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {60:1--60:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.60}, URN = {urn:nbn:de:0030-drops-158705}, doi = {10.4230/LIPIcs.STACS.2022.60}, annote = {Keywords: quantum complexity, Brownian motion} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani. Explicit Abelian Lifts and Quantum LDPC Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 88:1-88:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{jeronimo_et_al:LIPIcs.ITCS.2022.88, author = {Jeronimo, Fernando Granha and Mittal, Tushant and O'Donnell, Ryan and Paredes, Pedro and Tulsiani, Madhur}, title = {{Explicit Abelian Lifts and Quantum LDPC Codes}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {88:1--88: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.88}, URN = {urn:nbn:de:0030-drops-156846}, doi = {10.4230/LIPIcs.ITCS.2022.88}, annote = {Keywords: Graph lifts, expander graphs, quasi-cyclic LDPC codes, quantum LDPC codes} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Cornelius Brand and Kevin Pratt. Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{brand_et_al:LIPIcs.ICALP.2021.38, author = {Brand, Cornelius and Pratt, Kevin}, title = {{Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {38:1--38:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.38}, URN = {urn:nbn:de:0030-drops-141079}, doi = {10.4230/LIPIcs.ICALP.2021.38}, annote = {Keywords: Parameterized Algorithms, Algebraic Algorithms, Longest Cycle, Matroid Parity} }
Feedback for Dagstuhl Publishing