Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, and Carlos Palazuelos. Learning Low-Degree Quantum Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2024.13, author = {Arunachalam, Srinivasan and Dutt, Arkopal and Escudero Guti\'{e}rrez, Francisco and Palazuelos, Carlos}, title = {{Learning Low-Degree Quantum Objects}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {13:1--13:19}, 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.13}, URN = {urn:nbn:de:0030-drops-201563}, doi = {10.4230/LIPIcs.ICALP.2024.13}, annote = {Keywords: Tomography} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 105:1-105:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lee_et_al:LIPIcs.ICALP.2024.105, author = {Lee, Eunou and Parekh, Ojas}, title = {{An Improved Quantum Max Cut Approximation via Maximum Matching}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {105:1--105:11}, 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.105}, URN = {urn:nbn:de:0030-drops-202482}, doi = {10.4230/LIPIcs.ICALP.2024.105}, annote = {Keywords: approximation, optimization, local Hamiltonian, rounding, SDP, matching} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{groenland_et_al:LIPIcs.ICALP.2024.77, author = {Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {77:1--77:21}, 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.77}, URN = {urn:nbn:de:0030-drops-202208}, doi = {10.4230/LIPIcs.ICALP.2024.77}, annote = {Keywords: graph homomorphism, cutwidth, asymptotic matrix parameters} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, and Jeroen Zuiddam. Discreteness of Asymptotic Tensor Ranks (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{briet_et_al:LIPIcs.ITCS.2024.20, author = {Bri\"{e}t, Jop and Christandl, Matthias and Leigh, Itai and Shpilka, Amir and Zuiddam, Jeroen}, title = {{Discreteness of Asymptotic Tensor Ranks}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {20:1--20:14}, 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.20}, URN = {urn:nbn:de:0030-drops-195483}, doi = {10.4230/LIPIcs.ITCS.2024.20}, annote = {Keywords: Tensors, Asymptotic rank, Subrank, Slice rank, Restriction, Degeneration, Diagonalization, SLOCC} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M. P. Neumann. Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 21:1-21:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{briet_et_al:LIPIcs.ITCS.2024.21, author = {Bri\"{e}t, Jop and Buhrman, Harry and Castro-Silva, Davi and Neumann, Niels M. P.}, title = {{Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {21:1--21:11}, 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.21}, URN = {urn:nbn:de:0030-drops-195490}, doi = {10.4230/LIPIcs.ITCS.2024.21}, annote = {Keywords: Coding theory, circuit complexity, quantum complexity theory, higher-order Fourier analysis, non-local games} }
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.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)
Jop Briët and Francisco Escudero Gutiérrez. On Converses to the Polynomial Method. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{briet_et_al:LIPIcs.TQC.2022.6, author = {Bri\"{e}t, Jop and Escudero Guti\'{e}rrez, Francisco}, title = {{On Converses to the Polynomial Method}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {6:1--6: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.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.6}, URN = {urn:nbn:de:0030-drops-165139}, doi = {10.4230/LIPIcs.TQC.2022.6}, annote = {Keywords: Quantum query complexity, polynomial method, completely bounded polynomials} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Jop Briët and Farrokh Labib. High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 76:1-76:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{briet_et_al:LIPIcs.ITCS.2021.76, author = {Bri\"{e}t, Jop and Labib, Farrokh}, title = {{High-Entropy Dual Functions and Locally Decodable Codes}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {76:1--76:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.76}, URN = {urn:nbn:de:0030-drops-136157}, doi = {10.4230/LIPIcs.ITCS.2021.76}, annote = {Keywords: Higher-order Fourier analysis, dual functions, finite fields, additive combinatorics, coding theory} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Tom Bannink, Jop Briët, Farrokh Labib, and Hans Maassen. Quasirandom Quantum Channels. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bannink_et_al:LIPIcs.TQC.2020.5, author = {Bannink, Tom and Bri\"{e}t, Jop and Labib, Farrokh and Maassen, Hans}, title = {{Quasirandom Quantum Channels}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.5}, URN = {urn:nbn:de:0030-drops-120642}, doi = {10.4230/LIPIcs.TQC.2020.5}, annote = {Keywords: Quantum channels, quantum expanders, quasirandomness} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45, author = {Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald}, title = {{Improved Bounds on Fourier Entropy and Min-Entropy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45}, URN = {urn:nbn:de:0030-drops-119062}, doi = {10.4230/LIPIcs.STACS.2020.45}, annote = {Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba. On Quantum Chosen-Ciphertext Attacks and Learning with Errors. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alagic_et_al:LIPIcs.TQC.2019.1, author = {Alagic, Gorjan and Jeffery, Stacey and Ozols, Maris and Poremba, Alexander}, title = {{On Quantum Chosen-Ciphertext Attacks and Learning with Errors}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {1:1--1:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.1}, URN = {urn:nbn:de:0030-drops-103939}, doi = {10.4230/LIPIcs.TQC.2019.1}, annote = {Keywords: quantum chosen-ciphertext security, quantum attacks, learning with errors} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee. Bounding Quantum-Classical Separations for Classes of Nonlocal Games. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bannink_et_al:LIPIcs.STACS.2019.12, author = {Bannink, Tom and Bri\"{e}t, Jop and Buhrman, Harry and Labib, Farrokh and Lee, Troy}, title = {{Bounding Quantum-Classical Separations for Classes of Nonlocal Games}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {12:1--12:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.12}, URN = {urn:nbn:de:0030-drops-102512}, doi = {10.4230/LIPIcs.STACS.2019.12}, annote = {Keywords: Nonlocal games, communication complexity, bounded separations, semidefinite programming, pseudorandomness, Gowers norms} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum Query Algorithms are Completely Bounded Forms. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2018.3, author = {Arunachalam, Srinivasan and Bri\"{e}t, Jop and Palazuelos, Carlos}, title = {{Quantum Query Algorithms are Completely Bounded Forms}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {3:1--3:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.3}, URN = {urn:nbn:de:0030-drops-83383}, doi = {10.4230/LIPIcs.ITCS.2018.3}, annote = {Keywords: Quantum query algorithms, operator space theory, polynomial method, approximate degree.} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Jop Briët, Zeev Dvir, and Sivakanth Gopi. Outlaw Distributions and Locally Decodable Codes. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{briet_et_al:LIPIcs.ITCS.2017.20, author = {Bri\"{e}t, Jop and Dvir, Zeev and Gopi, Sivakanth}, title = {{Outlaw Distributions and Locally Decodable Codes}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {20:1--20:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.20}, URN = {urn:nbn:de:0030-drops-81888}, doi = {10.4230/LIPIcs.ITCS.2017.20}, annote = {Keywords: Locally Decodable Code, VC-dimension, Incidence Geometry, Cayley Hypergraphs} }
Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman. Round Elimination in Exact Communication Complexity. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 206-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{briet_et_al:LIPIcs.TQC.2015.206, author = {Bri\"{e}t, Jop and Buhrman, Harry and Leung, Debbie and Piovesan, Teresa and Speelman, Florian}, title = {{Round Elimination in Exact Communication Complexity}}, booktitle = {10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)}, pages = {206--225}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-96-5}, ISSN = {1868-8969}, year = {2015}, volume = {44}, editor = {Beigi, Salman and K\"{o}nig, Robert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.206}, URN = {urn:nbn:de:0030-drops-55588}, doi = {10.4230/LIPIcs.TQC.2015.206}, annote = {Keywords: communication complexity, round elimination, quantum communication, protocols, chromatic numbers} }