„Query complexity“

Suchergebnisse

263 Treffer

• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
  Ambainis, Andris ; Balodis, Kaspars ; Iraids, Jānis ; Khadiev, Kamil ; Kļevickis, Vladislavs ; Prūsis, Krišjānis ; Shen, Yixin ; Smotrovs, Juris ; Vihrovs, Jevgēnijs 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead
  Chakraborty, Sourav ; Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Paraashar, Manaswi 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
  Aaronson, Scott ; Kothari, Robin ; Kretschmer, William ; Thaler, Justin 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity
  Pitassi, Toniann ; Shirley, Morgan ; Watson, Thomas 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Quantum Distributed Complexity of Set Disjointness on a Line
  Magniez, Frédéric ; Nayak, Ashwin 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
  Chen, Yu ; Kannan, Sampath ; Khanna, Sanjeev 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• The Power of Many Samples in Query Complexity
  Bassilakis, Andrew ; Drucker, Andrew ; Göös, Mika ; Hu, Lunjia ; Ma, Weiyun ; Tan, Li-Yang 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Lower Bounds for Function Inversion with Quantum Advice
  Chung, Kai-Min ; Liao, Tai-Ning ; Qian, Luowen 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Improved Approximate Degree Bounds for k-Distinctness
  Mande, Nikhil S. ; Thaler, Justin ; Zhu, Shuchen 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Improved Bounds on Fourier Entropy and Min-Entropy
  Arunachalam, Srinivasan ; Chakraborty, Sourav ; Koucký, Michal ; Saurabh, Nitin ; de Wolf, Ronald 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Tight Lower Bound For Non-Coherent Index Erasure
  Lindzey, Nathan ; Rosmanis, Ansis 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Instance Complexity and Unlabeled Certificates in the Decision Tree Model
  Grossman, Tomer ; Komargodski, Ilan ; Naor, Moni 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Distributional Property Testing in a Quantum World
  Gilyén, András ; Li, Tongyang 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Triangle Estimation Using Tripartite Independent Set Queries
  Bhattacharya, Anup ; Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Single-Elimination Brackets Fail to Approximate Copeland Winner
  Hulett, Reyna 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• The Query Complexity of Mastermind with l_p Distances
  Fernández V, Manuel ; Woodruff, David P. ; Yasuda, Taisuke 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Quantum Algorithms for Classical Probability Distributions
  Belovs, Aleksandrs 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Query-Competitive Sorting with Uncertainty
  Halldórsson, Magnús M. ; de Lima, Murilo Santos 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Optimal Separation and Strong Direct Sum for Randomized Query Complexity
  Blais, Eric ; Brody, Joshua 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Applications of the Quantum Algorithm for st-Connectivity
  DeLorenzo, Kai ; Kimmel, Shelby ; Witter, R. Teal 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik