Cover Image

DNF Learning via Locally Mixing Random Walks

Fuente: arXiv

Saved in:

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

Faster exact learning of k-term DNFs with membership and equivalence queries
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)

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)

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

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)

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

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)

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)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, 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)

Engineering an Efficient Approximate DNF-Counter
by: Soos, Mate, et al.
Published: (2024)

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

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

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)

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

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

Scalable Algorithms for Approximate DNF Model Counting
by: Burkhardt, Paul, et al.
Published: (2026)

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

Learning DNF through Generalized Fourier Representations
by: Heidari, Mohsen, et al.
Published: (2025)

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)

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

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

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

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

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

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

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

FORWARD: Feasibility Oriented Random-Walk Inspired Algorithm for Radial Reconfiguration in Distribution Networks
by: Vendrell, Joan, et al.
Published: (2024)