4 citations · 7 across the 5 of their papers we have counts for
9 papers
A Refined Approximation for Euclidean k-Means
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani +2
In the Euclidean -Means problem we are given a collection of points in an Euclidean space and a positive integer . Our goal is to identify a collection of points…
Planted Models for -way Edge and Vertex Expansion
Anand Louis, Rakesh Venkat
Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a…
Semi-Random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
Anand Louis, Rakesh Venkat
The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph a…
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces
Yuval Rabani, Rakesh Venkat
We consider the problem of embedding a finite set of points that satisfy triangle inequalities into , when the points are…
Multiplayer parallel repetition for expander games
Irit Dinur, Prahladh Harsha, Rakesh Venkat +1
We investigate the value of parallel repetition of one-round games with any number of players . It has been an open question whether an analogue of Raz's Parallel Repetitio…
Embedding approximately low-dimensional metrics into
Amit Deshpande, Prahladh Harsha, Rakesh Venkat
Goemans showed that any points in -dimensions satisfying triangle inequalities can be embedded into , with worst-case distortion at mo…
Hypergraph Two-Coloring in the Streaming Model
Jaikumar Radhakrishnan, Saswata Shannigrahi, Rakesh Venkat
We consider space-efficient algorithms for two-coloring -uniform hypergraphs in the streaming model, when the hyperedges arrive one at a time. It is known that any suc…
On Fortification of Projection Games
Amey Bhangale, Ramprasad Saptharishi, Girish Varma +1
A recent result of Moshkovitz \cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection g…
Guruswami-Sinop Rounding without Higher Level Lasserre
Amit Deshpande, Rakesh Venkat
Guruswami and Sinop give a approximation guarantee for the non-uniform Sparsest Cut problem by solving -level Lasserre semidefinite constraints, provided that the ge…