4 papers · 1 filter
Upper bounds on the theta function of random graphs
Uriel Feige, Vadim Grinberg
The theta function of Lovasz is a graph parameter that can be computed up to arbitrary precision in polynomial time. It plays a key role in algorithms that approximate graph parame…
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…
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…
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…