„Query complexity“

Suchergebnisse

263 Treffer

• Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge
  Ben-David, Shalev ; Kothari, Robin 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Querying a Matrix Through Matrix-Vector Products
  Sun, Xiaoming ; Woodruff, David P. ; Yang, Guang ; Zhang, Jialin 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity
  Gavinsky, Dmitry ; Lee, Troy ; Santha, Miklos ; Sanyal, Swagato 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A ZPP^NP[1] Lifting Theorem
  Watson, Thomas 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Lifting Theorems for Equality
  Loff, Bruno ; Mukhopadhyay, Sagnik 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers
  Bishnu, Arijit ; Ghosh, Arijit ; Kolay, Sudeshna ; Mishra, Gopinath ; Saurabh, Saket 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
  Belovs, Aleksandrs ; Rosmanis, Ansis 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Querying the Unary Negation Fragment with Regular Path Expressions
  Jung, Jean Christoph ; Lutz, Carsten ; Martel, Mauricio ; Schneider, Thomas 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Rewriting Guarded Existential Rules into Small Datalog Programs
  Ahmetaj, Shqiponja ; Ortiz, Magdalena ; Simkus, Mantas 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Lower Bounds on Black-Box Reductions of Hitting to Density Estimation
  Tell, Roei 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• All Classical Adversary Methods are Equivalent for Total Functions
  Ambainis, Andris ; Kokainis, Martins ; Prusis, Krisjanis ; Vihrovs, Jevgenijs 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Computing Exact Minimum Cuts Without Knowing the Graph
  Rubinstein, Aviad ; Schramm, Tselil ; Weinberg, S. Matthew 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Composition Theorem for Randomized Query Complexity
  Anshu, Anurag ; Gavinsky, Dmitry ; Jain, Rahul ; Kundu, Srijita ; Lee, Troy ; Mukhopadhyay, Priyanka ; Santha, Miklos ; Sanyal, Swagato 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Ontology-Mediated Query Answering over Temporal Data: A Survey (Invited Talk)
  Artale, Alessandro ; Kontchakov, Roman ; Kovtunova, Alisa ; Ryzhikov, Vladislav ; Wolter, Frank ; Zakharyaschev, Michael 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Interactive Oracle Proofs with Constant Rate and Query Complexity
  Ben-Sasson, Eli ; Chiesa, Alessandro ; Gabizon, Ariel ; Riabzev, Michael ; Spooner, Nicholas 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Settling the Query Complexity of Non-Adaptive Junta Testing
  Chen, Xi ; Servedio, Rocco A. ; Tan, Li-Yang ; Waingarten, Erik ; Xie, Jinyu 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Query-to-Communication Lifting for P^NP
  Göös, Mika ; Kamath, Pritish ; Pitassi, Toniann ; Watson, Thomas 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Ham Sandwich is Equivalent to Borsuk-Ulam
  C. S., Karthik ; Saha, Arpan 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games
  Chen, Xi ; Cheng, Yu ; Tang, Bo 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Low-Sensitivity Functions from Unambiguous Certificates
  Ben-David, Shalev ; Hatami, Pooya ; Tal, Avishay 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik