Imagen de Portada

A Tolerant Independent Set Tester

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Seth, Cameron
Formato:	Preprint
Publicado:	2025
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

Near-Optimal Property Testers for Pattern Matching
por: Jin, Ce, et al.
Publicado: (2025)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
por: Blais, Eric, et al.
Publicado: (2024)

Testing Graph Properties with the Container Method
por: Blais, Eric, et al.
Publicado: (2023)

On the Structure of Replicable Hypothesis Testers
por: Aamand, Anders, et al.
Publicado: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
por: Saito, Rin, et al.
Publicado: (2025)

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
por: Black, Hadley, et al.
Publicado: (2023)

Optimal Neighborhood Exploration for Dynamic Independent Sets
por: Borowitz, Jannick, et al.
Publicado: (2024)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
por: Cardinal, Jean, et al.
Publicado: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
por: Dey, Dipan, et al.
Publicado: (2025)

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

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
por: Dumitrescu, Adrian
Publicado: (2021)

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

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
por: Großmann, Ernestine, et al.
Publicado: (2026)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
por: Großmann, Ernestine, et al.
Publicado: (2024)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
por: Eiben, Eduard, et al.
Publicado: (2024)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
por: Kothari, Pravesh, et al.
Publicado: (2024)

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

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
por: Ghoshal, Suprovat, et al.
Publicado: (2026)

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

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
por: Chaplick, Steven, et al.
Publicado: (2024)

Online Algorithms for Geometric Independent Set
por: De, Minati, et al.
Publicado: (2026)

On the Complexity of Bilevel Independent Set Problem
por: Muluk, Komal
Publicado: (2026)

Rounding Large Independent Sets on Expanders
por: Bafna, Mitali, et al.
Publicado: (2024)

Learning-augmented Maximum Independent Set
por: Braverman, Vladimir, et al.
Publicado: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
por: Ye, Daniel
Publicado: (2025)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
por: Kobayashi, Yasuaki, et al.
Publicado: (2023)

A Distributed Conductance Tester Without Global Information Collection
por: Batu, Tugkan, et al.
Publicado: (2023)

Stable Approximation Algorithms for Dominating Set and Independent Set
por: de Berg, Mark, et al.
Publicado: (2024)

Tolerant Testing for Unique Games
por: Yoshida, Yuichi
Publicado: (2026)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
por: Marin, Malory
Publicado: (2025)

Fault-Tolerant ST-Diameter Oracles
por: Bilò, Davide, et al.
Publicado: (2023)

Fault-Tolerant Bounded Flow Preservers
por: Bansal, Shivam, et al.
Publicado: (2024)

Max Weight Independent Set in sparse graphs with no long claws
por: Abrishami, Tara, et al.
Publicado: (2023)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
por: Tkachenko, Anastasiia, et al.
Publicado: (2026)

Pairwise-Independent Contention Resolution
por: Gupta, Anupam, et al.
Publicado: (2024)

History-Independent Load Balancing
por: Bender, Michael A., et al.
Publicado: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
por: Kosinas, Evangelos
Publicado: (2025)

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

Nearly Optimal Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
por: Efthymiou, Charilaos, et al.
Publicado: (2023)