LIPIcs, Volume 60
APPROX/RANDOM 2016, September 7-9, 2016, Paris, France
Editors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans. Finite Matrix Multiplication Algorithms from Infinite Groups. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{blasiak_et_al:LIPIcs.ITCS.2025.18, author = {Blasiak, Jonah and Cohn, Henry and Grochow, Joshua A. and Pratt, Kevin and Umans, Chris}, title = {{Finite Matrix Multiplication Algorithms from Infinite Groups}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {18:1--18:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.18}, URN = {urn:nbn:de:0030-drops-226460}, doi = {10.4230/LIPIcs.ITCS.2025.18}, annote = {Keywords: Fast matrix multiplication, representation theory, infinite groups} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Yakov Shalunov. Leakage-Resilient Hardness Equivalence to Logspace Derandomization. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 83:1-83:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{shalunov:LIPIcs.MFCS.2024.83, author = {Shalunov, Yakov}, title = {{Leakage-Resilient Hardness Equivalence to Logspace Derandomization}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {83:1--83:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.83}, URN = {urn:nbn:de:0030-drops-206395}, doi = {10.4230/LIPIcs.MFCS.2024.83}, annote = {Keywords: Derandomization, logspace computation, leakage-resilient hardness, psuedorandom generators} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148, author = {Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael}, title = {{An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {148:1--148:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.148}, URN = {urn:nbn:de:0030-drops-202912}, doi = {10.4230/LIPIcs.ICALP.2024.148}, annote = {Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ohad Klein, Joseph Slote, Alexander Volberg, and Haonan Zhang. Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{klein_et_al:LIPIcs.ITCS.2024.69, author = {Klein, Ohad and Slote, Joseph and Volberg, Alexander and Zhang, Haonan}, title = {{Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {69:1--69:22}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.69}, URN = {urn:nbn:de:0030-drops-195977}, doi = {10.4230/LIPIcs.ITCS.2024.69}, annote = {Keywords: Analysis of Boolean Functions, Remez Inequality, Bohnenblust-Hille Inequality, Statistical Learning Theory, Qudits} }
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.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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Joseph Slote. Parity vs. AC0 with Simple Quantum Preprocessing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 92:1-92:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{slote:LIPIcs.ITCS.2024.92, author = {Slote, Joseph}, title = {{Parity vs. AC0 with Simple Quantum Preprocessing}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {92:1--92: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.92}, URN = {urn:nbn:de:0030-drops-196209}, doi = {10.4230/LIPIcs.ITCS.2024.92}, annote = {Keywords: QNC0, AC0, Nonlocal games, k-wise indistinguishability, approximate degree, switching lemma, Fourier concentration} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 17:1-17:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2023.17, author = {van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas}, title = {{Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {17:1--17:36}, 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.17}, URN = {urn:nbn:de:0030-drops-182870}, doi = {10.4230/LIPIcs.CCC.2023.17}, annote = {Keywords: Hardness versus randomness tradeoff, Arthur-Merlin protocol, targeted hitting set generator} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans. Matrix Multiplication via Matrix Groups. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blasiak_et_al:LIPIcs.ITCS.2023.19, author = {Blasiak, Jonah and Cohn, Henry and Grochow, Joshua A. and Pratt, Kevin and Umans, Chris}, title = {{Matrix Multiplication via Matrix Groups}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {19:1--19:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.19}, URN = {urn:nbn:de:0030-drops-175226}, doi = {10.4230/LIPIcs.ITCS.2023.19}, annote = {Keywords: Fast matrix multiplication, representation theory, matrix groups} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC^0[p] Lower Bounds Against MCSP via the Coin Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{golovnev_et_al:LIPIcs.ICALP.2019.66, author = {Golovnev, Alexander and Ilango, Rahul and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina and Tal, Avishay}, title = {{AC^0\lbrackp\rbrack Lower Bounds Against MCSP via the Coin Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {66:1--66:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.66}, URN = {urn:nbn:de:0030-drops-106422}, doi = {10.4230/LIPIcs.ICALP.2019.66}, annote = {Keywords: Minimum Circuit Size Problem (MCSP), circuit lower bounds, AC0\lbrackp\rbrack, coin problem, hybrid argument, MKTP, biased random boolean functions} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Chloe Ching-Yun Hsu and Chris Umans. On Multidimensional and Monotone k-SUM. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{hsu_et_al:LIPIcs.MFCS.2017.50, author = {Hsu, Chloe Ching-Yun and Umans, Chris}, title = {{On Multidimensional and Monotone k-SUM}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {50:1--50:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.50}, URN = {urn:nbn:de:0030-drops-80618}, doi = {10.4230/LIPIcs.MFCS.2017.50}, annote = {Keywords: 3SUM, kSUM, monotone 3SUM, strong 3SUM conjecture} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Proceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2016, title = {{LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016}, URN = {urn:nbn:de:0030-drops-66809}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016}, annote = {Keywords: Theory of Computation, Models of Computation, Modes of Computation – Online Computation, Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Numerical Algorithms and Problems – Computations on Matrices, Nonnumerical Algorithms and Problems} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2016.0, author = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, title = {{Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.0}, URN = {urn:nbn:de:0030-drops-66235}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Arturs Backurs and Anastasios Sidiropoulos. Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{backurs_et_al:LIPIcs.APPROX-RANDOM.2016.1, author = {Backurs, Arturs and Sidiropoulos, Anastasios}, title = {{Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l\underlinep Spaces}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {1:1--1:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.1}, URN = {urn:nbn:de:0030-drops-66241}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.1}, annote = {Keywords: metric embeddings, Hausdorff metric, distortion, dimension} }
Feedback for Dagstuhl Publishing