:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Gavinsky, Dmytro
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2401.11274
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)

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)

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)

Average-case deterministic query complexity of boolean functions with fixed weight
by: Li, Yuan, et al.
Published: (2024)

Efficiently Batching Unambiguous Interactive Proofs
by: Berger, Bonnie, et al.
Published: (2025)

A Note On The Natural Range Of Unambiguous-SAT
by: Pay, Tayfun
Published: (2023)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

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

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, et al.
Published: (2025)

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

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

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

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

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

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

Extending CDCL to disjunctions of parity equations
by: Beame, Paul, et al.
Published: (2026)

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

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

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

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

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

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

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

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

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

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

Complexity of learning matchings and half graphs via edge queries
by: Mande, Nikhil S., et al.
Published: (2025)

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

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

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

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

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

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, et al.
Published: (2025)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)