Cover Image

Rounding Large Independent Sets on Expanders

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bafna, Mitali, Hsieh, Jun-Ting, Kothari, Pravesh K.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Explicit Lossless Vertex Expanders
by: Hsieh, Jun-Ting, et al.
Published: (2025)

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

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

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
by: Srivastava, Shashank, et al.
Published: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
by: Tale, Prafullkumar
Published: (2025)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Sharp Online Hardness for Large Balanced Independent Sets
by: Dhawan, Abhishek, et al.
Published: (2025)

Parameterized Max Min Feedback Vertex Set
by: Lampis, Michael, et al.
Published: (2023)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
by: Bilò, Davide, et al.
Published: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
by: Bilò, Davide, et al.
Published: (2024)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2026)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

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

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Uniformity testing when you have the source code
by: Canonne, Clément L., et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
by: Jia, He, et al.
Published: (2020)

Constant Degree Networks for Almost-Everywhere Reliable Transmission
by: Bafna, Mitali, et al.
Published: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

On the parameterized complexity of Broadcast Independence and Broadcast Packing
by: Dumont, Joanne, et al.
Published: (2026)

Distributed Triangle Detection is Hard in Few Rounds
by: Assadi, Sepehr, et al.
Published: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

(Independent) Roman Domination Parameterized by Distance to Cluster
by: Ashok, Pradeesha, et al.
Published: (2024)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Tight Inapproximability of Target Set Reconfiguration
by: Ohsaka, Naoto
Published: (2024)