LIPIcs, Volume 264
CCC 2023, July 17-20, 2023, Warwick, UK
Editors: Amnon Ta-Shma
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 1-936, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Proceedings{tashma:LIPIcs.CCC.2023, title = {{LIPIcs, Volume 264, CCC 2023, Complete Volume}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {1--936}, 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}, URN = {urn:nbn:de:0030-drops-182690}, doi = {10.4230/LIPIcs.CCC.2023}, annote = {Keywords: LIPIcs, Volume 264, CCC 2023, Complete Volume} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 0:i-0:xiv, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{tashma:LIPIcs.CCC.2023.0, author = {Ta-Shma, Amnon}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {0:i--0:xiv}, 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.0}, URN = {urn:nbn:de:0030-drops-182703}, doi = {10.4230/LIPIcs.CCC.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley. Separation of the Factorization Norm and Randomized Communication Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 1:1-1:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cheung_et_al:LIPIcs.CCC.2023.1, author = {Cheung, Tsun-Ming and Hatami, Hamed and Hosseini, Kaave and Shirley, Morgan}, title = {{Separation of the Factorization Norm and Randomized Communication Complexity}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {1:1--1: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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.1}, URN = {urn:nbn:de:0030-drops-182714}, doi = {10.4230/LIPIcs.CCC.2023.1}, annote = {Keywords: Factorization norms, randomized communication complexity} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj. Border Complexity of Symbolic Determinant Under Rank One Restriction. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 2:1-2:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.2, author = {Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan}, title = {{Border Complexity of Symbolic Determinant Under Rank One Restriction}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {2:1--2:15}, 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.2}, URN = {urn:nbn:de:0030-drops-182721}, doi = {10.4230/LIPIcs.CCC.2023.2}, annote = {Keywords: Border Complexity, Symbolic Determinant, Valuated Matroid} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Peter Ivanov, Liam Pavlovic, and Emanuele Viola. On Correlation Bounds Against Polynomials. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 3:1-3:35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ivanov_et_al:LIPIcs.CCC.2023.3, author = {Ivanov, Peter and Pavlovic, Liam and Viola, Emanuele}, title = {{On Correlation Bounds Against Polynomials}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {3:1--3:35}, 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.3}, URN = {urn:nbn:de:0030-drops-182734}, doi = {10.4230/LIPIcs.CCC.2023.3}, annote = {Keywords: Correlation bounds, Polynomials} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She. On the Algebraic Proof Complexity of Tensor Isomorphism. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 4:1-4:40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{galesi_et_al:LIPIcs.CCC.2023.4, author = {Galesi, Nicola and Grochow, Joshua A. and Pitassi, Toniann and She, Adrian}, title = {{On the Algebraic Proof Complexity of Tensor Isomorphism}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {4:1--4:40}, 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.4}, URN = {urn:nbn:de:0030-drops-182748}, doi = {10.4230/LIPIcs.CCC.2023.4}, annote = {Keywords: Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Lunjia Hu, Inbal Rachel Livni Navon, and Omer Reingold. Generative Models of Huge Objects. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hu_et_al:LIPIcs.CCC.2023.5, author = {Hu, Lunjia and Livni Navon, Inbal Rachel and Reingold, Omer}, title = {{Generative Models of Huge Objects}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {5:1--5:20}, 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.5}, URN = {urn:nbn:de:0030-drops-182758}, doi = {10.4230/LIPIcs.CCC.2023.5}, annote = {Keywords: pseudorandomness, generative models, regularity lemma} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 6:1-6:45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2023.6, author = {Hirahara, Shuichi and Lu, Zhenjian and Ren, Hanlin}, title = {{Bounded Relativization}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {6:1--6:45}, 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.6}, URN = {urn:nbn:de:0030-drops-182764}, doi = {10.4230/LIPIcs.CCC.2023.6}, annote = {Keywords: relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Russell Impagliazzo, Sasank Mouli, and Toniann Pitassi. Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 7:1-7:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{impagliazzo_et_al:LIPIcs.CCC.2023.7, author = {Impagliazzo, Russell and Mouli, Sasank and Pitassi, Toniann}, title = {{Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {7:1--7:24}, 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.7}, URN = {urn:nbn:de:0030-drops-182774}, doi = {10.4230/LIPIcs.CCC.2023.7}, annote = {Keywords: Proof complexity, Algebraic proof systems, Polynomial Calculus, Extension variables, AC⁰\lbrackp\rbrack-Frege} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Gil Cohen and Itay Cohen. Spectral Expanding Expanders. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 8:1-8:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.CCC.2023.8, author = {Cohen, Gil and Cohen, Itay}, title = {{Spectral Expanding Expanders}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {8:1--8:19}, 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.8}, URN = {urn:nbn:de:0030-drops-182780}, doi = {10.4230/LIPIcs.CCC.2023.8}, annote = {Keywords: Expanders, Normalized Random Walk, Spectral Analysis} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Eshan Chattopadhyay and Jyun-Jie Liao. Hardness Against Linear Branching Programs and More. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 9:1-9:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2023.9, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Hardness Against Linear Branching Programs and More}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {9:1--9:27}, 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.9}, URN = {urn:nbn:de:0030-drops-182794}, doi = {10.4230/LIPIcs.CCC.2023.9}, annote = {Keywords: linear branching programs, circuit lower bound, sumset extractors, hitting sets} }
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.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 264, 38th Computational Complexity Conference (CCC 2023)
Dean Doron and Roei Tell. Derandomization with Minimal Memory Footprint. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 11:1-11:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{doron_et_al:LIPIcs.CCC.2023.11, author = {Doron, Dean and Tell, Roei}, title = {{Derandomization with Minimal Memory Footprint}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {11:1--11:15}, 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.11}, URN = {urn:nbn:de:0030-drops-182816}, doi = {10.4230/LIPIcs.CCC.2023.11}, annote = {Keywords: derandomization, space-bounded computation, catalytic space} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12, author = {Goldberg, Halley and Kabanets, Valentine}, title = {{Improved Learning from Kolmogorov Complexity}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {12:1--12:29}, 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.12}, URN = {urn:nbn:de:0030-drops-182825}, doi = {10.4230/LIPIcs.CCC.2023.12}, annote = {Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity} }
Feedback for Dagstuhl Publishing