scientific article; zbMATH DE number 7378622
From MaRDI portal
Publication:5009502
DOI10.4230/LIPIcs.APPROX-RANDOM.2018.10MaRDI QIDQ5009502
Pasin Manurangsi, Eden Chlamtáč
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1804.07842
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (4)
Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem
Cites Work
- Unnamed Item
- Improved approximation algorithms for label cover problems
- The ordered covering problem
- Orienteering for electioneering
- Weighted sums of certain dependent random variables
- Public-key cryptography from different assumptions
- Detecting high log-densities
- Graph expansion and the unique games conjecture
- Sum-of-squares Lower Bounds for Planted Clique
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
- Relations between average case complexity and approximation complexity
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
- Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
- Approximation Algorithms for Label Cover and The Log-Density Threshold
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness
- Partitioning a Graph into Small Pieces with Applications to Path Transversal
- On Approximating Target Set Selection
- Hardness and approximation for network flow interdiction
- Approximation Algorithms and Hardness of the k -Route Cut Problem
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Concentration of multivariate polynomials and its applications
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
This page was built for publication:
