Copertina

Computational Complexity in Property Testing

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Pinto Jr., Renato Ferreira, Palit, Diptaksho, Raskhodnikova, Sofya
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Relative-error unateness testing
di: Chen, Xi, et al.
Pubblicazione: (2025)

Online versus Offline Adversaries in Property Testing
di: Kelman, Esty, et al.
Pubblicazione: (2024)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Testing Properties of Edge Distributions
di: Fei, Yumou
Pubblicazione: (2026)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
di: Firbas, Alexander, et al.
Pubblicazione: (2024)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
di: Kontogiannis, Andreas, et al.
Pubblicazione: (2026)

Computational Complexity of Swish
di: Horiyama, Takashi, et al.
Pubblicazione: (2026)

Homomorphism Testing with Resilience to Online Manipulations
di: Kelman, Esty, et al.
Pubblicazione: (2025)

Testing Connectedness of Images
di: Berman, Piotr, et al.
Pubblicazione: (2023)

Computational Complexities of Folding
di: Eppstein, David
Pubblicazione: (2024)

On Optimal Testing of Linearity
di: Arora, Vipul, et al.
Pubblicazione: (2024)

Improved Algorithm for Permutation Testing
di: Zhang, Xiaojin
Pubblicazione: (2020)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

Parameterized Complexity of Vehicle Routing
di: Döring, Michelle, et al.
Pubblicazione: (2025)

The Complexity of Finding and Counting Subtournaments
di: Döring, Simon, et al.
Pubblicazione: (2025)

On the Parameterized Complexity of Odd Coloring
di: Bhyravarapu, Sriram, et al.
Pubblicazione: (2025)

On the Complexity of Signed Roman Domination
di: Reddy, Sangam Balchandar
Pubblicazione: (2025)

On the Space Complexity of Online Convolution
di: Andersson, Joel Daniel, et al.
Pubblicazione: (2025)

The Complexity of Counting Small Sub-Hypergraphs
di: Bressan, Marco, et al.
Pubblicazione: (2025)

The Complexity of Maximal Common Subsequence Enumeration
di: Buzzega, Giovanni, et al.
Pubblicazione: (2025)

The Fine-Grained Complexity of Episode Matching
di: Bille, Philip, et al.
Pubblicazione: (2021)

On the Parameterized Complexity of Min-Sum-Radii
di: Kumar, Pankaj, et al.
Pubblicazione: (2026)

Testing noisy low-degree polynomials for sparsity
di: Bao, Yiqiao, et al.
Pubblicazione: (2025)

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Novel Complexity Results for Temporal Separators with Deadlines
di: Dondi, Riccardo, et al.
Pubblicazione: (2025)

Complexity of Local Search for Euclidean Clustering Problems
di: Manthey, Bodo, et al.
Pubblicazione: (2023)

Streaming Complexity Separations for Dense and Sparse Graphs
di: Liu, Yang P., et al.
Pubblicazione: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
di: Brânzei, Simina, et al.
Pubblicazione: (2020)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
di: Chudigiewitsch, Florian, et al.
Pubblicazione: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
di: Li, Qian, et al.
Pubblicazione: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
di: Putterman, Aaron, et al.
Pubblicazione: (2026)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
di: Kurita, Kazuhiro, et al.
Pubblicazione: (2025)

The Structure of In-Place Space-Bounded Computation
di: Cook, James, et al.
Pubblicazione: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
di: Nederlof, Jesper
Pubblicazione: (2026)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
di: Chen, Xi, et al.
Pubblicazione: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
di: Brânzei, Simina, et al.
Pubblicazione: (2026)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
di: Abu-Khzam, Faisal N., et al.
Pubblicazione: (2024)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
di: Liu, Wei, et al.
Pubblicazione: (2024)

Computational Explorations of Total Variation Distance
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2024)