Independent sets in semi-random hypergraphs
From MaRDI portal
Publication:832900
DOI10.1007/978-3-030-83508-8_38OpenAlexW3196397510MaRDI QIDQ832900
Rameesh Paul, Anand Louis, Yash Khanna
Publication date: 25 March 2022
Full work available at URL: https://arxiv.org/abs/2104.00927
semidefinite programminghypergraphsapproximation algorithmsbeyond worst-case analysisLasserre/SoS hierarchyplanted independent setssemi-random models
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency of spectral hypergraph partitioning under planted partition model
- Independent sets in semi-random hypergraphs
- Independent sets in bounded-degree hypergraphs
- Semidefinite programming relaxations for semialgebraic problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Heuristics for semirandom graph problems
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Global Optimization with Polynomials and the Problem of Moments
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Hypergraph Theory in Wireless Communication Networks
- Coloring Random and Semi-Random k-Colorable Graphs
- Finding and certifying a large hidden clique in a semirandom graph
- Reducibility among Combinatorial Problems
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- UG-hardness to NP-hardness by losing half
- A New Algorithm for the Robust Semi-random Independent Set Problem
- Constant factor approximation for balanced cut in the PIE model
- Approximation algorithms for semi-random partitioning problems
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- Planted Models for k-Way Edge and Vertex Expansion
This page was built for publication: Independent sets in semi-random hypergraphs
