Independent sets in semi-random hypergraphs
From MaRDI portal
Publication:832900
DOI10.1007/978-3-030-83508-8_38OpenAlexW3196397510MaRDI QIDQ832900FDOQ832900
Authors: Yash Khanna, Anand Louis, R. Paul 
Publication date: 25 March 2022
Full work available at URL: https://arxiv.org/abs/2104.00927
semidefinite programmingapproximation algorithmshypergraphsbeyond worst-case analysisLasserre/SoS hierarchyplanted independent setssemi-random models
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Global optimization with polynomials and the problem of moments
- Semidefinite programming relaxations for semialgebraic problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Title not available (Why is that?)
- Finding and certifying a large hidden clique in a semirandom graph
- Independent sets in bounded-degree hypergraphs
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Title not available (Why is that?)
- Constant factor approximation for balanced cut in the PIE model
- Consistency of spectral hypergraph partitioning under planted partition model
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Heuristics for semirandom graph problems
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Hypergraph theory in wireless communication networks
- Coloring Random and Semi-Random k-Colorable Graphs
- 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
- 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
- Independent sets in semi-random hypergraphs
Cited In (2)
This page was built for publication: Independent sets in semi-random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832900)
