Imagen de Portada

A basic lower bound for property testing

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Fischer, Eldar
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Refining the Adaptivity Notion in the Huge Object Model
por: Adar, Tomer, et al.
Publicado: (2023)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
por: Adar, Tomer, et al.
Publicado: (2024)

Support Testing in the Huge Object Model
por: Adar, Tomer, et al.
Publicado: (2023)

Optimal mass estimation in the conditional sampling model
por: Adar, Tomer, et al.
Publicado: (2025)

Clifford testing: algorithms and lower bounds
por: Hinsche, Marcel, et al.
Publicado: (2025)

An improved spectral lower bound of treewidth
por: Gima, Tatsuya, et al.
Publicado: (2024)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
por: Chakraborty, Sourav, et al.
Publicado: (2024)

Improved bounds for group testing in arbitrary hypergraphs
por: De Bonis, Annalisa
Publicado: (2024)

Complexity of basic boolean operators for digital circuit design
por: Sergeev, Igor S.
Publicado: (2026)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
por: Lachish, Oded, et al.
Publicado: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
por: S., Karthik C., et al.
Publicado: (2023)

Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
por: Wesołowski, Adam, et al.
Publicado: (2025)

Nearly Optimal Attention Coresets
por: Liberty, Edo, et al.
Publicado: (2026)

Sumsets, 3SUM, Subset Sum: Now for Real!
por: Fischer, Nick
Publicado: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
por: Fischer, Nick
Publicado: (2026)

Optimal lower bounds for quantum state tomography
por: Scharnhorst, Thilo, et al.
Publicado: (2025)

A note on the depth of optimal fanout-bounded prefix circuits
por: Sergeev, Igor S.
Publicado: (2025)

Height-bounded Lempel-Ziv encodings
por: Bannai, Hideo, et al.
Publicado: (2024)

Optimal bounds on a tree inference algorithm
por: Gardiner, Jack, et al.
Publicado: (2024)

Upper bounds on the theta function of random graphs
por: Feige, Uriel, et al.
Publicado: (2025)

A Simple Algorithm for Trimmed Multipoint Evaluation
por: Fischer, Nick, et al.
Publicado: (2025)

Quantum property testing in sparse directed graphs
por: Apers, Simon, et al.
Publicado: (2024)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
por: Fischer, Nick, et al.
Publicado: (2024)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
por: Fischer, Nick, et al.
Publicado: (2025)

Testing $C_k$-freeness in bounded-arboricity graphs
por: Eden, Talya, et al.
Publicado: (2024)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
por: Kacham, Praneeth, et al.
Publicado: (2023)

The Leafed Induced Subtree in chordal and bounded treewidth graphs
por: Baste, Julien
Publicado: (2023)

Tight bounds for the sensitivity of CDAWGs with left-end edits
por: Fujimaru, Hiroto, et al.
Publicado: (2023)

Unrolled denoising networks provably learn optimal Bayesian inference
por: Karan, Aayush, et al.
Publicado: (2024)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
por: Deppert, Max A., et al.
Publicado: (2025)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
por: Feng, Yilong, et al.
Publicado: (2025)

A Faster Algorithm for Constrained Correlation Clustering
por: Fischer, Nick, et al.
Publicado: (2025)

Dynamic r-index: An Updatable Self-Index in LCP-bounded Time
por: Nishimoto, Takaaki, et al.
Publicado: (2025)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
por: Bodlaender, Hans L., et al.
Publicado: (2025)

A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
por: Czyżewska, Jadwiga, et al.
Publicado: (2025)

The complexity of testing all properties of planar graphs, and the role of isomorphism
por: Basu, Sabyasachi, et al.
Publicado: (2021)

Approximating maximum properly colored forests via degree bounded independent sets
por: Bai, Yuhang, et al.
Publicado: (2025)

Improving polynomial bounds for the Graphical Traveling Salesman Problem with release dates on paths
por: Clementino, Thailsson, et al.
Publicado: (2025)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
por: Fischer, Nick, et al.
Publicado: (2024)