Independent sets in semi-random hypergraphs
type: Item
instance of: scholarly article
title: Independent sets in semi-random hypergraphs
DOI: 10.1007/978-3-030-83508-8_38
author: Yash Khanna
author: Anand Louis
author: R. Paul
publication date: 2022-03-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/2104.00927
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7498701
zbMATH Keywords: planted independent sets
zbMATH Keywords: semi-random models
zbMATH Keywords: hypergraphs
zbMATH Keywords: approximation algorithms
zbMATH Keywords: semidefinite programming
zbMATH Keywords: Lasserre/SoS hierarchy
zbMATH Keywords: beyond worst-case analysis
MaRDI profile type: Publication
OpenAlex ID: W3196397510
cites work: Q4705344
cites work: Q3002828
cites work: UG-hardness to NP-hardness by losing half
cites work: Coloring Random and Semi-Random k-Colorable Graphs
cites work: Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
cites work: Exact recovery in the hypergraph stochastic block model: a spectral algorithm
cites work: Finding and certifying a large hidden clique in a semirandom graph
cites work: Heuristics for semirandom graph problems
cites work: Consistency of spectral hypergraph partitioning under planted partition model
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Independent sets in bounded-degree hypergraphs
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Q4218130
cites work: Reducibility among Combinatorial Problems
cites work: How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
cites work: Approximating coloring and maximum independent sets in 3-uniform hypergraphs
cites work: Global optimization with polynomials and the problem of moments
cites work: Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
cites work: Planted Models for k-Way Edge and Vertex Expansion
cites work: Approximation algorithms for semi-random partitioning problems
cites work: Constant factor approximation for balanced cut in the PIE model
cites work: A New Algorithm for the Robust Semi-random Independent Set Problem
cites work: Q4496025
cites work: Semidefinite programming relaxations for semialgebraic problems
cites work: Hypergraph Theory in Wireless Communication Networks
cites work: Q3002782
description: scientific article; zbMATH DE number 7498701