Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bshouty, Nader H., Haddad, George
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Testably Learning Polynomial Threshold Functions
por: Slot, Lucas, et al.
Publicado: (2024)

Testability in group theory
por: Becker, Oren, et al.
Publicado: (2022)

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

Simpler O(1) Query Algorithm for Level Ancestors
por: Saxena, Sanjeev
Publicado: (2022)

Testability of relations between permutations
por: Becker, Oren, et al.
Publicado: (2020)

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

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

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

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

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

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

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

Extraction Theorems With Small Extraction Numbers
por: Agarwal, Arjun, et al.
Publicado: (2024)