All reports by Author David Steurer:

__
TR13-179
| 15th December 2013
__

Irit Dinur, David Steurer#### Direct Product Testing

__
TR11-142
| 2nd November 2011
__

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer#### Making the long code shorter, with applications to the Unique Games Conjecture

Revisions: 1

__
TR11-065
| 25th April 2011
__

Boaz Barak, Prasad Raghavendra, David Steurer#### Rounding Semidefinite Programming Hierarchies via Global Correlation

__
TR10-172
| 11th November 2010
__

Prasad Raghavendra, David Steurer, Madhur Tulsiani#### Reductions Between Expansion Problems

__
TR10-041
| 11th March 2010
__

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer#### Improved Algorithms for Unique Games via Divide and Conquer

__
TR09-129
| 30th November 2009
__

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer#### Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

__
TR09-125
| 24th November 2009
__

David Steurer, Nisheeth Vishnoi#### Connections Between Unique Games and Multicut

Irit Dinur, David Steurer

A direct product is a function of the form $g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with $2$ queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability.

This local testing question comes up ... more >>>

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer

The long code is a central tool in hardness of approximation, especially in

questions related to the unique games conjecture. We construct a new code that

is exponentially more ecient, but can still be used in many of these applications.

Using the new code we obtain exponential improvements over several ...
more >>>

Boaz Barak, Prasad Raghavendra, David Steurer

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with ... more >>>

Prasad Raghavendra, David Steurer, Madhur Tulsiani

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique ... more >>>

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

We study the question of whether the value of mathematical programs such as

linear and semidefinite programming hierarchies on a graph $G$, is preserved

when taking a small random subgraph $G'$ of $G$. We show that the value of the

Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is

more >>>

David Steurer, Nisheeth Vishnoi

In this paper we demonstrate a close connection between UniqueGames and

MultiCut.

%

In MultiCut, one is given a ``network graph'' and a ``demand

graph'' on the same vertex set and the goal is to remove as few

edges from the network graph as ...
more >>>