Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 11:1-11:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bassirian_et_al:LIPIcs.TQC.2023.11, author = {Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal}, title = {{On the Power of Nonstandard Quantum Oracles}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {11:1--11:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-283-9}, ISSN = {1868-8969}, year = {2023}, volume = {266}, editor = {Fawzi, Omar and Walter, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.11}, URN = {urn:nbn:de:0030-drops-183215}, doi = {10.4230/LIPIcs.TQC.2023.11}, annote = {Keywords: quantum complexity, QCMA, expander graphs, representation theory} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Ellipsoid Fitting up to a Constant. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 78:1-78:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hsieh_et_al:LIPIcs.ICALP.2023.78, author = {Hsieh, Jun-Ting and Kothari, Pravesh K. and Potechin, Aaron and Xu, Jeff}, title = {{Ellipsoid Fitting up to a Constant}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {78:1--78:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.78}, URN = {urn:nbn:de:0030-drops-181304}, doi = {10.4230/LIPIcs.ICALP.2023.78}, annote = {Keywords: Semidefinite programming, random matrices, average-case complexity} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
James Cook and Ian Mertz. Trading Time and Space in Catalytic Branching Programs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 8:1-8:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cook_et_al:LIPIcs.CCC.2022.8, author = {Cook, James and Mertz, Ian}, title = {{Trading Time and Space in Catalytic Branching Programs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.8}, URN = {urn:nbn:de:0030-drops-165708}, doi = {10.4230/LIPIcs.CCC.2022.8}, annote = {Keywords: complexity theory, branching programs, amortized, space complexity, catalytic computation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43, author = {Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon}, title = {{Expander Random Walks: The General Case and Limitations}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {43:1--43:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43}, URN = {urn:nbn:de:0030-drops-163849}, doi = {10.4230/LIPIcs.ICALP.2022.43}, annote = {Keywords: Expander Graphs, Random Walks, Lower Bounds} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Chris Jones and Aaron Potechin. Almost-Orthogonal Bases for Inner Product Polynomials. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 89:1-89:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{jones_et_al:LIPIcs.ITCS.2022.89, author = {Jones, Chris and Potechin, Aaron}, title = {{Almost-Orthogonal Bases for Inner Product Polynomials}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {89:1--89: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.89}, URN = {urn:nbn:de:0030-drops-156853}, doi = {10.4230/LIPIcs.ITCS.2022.89}, annote = {Keywords: Orthogonal polynomials, Fourier analysis, combinatorics} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Shuo Pang. SOS Lower Bound for Exact Planted Clique. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 26:1-26:63, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{pang:LIPIcs.CCC.2021.26, author = {Pang, Shuo}, title = {{SOS Lower Bound for Exact Planted Clique}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {26:1--26:63}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.26}, URN = {urn:nbn:de:0030-drops-143000}, doi = {10.4230/LIPIcs.CCC.2021.26}, annote = {Keywords: Sum-of-Squares, planted clique, random graphs, average-case lower bound} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Adam Kurpisz, Aaron Potechin, and Elias Samuel Wirth. SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 90:1-90:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kurpisz_et_al:LIPIcs.ICALP.2021.90, author = {Kurpisz, Adam and Potechin, Aaron and Wirth, Elias Samuel}, title = {{SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {90:1--90:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.90}, URN = {urn:nbn:de:0030-drops-141595}, doi = {10.4230/LIPIcs.ICALP.2021.90}, annote = {Keywords: symmetric quadratic functions, SoS certificate, hypercube optimization, semidefinite programming} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Neng Huang and Aaron Potechin. On the Approximability of Presidential Type Predicates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 58:1-58:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2020.58, author = {Huang, Neng and Potechin, Aaron}, title = {{On the Approximability of Presidential Type Predicates}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {58:1--58:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.58}, URN = {urn:nbn:de:0030-drops-126612}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.58}, annote = {Keywords: constraint satisfaction problems, approximation algorithms, presidential type predicates} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Aaron Potechin. Sum of Squares Bounds for the Ordering Principle. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 38:1-38:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{potechin:LIPIcs.CCC.2020.38, author = {Potechin, Aaron}, title = {{Sum of Squares Bounds for the Ordering Principle}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {38:1--38:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.38}, URN = {urn:nbn:de:0030-drops-125900}, doi = {10.4230/LIPIcs.CCC.2020.38}, annote = {Keywords: sum of squares hierarchy, proof complexity, ordering principle} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Susanna F. de Rezende, Jakob Nordström, Or Meir, and Robert Robere. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{derezende_et_al:LIPIcs.CCC.2019.18, author = {de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Meir, Or and Robere, Robert}, title = {{Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {18:1--18:16}, 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.18}, URN = {urn:nbn:de:0030-drops-108403}, doi = {10.4230/LIPIcs.CCC.2019.18}, annote = {Keywords: proof complexity, Nullstellensatz, pebble games, trade-offs, size, degree} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Albert Atserias and Tuomas Hakoniemi. Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{atserias_et_al:LIPIcs.CCC.2019.24, author = {Atserias, Albert and Hakoniemi, Tuomas}, title = {{Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {24:1--24:20}, 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.24}, URN = {urn:nbn:de:0030-drops-108464}, doi = {10.4230/LIPIcs.CCC.2019.24}, annote = {Keywords: Proof complexity, semialgebraic proof systems, Sums-of-Squares, Positivstellensatz, trade-offs, lower bounds, monomial size, degree} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Ryan O'Donnell and Tselil Schramm. Sherali - Adams Strikes Back. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{odonnell_et_al:LIPIcs.CCC.2019.8, author = {O'Donnell, Ryan and Schramm, Tselil}, title = {{Sherali - Adams Strikes Back}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {8:1--8:30}, 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.8}, URN = {urn:nbn:de:0030-drops-108309}, doi = {10.4230/LIPIcs.CCC.2019.8}, annote = {Keywords: Linear programming, Sherali, Adams, max-cut, graph eigenvalues, Sum-of-Squares} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Aaron Potechin. Sum of Squares Lower Bounds from Symmetry and a Good Story. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 61:1-61:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{potechin:LIPIcs.ITCS.2019.61, author = {Potechin, Aaron}, title = {{Sum of Squares Lower Bounds from Symmetry and a Good Story}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {61:1--61:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.61}, URN = {urn:nbn:de:0030-drops-101545}, doi = {10.4230/LIPIcs.ITCS.2019.61}, annote = {Keywords: Sum of squares hierarchy, proof complexity, graph theory, lower bounds} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Aaron Potechin. A Note on Amortized Branching Program Complexity. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 4:1-4:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{potechin:LIPIcs.CCC.2017.4, author = {Potechin, Aaron}, title = {{A Note on Amortized Branching Program Complexity}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.4}, URN = {urn:nbn:de:0030-drops-75448}, doi = {10.4230/LIPIcs.CCC.2017.4}, annote = {Keywords: branching programs, space complexity, amortization} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Dhruv Medarametla and Aaron Potechin. Bounds on the Norms of Uniform Low Degree Graph Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 40:1-40:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{medarametla_et_al:LIPIcs.APPROX-RANDOM.2016.40, author = {Medarametla, Dhruv and Potechin, Aaron}, title = {{Bounds on the Norms of Uniform Low Degree Graph Matrices}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {40:1--40:26}, 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.40}, URN = {urn:nbn:de:0030-drops-66638}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.40}, annote = {Keywords: sum of squares hierarchy, matrix norm bounds} }
Feedback for Dagstuhl Publishing