:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Yuan, Wu, Haowei, Yang, Yi
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2403.03530
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Between the deterministic and non-deterministic query complexity
di: Gerbner, Dániel
Pubblicazione: (2019)

On query complexity measures and their relations for symmetric functions
di: Mittal, Rajat, et al.
Pubblicazione: (2021)

Quantum and classical query complexities of functions of matrices
di: Montanaro, Ashley, et al.
Pubblicazione: (2023)

Unambiguous parity-query complexity
di: Gavinsky, Dmytro
Pubblicazione: (2024)

Direct sum theorems beyond query complexity
di: Suruga, Daiki
Pubblicazione: (2024)

Separations in query complexity for total search problems
di: Ben-David, Shalev, et al.
Pubblicazione: (2024)

Time complexity for deterministic string machines
di: Cataltepe, Ali, et al.
Pubblicazione: (2024)

Communication complexity of pointer chasing via the fixed-set lemma
di: Viola, Emanuele
Pubblicazione: (2025)

Pseudo-deterministic Quantum Algorithms
di: Aaronson, Hugo, et al.
Pubblicazione: (2026)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
di: Yao, Penghui, et al.
Pubblicazione: (2023)

Sublinear-query relative-error testing of halfspaces
di: Chen, Xi, et al.
Pubblicazione: (2026)

Efficient derandomization of differentially private counting queries
di: Ghentiyala, Surendra
Pubblicazione: (2025)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
di: Lemus, Mariano, et al.
Pubblicazione: (2023)

Randomized query composition and product distributions
di: Sanyal, Swagato
Pubblicazione: (2024)

Instance complexity of Boolean functions
di: Liu, Alison Hsiang-Hsuan, et al.
Pubblicazione: (2023)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
di: Block, Alexander R., et al.
Pubblicazione: (2026)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
di: Chen, Mark, et al.
Pubblicazione: (2025)

Learning unitaries with quantum statistical queries
di: Angrisani, Armando
Pubblicazione: (2023)

Conjugate queries can help
di: Tang, Ewin, et al.
Pubblicazione: (2025)

Classical versus quantum queries in quantum PCPs with classical proofs
di: Buhrman, Harry, et al.
Pubblicazione: (2024)

Real non-attractive fixed point conjecture for complex harmonic functions
di: Vaseem, Mohd
Pubblicazione: (2025)

Matrices with displacement structure: a deterministic approach for linear systems and nullspace bases
di: Khichane, Sara, et al.
Pubblicazione: (2026)

Smoothed analysis of deterministic discounted and mean-payoff games
di: Loff, Bruno, et al.
Pubblicazione: (2024)

On one-way functions and the average time complexity of almost-optimal compression
di: Zimand, Marius
Pubblicazione: (2024)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
di: Cai, Jin-Yi, et al.
Pubblicazione: (2024)

Quantum computational complexity of matrix functions
di: Cifuentes, Santiago, et al.
Pubblicazione: (2024)

Query complexity of Boolean functions on the middle slice of the cube
di: Gerbner, Dániel, et al.
Pubblicazione: (2023)

Enumeration and updates for conjunctive linear algebra queries through expressibility
di: Muñoz, Thomas, et al.
Pubblicazione: (2023)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
di: Fu, Cheng-Hao, et al.
Pubblicazione: (2025)

On the enumeration of Tarski fixed points
di: Müller, Julian
Pubblicazione: (2023)

Undecidability of tiling the plane with a fixed number of Wang bars
di: Yang, Chao, et al.
Pubblicazione: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Partial and weighted matrix multiplication
di: Vrana, Péter
Pubblicazione: (2024)

The complexity of computing in continuous time: space complexity is precision
di: Blanc, Manon, et al.
Pubblicazione: (2024)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
di: Apers, Simon, et al.
Pubblicazione: (2021)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2025)

On the complexity of Multipacking
di: Das, Sandip, et al.
Pubblicazione: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
di: Li, Tiange, et al.
Pubblicazione: (2026)

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
di: Suruga, Daiki
Pubblicazione: (2025)

On the average-case complexity of learning output distributions of quantum circuits
di: Nietner, Alexander, et al.
Pubblicazione: (2023)