Copertina

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chen, Xi, Fei, Yumou, Patel, Shyamal
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
di: Fei, Yumou
Pubblicazione: (2025)

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

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

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

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
di: Bishnu, Arijit, et al.
Pubblicazione: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
di: Bille, Philip, et al.
Pubblicazione: (2022)

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

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

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
di: Shah, Vihan
Pubblicazione: (2026)

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

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

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

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
di: Ferber, Asaf, et al.
Pubblicazione: (2025)

Computing String Covers in Sublinear Time
di: Radoszewski, Jakub, et al.
Pubblicazione: (2024)

On Solving Linear Systems in Sublinear Time
di: Andoni, Alexandr, et al.
Pubblicazione: (2018)

Almost-Optimal Sublinear Additive Spanners
di: Tan, Zihan, et al.
Pubblicazione: (2023)

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

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

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
di: Biedl, Therese, et al.
Pubblicazione: (2026)

Simple and Optimal Sublinear Algorithms for Mean Estimation
di: Bertolotti, Beatrice, et al.
Pubblicazione: (2024)

Solving the Correlation Cluster LP in Sublinear Time
di: Cao, Nairen, et al.
Pubblicazione: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
di: He, Jialin, et al.
Pubblicazione: (2025)

Counting Distinct Square Substrings in Sublinear Time
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2025)

Sublinear Algorithms for TSP via Path Covers
di: Behnezhad, Soheil, et al.
Pubblicazione: (2023)

Sublinear Spectral Clustering Oracle with Little Memory
di: Shen, Ranran, et al.
Pubblicazione: (2026)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
di: Kempa, Dominik, et al.
Pubblicazione: (2024)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Sublinear Random Access Generators for Preferential Attachment Graphs
di: Even, Guy, et al.
Pubblicazione: (2016)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
di: Dai, Jiangqi, et al.
Pubblicazione: (2025)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
di: Eden, Talya, et al.
Pubblicazione: (2025)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
di: Peng, Pan, et al.
Pubblicazione: (2025)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
di: Chen, Yixin, et al.
Pubblicazione: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
di: Mahabadi, Sepideh, et al.
Pubblicazione: (2025)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
di: Fu, Bin, et al.
Pubblicazione: (2026)

Improved Sublinear-time Moment Estimation using Weighted Sampling
di: Bhattacharya, Anup, et al.
Pubblicazione: (2025)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
di: Kwok, Tsz Chiu, et al.
Pubblicazione: (2025)