and Problem Complexity—Nonnumerical Algorithms and Problems General Terms (2009)
We present an efficient algorithm to find a good solution to the Unique Games problem when the constraint graph is an expander. We introduce a new analysis of the standard SDP in this case that...
O(plog n) Approximation to Sparsest Cut in ~O(n2) Time (2009)
Abstract We show how to compute O(plog n)-approximations to Sparsest Cut and Balanced Separator problems in ~O(n2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004)....
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analyses are usually very...
1. A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover (2008)
Advisor Luca Trevisan, Sanjeev Arora, Subhash Khot, Ra Kolla, David Steurer, Nisheeth Vishnoi
We prove that the integrality gap for Vertex Cover remains at least 7/6 − ɛ after Ωɛ(n) rounds of LS+ method, which generates tighter semidefinite relaxations at each round. Our results apply...
ABSTRACT Euclidean distortion and the Sparsest Cut (2008)
We prove that every n-point metric space of negative type (in particular, every n-point subset of L1) embeds into a Euclidean space with distortion O ( √ log n log log n), a result which is tight...
ABSTRACT We describe how to color every 3-colorable graph with O(n0.2111) colors, thus improving an algorithm of Blum and Karger from almost a decade ago. Our analysis uses new geometric ideas...
Sanjeev Arora, Bernard Chazelle
Computer science is nothing less than a new way of thinking; explaining it to the wider world is critical to the future of the field. The irony is hard to miss: While computing technology is thriving...
On Non-Approximability for Quadratic Programs Preliminary Version (2008)
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 ∈ {−1, +1} n that maximizes xT Ax....
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
Not to be reproduced or distributed without the authors ’ permission This is an Internet draft. Some chapters are more finished than others. References and attributions are very preliminary and we...
Mixtures of gaussian (or normal) distributions arise in a variety of application areas. Many techniques have been proposed for the task of finding the component gaussians given samples from the...
• Approximation Algorithms • Convex Optimization (2008)
Eden Chlamtac, Advisor Prof, Sanjeev Arora, Advisor Prof, Uriel Feige
Research Interests My main area of interest is in designing and analyzing approximation algorithms which use Semidefinite Programming (SDP) relaxations. Much of my work has focused on applying this...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
and Problem Complexity—General General Terms Algorithms, Theory (2008)
We prove that every n-point metric space of negative type (in particular, every n-point subset of L1) embeds into a Euclidean space with distortion O ( √ log n log log n), a result which is tight...
Hardness of Approximation Problems (2008)
Sanjeev Arora, Sanjeev Arora, Olden St
(Revised version of a dissertation submitted at
PCP Theorem and Hardness of Computing Approximate (2008)
Since we have few techniques for proving strong lowerbounds on Turing machine computations, an interim approach is to study interrelationships between various complexity questions. We usually prove...
Given a planar graph on n nodes with costs (weights) on its edges, de ne the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Sanjeev Arora, Princeton U, David Karger, Philip Klein, Brown U, Andrzej Woloszyn, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
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...
We present a randomized polynomial time approximation scheme for Euclidean TSP in!
Sanjeev Arora, Yuval Rabani, Umesh Vazirani
Quadratic Dynamical Systems (QDS), whose definition extends that of Markov chains, are used to model phenomena in a variety of fields like statistical physics and natural evolution. Such systems also...
Sanjeev Arora, Princeton U, David Karger, Philip Klein, Brown U, Andrzej Woloszyn, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
Ecole Normale Sup'erieure (2007)
Sanjeev Arora, Jacques Stern, Z Sweedyk, U. C. Berkeley
We prove the following about the Nearest Lattice Vector Problem (in any `p norm), the Nearest Codeword Problem for binary codes, the problem of learning a halfspace in the presence of errors, and...
We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satises any linear inequality, then with high probability, the...
2 (more generally, in d (2007)
NP-hard geometric optimization problems arise in many disciplines. Perhaps the most famous one is the traveling salesman problem (TSP): given n nodes in
Learning mixtures of arbitrary gaussians [Extended Abstract] (2007)
Mixtures of gaussian (or normal) distributions arise in a variety of application areas. Many techniques have been proposed for the task of finding the component gaussians given samples from the...
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Mario Szegedy
We show that every language in NP has a probablistic verier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a...
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...
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...
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni-form caching). However, recent...
Expander Flows, Geometric Embeddings and Graph Partitioning (2007)
Sanjeev Arora, Satish Rao, Umesh Vazirani
We give a O( # log n)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves the O(log n)-approxi- mation of Leighton and Rao (1988). We use a...
Satyen Kale, Advisor Prof, Sanjeev Arora, Advisor Prof, Abhiram Ranade
Completed equivalent of a Master’s course in mathematics.
O(plog n) Approximation to Sparsest Cut in ~O(n2) Time (2007)
Sanjeev Arora, Elad Hazan, Satyen Kale
Abstract We show how to compute O(plog n)-approximations to Sparsest Cut and Balanced Separator problems in ~O(n2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004)....
A combinatorial, primal-dual approach to semidefinite programs (2007)
Semidefinite programs (SDP) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative...
Local versus global properties of metric spaces (2006)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala
Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ1 with low distortion) are...
Local versus global properties of metric spaces (2006)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala
Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ1 with low distortion) are...
A Fast Random Sampling Algorithm for Sparsifying Matrices (2006)
Sanjeev Arora, Elad Hazan, Satyen Kale
We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the...
Euclidean distortion and the Sparsest Cut (2005)
Arora, Sanjeev, Lee, James R., Naor, Assaf
We prove that every $n$-point metric space of negative type (and, in particular, every $n$-point subset of $L_1$) embeds into a Euclidean space with distortion $O(\sqrt{\log n} \cdot\log \log n)$, a...
Learning mixtures of separated nonspherical Gaussians (2005)
Mixtures of Gaussian (or normal) distributions arise in a variety of application areas. Many heuristics have been proposed for the task of finding the component Gaussians given samples from the...
Learning mixtures of separated nonspherical Gaussians (2005)
Mixtures of Gaussian (or normal) distributions arise in a variety of application areas. Many heuristics have been proposed for the task of finding the component Gaussians given samples from the...
Euclidean distortion and the Sparsest Cut (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
Bi-Lipschitz embeddings of finite metric spaces, a topic originally studied in geometric analysis and Banach space theory, became an integral part of theoretical computer science following work of...
Euclidean distortion and the Sparsest Cut (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
We prove that every n-point metric space of negative type (and, in particular, every npoint subset of L1) embeds into a Euclidean space with distortion O ( √ log n · log log n), a result which is...
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy (2005)
Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis
hierarchy
On non-approximability for quadratic programs (2005)
This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x ∈ {−1, 1} n that maximizes x T Mx....
The multiplicative weights update method: a meta algorithm and applications (2005)
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very...
The multiplicative weights update method: a meta algorithm and applications (2005)
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very...
Sanjeev Arora, Elad Hazan, Satyen Kale
Semidefinite programming (SDP) relaxations appear in many recent approximation algorithms but the only general technique for solving such SDP relaxations is via interior point methods. We use a...
SAFRA: On non-approximability for quadratic programs (2005)
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 ∈ {−1, 1} n that maximizes x T Mx....
The multiplicative weights update method: a meta algorithm and applications (2005)
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very...
Expander flows, geometric embeddings and graph partitioning (2004)
Sanjeev Arora, Satish Rao, Umesh Vazirani
We give aO ( � logn)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves theO(logn)-approximation of Leighton and Rao (1988). We use a...
O(plog n) approximation to SPARSEST CUT in ~O(n2) time (2004)
Sanjeev Arora, Elad Hazan, Satyen Kale
We show how to compute O ( √ log n)-approximations to Sparsest Cut and Balanced Separator problems in Õ(n2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their...
O ( √ log n) approximation to SPARSEST CUT can be found in Õ(n 2) time FOCS 2004 Submission (2004)
Sanjeev Arora, Elad Hazan, Satyen Kale
We show that the recent results for obtaining O ( √ log n)-approximation to sparsest cut and balanced separator problems due to Arora, Rao, and Vazirani (2004) can be used to derive an Õ(n2) time...
How NP got a new definition: a survey of probabilistically checkable proofs (2003)
We survey a collective achievement of a group of researchers: the PCP Theorems. They give new definitions of the class \np, and imply that computing approximate solutions to many \np-hard problems is...
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (2003)
Hall, Alex, Langkau, Katharina, Skutella, Martin, Arora, Sanjeev, Jansen, Klaus, Rolim, Jose D. P., ...
Given a network with capacities and transit times on the arcs, the quickest flow problem asks for a `flow over time' that satisfies given demands within minimal time. In the setting of flows over...
Approximation schemes for NP-hard geometric optimization problems: A survey (2003)
NP-hard geometric optimization problems arise in many disciplines. Perhaps the most famous one is the traveling salesman problem (TSP): given n nodes in ℜ 2 (more generally, in ℜ d), find the...
Approximation schemes for degree-restricted MST and red-blue separation problem (2003)
Abstract We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST problem by adapting techniques used previously by Arora for approximating TSP....
Approximation schemes for degree-restricted MST and red-blue separation problem (2003)
We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST problem by adapting techniques used previously by Arora for approximating TSP. Given n...
A Randomized Online Algorithm for Bandwidth Utilization (2002)
Protocols for data transmission over an IP computer network should not only lead to e#cient network utilization but also be fair to di#erent users. Current networks accomplish these goals by some...
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
jh(xi) \Gamma yij ^ ffi for at least ae fraction of the indices i (1) If ffi = 0, this is just the list decoding problem that has been popular in complexity theory and for which Sudan gave a poly(m;...
Fitting algebraic curves to noisy data (2002)
We introduce the following problem which is motivated by applications in vision and pattern detection: We are given pairs of datapoints (x 1, y 1), (x 2, y 2),..., (xm, ym)
A Randomized Online Algorithm for Bandwidth Utilization (2002)
Protocols for data transmission over an IP computer network should not only lead to ecient network utilization but also be fair to dierent users. Current networks accomplish these goals by some form...
Fitting algebraic curves to noisy data (2002)
Motivated by applications in vision and pattern detection, we introduce the following problem. We are given pairs of datapoints (x 1, y 1), (x 2, y 2),..., (xm, ym), a noise parameter #> 0, a...
Proving integrality gaps without knowing the linear program (2002)
Proving integrality gaps for linear relaxations of NP optimization problems is a di#cult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an...
A Randomized Online Algorithm for Bandwidth Utilization (2002)
Protocols for data transmission over a TCP-like computer network should not only lead to ecient network utilization but also be fair to dierent users. Current networks accomplish these goals by some...
A Randomized Online Algorithm for Bandwidth Utilization (2002)
Princeton University Abstract Protocols for data transmission over a TCP-like computer network should not only lead to efficient network utilization but also be fair to different users. Current...
A Randomized Online Algorithm for Bandwidth Utilization (2002)
Protocols for data transmission over a TCP-like computer network should not only lead to efficient network utilization but also be fair to different users. Current networks accomplish these goals by...
A Note on the Representational Incompatibility (2002)
Of Function Approximation, Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
Proving integrality gaps without knowing the linear program (2002)
Sanjeev Arora, Béla Bollobás, László Lovász, Iannis Tourlakis
Abstract: Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We...
A 2 + # approximation algorithm for the k-MST problem (2000)
Sanjeev Arora, George Karakostas
For any #> 0 we give a (2+#)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [5]. As in...
Approximation schemes for minimum latency problems (1999)
Abstract The minimum latency problem, also known as travelingrepairman problem [1], is a variant of the TSP in which the starting node of the tour is given and the goal isto minimize the sum of the...
Approximation schemes for minimum latency problems (1999)
Sanjeev Arora, George Karakostas
The minimum latency problem, also known as traveling repairman problem [1], is a variant of the TSP in which the starting node of the tour is given and the goal is to minimize the sum of the arrival...
Page replacement for general caching problems (1999)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni-form caching). However, recent...
Page Replacement for General Caching Problems (1999)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
Probabilistic checking of proofs: a new characterization of NP (1998)
Abstract. We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in...
Probabilistic checking of proofs: a new characterization of NP (1998)
We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial...
Approximation schemes for euclidean k-medians and related problems (1998)
Sanjeev Arora, Prabhakar Raghavan, Satish Rao
In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points...
The Approximability of NP-Hard Problems (1998)
Many problems in combinatorial optimization are NP-hard (see [60]). This has forced researchers to
Approximation schemes for Euclidean (1998)
Medians And Related, Sanjeev Arora, Prabhakar Raghavan, Satish Rao
In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points...
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1998)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1998)
Sanjeev Arora, Michelangelo Grigni, Princeton U, David Karger, Philip Klein, Brown U, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1998)
Sanjeev Arora, Michelangelo Grigni, Princeton U, David Karger, Philip Klein, Brown U, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
On winning strategies in Ehrenfeucht-Fraiss'e games (1997)
We present a powerful and versatile new sufficient condition for the second player (the "duplicator") to have a winning strategy in an Ehrenfeucht-Fraiss'e game on graphs. We...
ing the situation, assume only that on input x the verifier V uses poly(logn) bits from a proof \Pi, uses O(log n) random bits, and is non-adaptive. We design a verifier V new which expects a proof...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1997)
Graph Tsp, Michelangelo Grigni, Sanjeev Arora, Princeton U, David Karger, Philip Klein, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Improved Low-Degree Testing and Its Applications (1997)
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...
Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems (1997)
We present a randomized polynomial time approximation scheme for Euclidean TSP in ! 2 that is substantially more efficient than our earlier scheme in [3] (and the scheme of Mitchell [40]). For any...
Improved Low-Degree Testing and Its Applications (1997)
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...
Nearly linear time approximation schemes for Euclidean TSP and other geometric problems (1997)
Abstract We present a randomized polynomial time approximation scheme for Euclidean TSP in!2 that is substantially more efficient than our earlier scheme in [2] (and the scheme of Mitchell [21]). For...
Improved low degree testing and its applications (1997)
NP = PCP(log n, 1) and related results crucially depend upon the close connection betsveen the probability with which a function passes a low degree test and the distance of this function to the...
On-line algorithms for path selection in a nonblocking network (1996)
Sanjeev Arora, F. Thomson Leighton, M. Maggs
This paper presents the first optimal-time algorithms for path selection in an optimal-size nonblocking network. In particular, we describe an N-input, N-output, nonblocking network with O(N log N)...
Haim Kaplan z We present approximation schemes for \dense " instances of many well-known NP-hard problems, including 0-1 quadratic-assignment, (an optimization formulation of)...
Polynomial time approximation schemes for euclidean tsp and other geometric problems (1996)
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c> 1 and given any n nodes in
On-line algorithms for path selection in a nonblocking network (1996)
Sanjeev Arora, F. Thomson Leighton, M. Maggs
This paper presents the first optimal-time algorithms for path selection in an optimal-size nonblocking network. In particular, we describe an N-input, N-output, nonblocking network with O(N log N)...
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in # 2 , a randomized version of the scheme finds a (1 +...
Hardness Of Approximations (1996)
This chapter is a self-contained survey of recent results about the hardness of approximating NP-hard optimization problems.
We present approximation schemes for "dense" instances of many well-known NP-hard problems, including 0-1 quadratic-assignment, (an optimization formulation of) graphisomorphism,...
On-line Algorithms for Path Selection in a Nonblocking Network (1996)
Sanjeev Arora, F. T. Leighton, Bruce M. Maggs
Nonblocking networks arise in a variety of communication applications including telephone systems and distributed-memory computer architectures. Although asymptotically optimal constructions are...
Sanjeev Arora, Alan Frieze, Haim Kaplan
We present approximation schemes for "dense" instances of many well-known NP-hard problems, including 0-1 quadratic-assignment, (an optimization formulation of) graphisomorphism,...
Sanjeev Arora, Alan Frieze, Haim Kaplan
We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability,...
Polynomial time approximation schemes for euclidean tsp and other geometric problems (1996)
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c> 1 and given any n nodes in ℜ2, a randomized version of the scheme finds a (1 +...
Reductions, codes, PCPs, and inapproximability (1995)
Many recent results show the hardness of approximating NP-hard functions. We formalize, in a very simple way, what these results involve: a code-like Levin reduction. Assuming a well-known complexity...
Polynomial time approximation schemes for dense instances of NP-hard problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense " instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial time approximation schemes for dense instances of NP-hard problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...
Polynomial time approximation schemes for dense instances of NP-hard problems (1995)
Sanjeev Arora, David Karger, Marek Karpinski
We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense ” instances of many NP-hard optimization problems, including maximum cut, graph bisection,...
Probabilistic checking of proofs and hardness of approximation problems / (1994)
Thesis (Ph. D.)--Princeton University, 1994.
Probabilistic checking of proofs and hardness of approximation problems / (1994)
Revised version of a dissertation submitted at CS Division. UC Berkeley in August 1994.
On-line Algorithms for Path Selection in a Nonblocking Network (1994)
Sanjeev Arora, F. T. Leighton, Bruce M. Maggs
Nonblocking networks arise in a variety of communication contexts including telephone systems and distributed-memory computer architectures. Although asymptotically optimal constructions are known...
Simulating Quadratic Dynamical Systems is PSPACE-complete (1994)
Sanjeev Arora, Yuval Rabani, Umesh Vazirani
Quadratic Dynamical Systems (QDS), whose definition extends that of Markov chains, are used to model phenomena in a variety of fields like statistical physics and natural evolution. Such systems also...
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations (1993)
Sanjeev Arora Computer, Sanjeev Arora, Jacques Stern, Z Sweedyk, U. C. Berkeley
We prove the following about the Nearest Lattice Vector Problem (in any ` p norm), the Nearest Codeword Problem for binary codes, the problem of learning a halfspace in the presence of errors, and...
Photocopy.
Photocopy.
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Proof verification and hardness of approximation problems (1992)
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 constant number of bits in the proof. If...
Proof Verification and Hardness of Approximation Problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Relativizing versus nonrelativizing techniques: The role of local checkability (1992)
Sanjeev Arora, Russell Impagliazzo, Umesh Vazirani, U. C. Berkeley, U. C. Berkeley
Contradictory oracle results have traditionally been interpreted as giving some evidence that resolving a complexity issue is difficult. However, for quite a while, there have been a few known...
Proof verification and hardness of approximation problems (1992)
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 constant number of bits in the proof. If...
A new calculation of the antiproton to proton ratio in supernova shells /--by Sanjeev Arora. (1988)
Photocopy.
Arora, Sanjeev, Thornton, Karla, Jenkusky, Steven M., Parish, Brooke, Scaletti, Joseph V.
Project Extension for Community Healthcare Outcomes (Project ECHO) is a telemedicine and distance-learning program designed to improve access to quality health care for New Mexicans with hepatitis C....