Image de couverture de livre

A Tolerant Independent Set Tester

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Seth, Cameron
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Near-Optimal Property Testers for Pattern Matching
par: Jin, Ce, et autres
Publié: (2025)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
par: Blais, Eric, et autres
Publié: (2024)

Testing Graph Properties with the Container Method
par: Blais, Eric, et autres
Publié: (2023)

On the Structure of Replicable Hypothesis Testers
par: Aamand, Anders, et autres
Publié: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
par: Saito, Rin, et autres
Publié: (2025)

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
par: Black, Hadley, et autres
Publié: (2023)

Optimal Neighborhood Exploration for Dynamic Independent Sets
par: Borowitz, Jannick, et autres
Publié: (2024)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
par: Cardinal, Jean, et autres
Publié: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
par: Dey, Dipan, et autres
Publié: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
par: Mahabadi, Sepideh, et autres
Publié: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
par: Dumitrescu, Adrian
Publié: (2021)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
par: Bieliński, Paweł Rafał, et autres
Publié: (2026)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
par: Großmann, Ernestine, et autres
Publié: (2026)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
par: Großmann, Ernestine, et autres
Publié: (2024)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
par: Eiben, Eduard, et autres
Publié: (2024)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
par: Kothari, Pravesh, et autres
Publié: (2024)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
par: Adar, Tomer, et autres
Publié: (2026)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
par: Ghoshal, Suprovat, et autres
Publié: (2026)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
par: Adar, Tomer, et autres
Publié: (2026)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
par: Chaplick, Steven, et autres
Publié: (2024)

Online Algorithms for Geometric Independent Set
par: De, Minati, et autres
Publié: (2026)

On the Complexity of Bilevel Independent Set Problem
par: Muluk, Komal
Publié: (2026)

Rounding Large Independent Sets on Expanders
par: Bafna, Mitali, et autres
Publié: (2024)

Learning-augmented Maximum Independent Set
par: Braverman, Vladimir, et autres
Publié: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
par: Ye, Daniel
Publié: (2025)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
par: Kobayashi, Yasuaki, et autres
Publié: (2023)

A Distributed Conductance Tester Without Global Information Collection
par: Batu, Tugkan, et autres
Publié: (2023)

Stable Approximation Algorithms for Dominating Set and Independent Set
par: de Berg, Mark, et autres
Publié: (2024)

Tolerant Testing for Unique Games
par: Yoshida, Yuichi
Publié: (2026)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
par: Marin, Malory
Publié: (2025)

Fault-Tolerant ST-Diameter Oracles
par: Bilò, Davide, et autres
Publié: (2023)

Fault-Tolerant Bounded Flow Preservers
par: Bansal, Shivam, et autres
Publié: (2024)

Max Weight Independent Set in sparse graphs with no long claws
par: Abrishami, Tara, et autres
Publié: (2023)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
par: Tkachenko, Anastasiia, et autres
Publié: (2026)

Pairwise-Independent Contention Resolution
par: Gupta, Anupam, et autres
Publié: (2024)

History-Independent Load Balancing
par: Bender, Michael A., et autres
Publié: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
par: Kosinas, Evangelos
Publié: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
par: He, Jialin, et autres
Publié: (2025)

Nearly Optimal Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
par: Efthymiou, Charilaos, et autres
Publié: (2023)