Cover Image

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kothari, Pravesh, Potechin, Aaron, Xu, Jeff
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

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

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

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

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
by: Funke, Daniel, et al.
Published: (2024)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
by: Bakshi, Ainesh, et al.
Published: (2026)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
by: Kalavasis, Alkis, et al.
Published: (2026)

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
by: Brakensiek, Joshua, et al.
Published: (2026)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
by: Kothari, Pravesh K., et al.
Published: (2024)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

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

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
by: Göbel, Andreas, et al.
Published: (2025)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

MAX BISECTION might be harder to approximate than MAX CUT
by: Brakensiek, Joshua, et al.
Published: (2025)

Sparse Graph Reconstruction and Seriation for Large-Scale Image Stacks
by: Yang, Fuming, et al.
Published: (2025)

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

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

A Tight Lower Bound for Cycle Detection in Grid Graphs
by: Au, Andrew
Published: (2026)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Robust Sparse Mean Estimation via Sum of Squares
by: Diakonikolas, Ilias, et al.
Published: (2022)

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

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
by: Ghosh, Prantar, et al.
Published: (2024)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

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

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

Distance Reconstruction of Sparse Random Graphs
by: Bastide, Paul
Published: (2024)

Min-Sum Set Cover on Parallel Machines
by: Szyfelbein, Michał
Published: (2026)

A Tolerant Independent Set Tester
by: Seth, Cameron
Published: (2025)

Inverse Quadratic Decay in Random Subset Sum
by: Chen, Edwin, et al.
Published: (2026)

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

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

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

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)