Cover Image

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Xi, Patel, Shyamal, Servedio, Rocco A.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

Learning Functions of Halfspaces
by: Alman, Josh, et al.
Published: (2026)

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

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

Faster exact learning of k-term DNFs with membership and equivalence queries
by: Alman, Josh, et al.
Published: (2025)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
by: Chen, Xi, et al.
Published: (2024)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

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

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, et al.
Published: (2026)

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

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

A Simple Algorithm for Dynamic Carpooling with Recourse
by: Efron, Yuval, et al.
Published: (2024)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

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

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

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

Relative-error unateness testing
by: Chen, Xi, et al.
Published: (2025)

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

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

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
by: Kosinas, Evangelos
Published: (2025)

Tolerant Testing for Unique Games
by: Yoshida, Yuichi
Published: (2026)

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

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

Relative-error monotonicity testing
by: Chen, Xi, et al.
Published: (2024)

Enumeration Algorithms for Conjunctive Queries with Projection
by: Deep, Shaleen, et al.
Published: (2021)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)

Learning Juntas under Markov Random Fields
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
by: Carmeli, Nofar, et al.
Published: (2025)

New Statistical and Computational Results for Learning Junta Distributions
by: Beretta, Lorenzo
Published: (2025)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
by: Bringmann, Karl, et al.
Published: (2022)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
by: Casel, Katrin, et al.
Published: (2019)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

A Tolerant Independent Set Tester
by: Seth, Cameron
Published: (2025)