Cover Image

Average-case deterministic query complexity of boolean functions with fixed weight

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Yuan, Wu, Haowei, Yang, Yi
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

Direct sum theorems beyond query complexity
by: Suruga, Daiki
Published: (2024)

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

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

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

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

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

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

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

Efficient derandomization of differentially private counting queries
by: Ghentiyala, Surendra
Published: (2025)

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

Randomized query composition and product distributions
by: Sanyal, Swagato
Published: (2024)

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

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

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

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

Learning unitaries with quantum statistical queries
by: Angrisani, Armando
Published: (2023)

Conjugate queries can help
by: Tang, Ewin, et al.
Published: (2025)

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

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

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

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

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

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

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

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

Partial and weighted matrix multiplication
by: Vrana, Péter
Published: (2024)

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

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

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

On the complexity of Multipacking
by: Das, Sandip, et al.
Published: (2026)

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

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

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

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

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
by: Li, Songsong, et al.
Published: (2024)

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