Cover Image

Faster exact learning of k-term DNFs with membership and equivalence queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Alman, Josh, Nadimpalli, Shivam, Patel, Shyamal, Servedio, Rocco
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

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

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

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

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

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

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

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

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

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

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)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

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

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

A Refined Laser Method and Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2020)

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

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

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
by: Alman, Josh, et al.
Published: (2025)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
by: Alman, Josh, et al.
Published: (2025)

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

Finer-Grained Hardness of Kernel Density Estimation
by: Alman, Josh, et al.
Published: (2024)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
by: Nadimpalli, Shivam, et al.
Published: (2025)

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

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

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

Rényi-infinity constrained sampling with $d^3$ membership queries
by: Kook, Yunbum, et al.
Published: (2024)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

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

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

Learning and Testing Convex Functions
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

Faster algorithms for k-Orthogonal Vectors in low dimension
by: Dürr, Anita, et al.
Published: (2025)

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

Temporal queries for dynamic temporal forests
by: Bilò, Davide, et al.
Published: (2024)

Optimal prefix-suffix queries with applications
by: Pissis, Solon P.
Published: (2024)

On the cut-query complexity of approximating max-cut
by: Plevrakis, Orestis, et al.
Published: (2022)