Copertina

DNF formulas are efficiently testable with relative error

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chen, Xi, Pires, William, Pitassi, Toniann, Servedio, Rocco A.
Natura:	Preprint
Pubblicazione:	2026
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 testing of conjunctions and decision lists
di: Chen, Xi, et al.
Pubblicazione: (2025)

Testing Juntas and Junta Subclasses with Relative Error
di: Chen, Xi, et al.
Pubblicazione: (2025)

Halfspaces are hard to test with relative error
di: Chen, Xi, et al.
Pubblicazione: (2025)

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

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

Enumerating models of DNF faster: breaking the dependency on the formula size
di: Capelli, Florent, et al.
Pubblicazione: (2018)

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

Learning Functions of Halfspaces
di: Alman, Josh, et al.
Pubblicazione: (2026)

Relative-error monotonicity testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

Detecting Low-Degree Truncation
di: De, Anindya, et al.
Pubblicazione: (2024)

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

Model-agnostic super-resolution in high dimensions
di: Chen, Xi, et al.
Pubblicazione: (2025)

Testing Convex Truncation
di: De, Anindya, et al.
Pubblicazione: (2023)

Is nasty noise actually harder than malicious noise?
di: Blanc, Guy, et al.
Pubblicazione: (2025)

DNF Learning via Locally Mixing Random Walks
di: Alman, Josh, et al.
Pubblicazione: (2025)

Differential privacy from axioms
di: Blanc, Guy, et al.
Pubblicazione: (2025)

Sparsifying Suprema of Gaussian Processes
di: De, Anindya, et al.
Pubblicazione: (2024)

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

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

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

Quadratic Speedup for Computing Contraction Fixed Points
di: Chen, Xi, et al.
Pubblicazione: (2026)

Holonomic equations and efficient random generation of binary trees
di: Lescanne, Pierre
Pubblicazione: (2022)

Sketching approximations and LP approximations for finite CSPs are related
di: Singer, Noah G., et al.
Pubblicazione: (2025)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
di: Chen, Xi, et al.
Pubblicazione: (2025)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
di: Bendotti, Pascale, et al.
Pubblicazione: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
di: Enright, Jessica, et al.
Pubblicazione: (2020)

Computing the $D$-base and $D$-relation in finite closure systems
di: Adaricheva, Kira, et al.
Pubblicazione: (2024)

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

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
di: Tate, Elise, et al.
Pubblicazione: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
di: Jansen, Bart M. P., et al.
Pubblicazione: (2026)

A Simple Proof that Ricochet Robots is PSPACE-Complete
di: Balanza-Martinez, Jose, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
di: Frei, Fabian, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
di: Frei, Fabian, et al.
Pubblicazione: (2025)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
di: Bai, Tian, et al.
Pubblicazione: (2026)

Algorithms and Hardness for Estimating Statistical Similarity
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

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

Trace reconstruction from local statistical queries
di: Chen, Xi, et al.
Pubblicazione: (2024)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Lazy Kronecker Product
di: Song, Zhao
Pubblicazione: (2026)