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 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} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Amitabh Basu, Michael Dinitz, and Xin Li. Computing Approximate PSD Factorizations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{basu_et_al:LIPIcs.APPROX-RANDOM.2016.2, author = {Basu, Amitabh and Dinitz, Michael and Li, Xin}, title = {{Computing Approximate PSD Factorizations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {2:1--2:12}, 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.2}, URN = {urn:nbn:de:0030-drops-66258}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.2}, annote = {Keywords: PSD rank, PSD factorizations} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bliznets_et_al:LIPIcs.APPROX-RANDOM.2016.3, author = {Bliznets, Ivan and Cygan, Marek and Komosa, Pawel and Pilipczuk, Michal}, title = {{Hardness of Approximation for H-Free Edge Modification Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {3:1--3:17}, 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.3}, URN = {urn:nbn:de:0030-drops-66260}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.3}, annote = {Keywords: hardness of approximation, parameterized complexity, kernelization, edge modification problems} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Moses Charikar, Yonatan Naamad, and Anthony Wirth. On Approximating Target Set Selection. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{charikar_et_al:LIPIcs.APPROX-RANDOM.2016.4, author = {Charikar, Moses and Naamad, Yonatan and Wirth, Anthony}, title = {{On Approximating Target Set Selection}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {4:1--4:16}, 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.4}, URN = {urn:nbn:de:0030-drops-66274}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.4}, annote = {Keywords: target set selection, influence propagation, approximation algorithms, hardness of approximation, planted dense subgraph} }
Feedback for Dagstuhl Publishing