All reports by Author Prasad Raghavendra:

__
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-075
| 6th May 2011
__

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira#### Testing Odd-Cycle-Freeness in Boolean Functions

__
TR11-065
| 25th April 2011
__

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

__
TR11-027
| 28th February 2011
__

Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar#### Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

__
TR10-185
| 2nd December 2010
__

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu#### Agnostic Learning of Monomials by Halfspaces is Hard

__
TR10-177
| 16th November 2010
__

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu#### Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

__
TR10-172
| 11th November 2010
__

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

__
TR09-020
| 2nd March 2009
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

__
TR08-105
| 26th November 2008
__

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra#### List Decoding Tensor Products and Interleaved Codes

__
TR08-105
| 26th November 2008
__

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra#### List Decoding Tensor Products and Interleaved Codes

__
TR08-060
| 10th April 2008
__

James R. Lee, Prasad Raghavendra#### Coarse Differentiation and Multi-flows in Planar Graphs

__
TR08-008
| 8th February 2008
__

Venkatesan Guruswami, Prasad Raghavendra#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

__
TR07-016
| 13th February 2007
__

Prasad Raghavendra#### A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

__
TR06-061
| 5th May 2006
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Learning Halfspaces with Noise

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 >>>

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... 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 >>>

Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation

resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ...
more >>>

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... 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 >>>

Venkatesan Guruswami, Prasad Raghavendra

A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

James R. Lee, Prasad Raghavendra

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.

This also improves the largest known gap for planar graphs ... more >>>

Venkatesan Guruswami, Prasad Raghavendra

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

Prasad Raghavendra

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>>

Venkatesan Guruswami, Prasad Raghavendra

Learning an unknown halfspace (also called a perceptron) from

labeled examples is one of the classic problems in machine learning.

In the noise-free case, when a halfspace consistent with all the

training examples exists, the problem can be solved in polynomial

time using linear programming. ...
more >>>