3 papers
cs.DS2022
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest -Subgraph and Other Problems
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg +1
We propose a new conjecture on hardness of low-degree -CSP's, and show that new hardness of approximation results for Densest -Subgraph and several other problems, including…
cs.DS2020
How to hide a clique?
Uriel Feige, Vadim Grinberg
In the well known planted clique problem, a clique (or alternatively, an independent set) of size is planted at random in an Erdos-Renyi random graph, and the goal is…
cs.DS2019
Approximating Star Cover Problems
Buddhima Gamlath, Vadim Grinberg
Given a metric space , we consider star covers of with balanced loads. A star is a pair where and , and the load of a star…