Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Adam Izdebski and Ronald de Wolf. Improved Quantum Boosting. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 64:1-64:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{izdebski_et_al:LIPIcs.ESA.2023.64, author = {Izdebski, Adam and de Wolf, Ronald}, title = {{Improved Quantum Boosting}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {64:1--64:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.64}, URN = {urn:nbn:de:0030-drops-187178}, doi = {10.4230/LIPIcs.ESA.2023.64}, annote = {Keywords: Learning theory, Boosting algorithms, Quantum computing} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Nikhil S. Mande and Ronald de Wolf. Tight Bounds for Quantum Phase Estimation and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 81:1-81:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{mande_et_al:LIPIcs.ESA.2023.81, author = {Mande, Nikhil S. and de Wolf, Ronald}, title = {{Tight Bounds for Quantum Phase Estimation and Related Problems}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {81:1--81:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.81}, URN = {urn:nbn:de:0030-drops-187346}, doi = {10.4230/LIPIcs.ESA.2023.81}, annote = {Keywords: Phase estimation, quantum computing} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. Improved Hardness Results for the Guided Local Hamiltonian Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 32:1-32:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cade_et_al:LIPIcs.ICALP.2023.32, author = {Cade, Chris and Folkertsma, Marten and Gharibian, Sevag and Hayakawa, Ryu and Le Gall, Fran\c{c}ois and Morimae, Tomoyuki and Weggemans, Jordi}, title = {{Improved Hardness Results for the Guided Local Hamiltonian Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {32:1--32:19}, 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.32}, URN = {urn:nbn:de:0030-drops-180840}, doi = {10.4230/LIPIcs.ICALP.2023.32}, annote = {Keywords: Quantum computing, Quantum advantage, Quantum Chemistry, Guided Local Hamiltonian Problem} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 38:1-38:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.38, author = {Chen, Yanlin and de Wolf, Ronald}, title = {{Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {38:1--38:21}, 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.38}, URN = {urn:nbn:de:0030-drops-180907}, doi = {10.4230/LIPIcs.ICALP.2023.38}, annote = {Keywords: Quantum algorithms, Regularized linear regression, Lasso, Ridge, Lower bounds} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Arjan Cornelissen, Nikhil S. Mande, and Subhasree Patro. Improved Quantum Query Upper Bounds Based on Classical Decision Trees. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 15:1-15:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cornelissen_et_al:LIPIcs.FSTTCS.2022.15, author = {Cornelissen, Arjan and Mande, Nikhil S. and Patro, Subhasree}, title = {{Improved Quantum Query Upper Bounds Based on Classical Decision Trees}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {15:1--15:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.15}, URN = {urn:nbn:de:0030-drops-174071}, doi = {10.4230/LIPIcs.FSTTCS.2022.15}, annote = {Keywords: Quantum Query Complexity, Decision Trees, Decision Tree Rank} }
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 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, and Ronald de Wolf. Symmetry and Quantum Query-To-Communication Simulation. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 20:1-20:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chakraborty_et_al:LIPIcs.STACS.2022.20, author = {Chakraborty, Sourav and Chattopadhyay, Arkadev and H{\o}yer, Peter and Mande, Nikhil S. and Paraashar, Manaswi and de Wolf, Ronald}, title = {{Symmetry and Quantum Query-To-Communication Simulation}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {20:1--20:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.20}, URN = {urn:nbn:de:0030-drops-158309}, doi = {10.4230/LIPIcs.STACS.2022.20}, annote = {Keywords: Classical and quantum communication complexity, query-to-communication-simulation, quantum computing} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Sander Gribling and Harold Nieuwboer. Improved Quantum Lower and Upper Bounds for Matrix Scaling. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 35:1-35:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gribling_et_al:LIPIcs.STACS.2022.35, author = {Gribling, Sander and Nieuwboer, Harold}, title = {{Improved Quantum Lower and Upper Bounds for Matrix Scaling}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {35:1--35:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.35}, URN = {urn:nbn:de:0030-drops-158458}, doi = {10.4230/LIPIcs.STACS.2022.35}, annote = {Keywords: Matrix scaling, quantum algorithms, lower bounds} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{mande_et_al:LIPIcs.STACS.2022.49, author = {Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail}, title = {{One-Way Communication Complexity and Non-Adaptive Decision Trees}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {49:1--49:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49}, URN = {urn:nbn:de:0030-drops-158598}, doi = {10.4230/LIPIcs.STACS.2022.49}, annote = {Keywords: Decision trees, communication complexity, composed Boolean functions} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Simon Apers and Troy Lee. Quantum Complexity of Minimum Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 28:1-28:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{apers_et_al:LIPIcs.CCC.2021.28, author = {Apers, Simon and Lee, Troy}, title = {{Quantum Complexity of Minimum Cut}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {28:1--28:33}, 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.28}, URN = {urn:nbn:de:0030-drops-143026}, doi = {10.4230/LIPIcs.CCC.2021.28}, annote = {Keywords: Quantum algorithms, quantum query complexity, minimum cut} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum Algorithms for Matrix Scaling and Matrix Balancing. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 110:1-110:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{vanapeldoorn_et_al:LIPIcs.ICALP.2021.110, author = {van Apeldoorn, Joran and Gribling, Sander and Li, Yinan and Nieuwboer, Harold and Walter, Michael and de Wolf, Ronald}, title = {{Quantum Algorithms for Matrix Scaling and Matrix Balancing}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {110:1--110:17}, 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.110}, URN = {urn:nbn:de:0030-drops-141793}, doi = {10.4230/LIPIcs.ICALP.2021.110}, annote = {Keywords: Matrix scaling, matrix balancing, quantum algorithms} }
Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Joran van Apeldoorn. Quantum Probability Oracles & Multidimensional Amplitude Estimation. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 9:1-9:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{vanapeldoorn:LIPIcs.TQC.2021.9, author = {van Apeldoorn, Joran}, title = {{Quantum Probability Oracles \& Multidimensional Amplitude Estimation}}, booktitle = {16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)}, pages = {9:1--9:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-198-6}, ISSN = {1868-8969}, year = {2021}, volume = {197}, editor = {Hsieh, Min-Hsiu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.9}, URN = {urn:nbn:de:0030-drops-140046}, doi = {10.4230/LIPIcs.TQC.2021.9}, annote = {Keywords: quantum algorithms, amplitude estimation, monte carlo} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{buhrman_et_al:LIPIcs.STACS.2021.19, author = {Buhrman, Harry and Patro, Subhasree and Speelman, Florian}, title = {{A Framework of Quantum Strong Exponential-Time Hypotheses}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {19:1--19:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.19}, URN = {urn:nbn:de:0030-drops-136642}, doi = {10.4230/LIPIcs.STACS.2021.19}, annote = {Keywords: complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 53:1-53:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{garg_et_al:LIPIcs.ITCS.2021.53, author = {Garg, Ankit and Kothari, Robin and Netrapalli, Praneeth and Sherif, Suhail}, title = {{No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {53:1--53:20}, 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.53}, URN = {urn:nbn:de:0030-drops-135921}, doi = {10.4230/LIPIcs.ITCS.2021.53}, annote = {Keywords: Quantum algorithms, Gradient descent, Convex optimization} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 47:1-47:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chia_et_al:LIPIcs.ISAAC.2020.47, author = {Chia, Nai-Hui and Gily\'{e}n, Andr\'{a}s and Lin, Han-Hsuan and Lloyd, Seth and Tang, Ewin and Wang, Chunhao}, title = {{Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {47:1--47:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.47}, URN = {urn:nbn:de:0030-drops-133916}, doi = {10.4230/LIPIcs.ISAAC.2020.47}, annote = {Keywords: sublinear algorithms, quantum-inspired, regression, importance sampling, quantum machine learning} }
Feedback for Dagstuhl Publishing