All reports by Author Sanjeev Arora:

__
TR12-094
| 19th July 2012
__

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva#### Testing Permanent Oracles -- Revisited

__
TR10-066
| 14th April 2010
__

Sanjeev Arora, Rong Ge#### Learning Parities with Structured Noise

Revisions: 1

__
TR10-041
| 11th March 2010
__

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

__
TR05-058
| 24th May 2005
__

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra#### On Non-Approximability for Quadratic Programs

__
TR04-117
| 1st December 2004
__

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis#### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

__
TR98-008
| 15th January 1998
__

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy#### Proof verification and the hardness of approximation problems.

__
TR97-003
| 29th January 1997
__

Sanjeev Arora, Madhu Sudan#### Improved low-degree testing and its applications

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>Sanjeev Arora, Rong Ge

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we

have access to an oracle that, each time we press a button,

returns a random vector $ a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as

$a\cdot u +\eta$, where ...
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 >>>

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

This paper studies the computational complexity of the following type of

quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ...
more >>>

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such ... more >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Sanjeev Arora, Madhu Sudan

NP = PCP(log n, 1) and related results crucially depend upon

the close connection between the probability with which a

function passes a ``low degree test'' and the distance of

this function to the nearest degree d polynomial. In this

paper we study a test ...
more >>>