On the fine-grained query complexity of symmetric functions
From MaRDI portal
Cites work
- A note on quantum algorithms and the minimal degree of -error polynomials for symmetric functions
- A note on the quantum query complexity of permutation symmetric functions
- A quantum advantage for a natural streaming problem
- An optimal separation of randomized and Quantum query complexity
- Approximate inclusion-exclusion for arbitrary symmetric functions
- Complexity measures and decision tree complexity: a survey.
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Exponential separations between learning with and without quantum memory
- Forrelation: a problem that optimally separates quantum from classical computing
- Fractional certificates for bounded functions
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 6789291 (Why is no real title available?)
- Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond
- k-forrelation optimally separates Quantum and classical query complexity
- Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
- On exact quantum query complexity
- On the fine-grained query complexity of symmetric functions
- On the sum of the L₁ influences of bounded functions
- Quantum advantage with noisy shallow circuits in 3D
- Quantum cryptanalysis of hash and claw-free functions
- Quantum lower bounds by polynomials
- Quantum lower bounds for approximate counting via Laurent polynomials
- Quantum vs. classical proofs and subset verification
- Rapid solution of problems by quantum computation
- Revisiting Deutsch-Jozsa algorithm
- Symmetries, graph properties, and quantum speedups
- The need for structure in quantum speedups
- The structure of promises in quantum speedups
- Towards optimal separations between quantum and randomized query complexities
- Unbounded-Error Classical and Quantum Communication Complexity
- Unbounded-Error One-Way Classical and Quantum Communication Complexity
- Unbounded-Error Quantum Query Complexity
- Verifiable quantum advantage without structure
This page was built for publication: On the fine-grained query complexity of symmetric functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953159)
