Cover Image

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bshouty, Nader H., Haddad, George
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing
by: Bshouty, Nader H.
Published: (2026)

On Exact Learning of $d$-Monotone Functions
by: Bshouty, Nader H.
Published: (2025)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
by: Bathie, Gabriel, et al.
Published: (2025)

A simple $(2+ε)$-approximation for knapsack interdiction
by: Weninger, Noah
Published: (2026)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
by: Adil, Deeksha, et al.
Published: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
by: Haeupler, Bernhard, et al.
Published: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Limitations of Membership Queries in Testable Learning
by: Lange, Jane, et al.
Published: (2025)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
by: Baligács, Júlia, et al.
Published: (2024)

ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys
by: Vigna, Sebastiano
Published: (2025)

A $O^*((2 + ε)^k)$ Time Algorithm for Cograph Deletion Using Unavoidable Subgraphs in Large Prime Graphs
by: Lafond, Manuel, et al.
Published: (2026)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
by: Bernshteyn, Anton, et al.
Published: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate
by: Chen, Ho-Lin, et al.
Published: (2026)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

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

Testable Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2023)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Testability in group theory
by: Becker, Oren, et al.
Published: (2022)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

Simpler O(1) Query Algorithm for Level Ancestors
by: Saxena, Sanjeev
Published: (2022)

Testability of relations between permutations
by: Becker, Oren, et al.
Published: (2020)

Testable Learning of General Halfspaces under Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2026)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
by: Baguley, Samuel, et al.
Published: (2024)

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

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

Extraction Theorems With Small Extraction Numbers
by: Agarwal, Arjun, et al.
Published: (2024)