Search results for "Sanjeev Arora"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
1	Sanjeev Arora, Rong Ge, Ankur Moitra	Learning Topic Models - Going beyond SVD	CoRR	2012	DBLP BibTeX RDF
1	Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala	Local Versus Global Properties of Metric Spaces.	SIAM J. Comput.	2012	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra	Computing a nonnegative matrix factorization - provably.	STOC	2012	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge	Computational complexity and information asymmetry in financial products.	Commun. ACM	2011	DBLP DOI BibTeX RDF
1	Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy.	Computational Complexity	2011	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra	Computing a Nonnegative Matrix Factorization -- Provably	CoRR	2011	DBLP BibTeX RDF
1	Sanjeev Arora, James R. Lee, Sushant Sachdeva	A Reformulation of the Arora-Rao-Vazirani Structure Theorem	CoRR	2011	DBLP BibTeX RDF
1	Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck	Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach	CoRR	2011	DBLP BibTeX RDF
1	Sanjeev Arora, Rong Ge	New Algorithms for Learning in Presence of Errors.	ICALP	2011	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Rong Ge	New Tools for Graph Coloring.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Semidefinite Programming and Approximation Algorithms: A Survey.	ISAAC	2011	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer	Improved Algorithms for Unique Games via Divide and Conquer.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Sanjeev Arora, Rong Ge	Learning Parities with Structured Noise.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer	Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)	CoRR	2010	DBLP BibTeX RDF
1	Sanjeev Arora, Elad Hazan, Satyen Kale	O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n2) Time.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Semidefinite Programming and Approximation Algorithms: A Survey.	SWAT	2010	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge	Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract).	ICS	2010	DBLP BibTeX RDF
1	Sanjeev Arora, Boaz Barak, David Steurer	Subexponential Algorithms for Unique Games and Related Problems.	FOCS	2010	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Expander flows, geometric embeddings and graph partitioning.	J. ACM	2009	DBLP DOI BibTeX RDF	Graph partitioning, semidefinite programs, multicommodity flows, expanders, expansion, graph separators
1	Sanjeev Arora, Boaz Barak	Computational Complexity - A Modern Approach.		2009	RDF
1	Sanjeev Arora, David Steurer, Avi Wigderson	Towards a Study of Low-Complexity Graphs.	ICALP	2009	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Constantinos Daskalakis, David Steurer	Message passing algorithms and improved LP decoding.	STOC	2009	DBLP DOI BibTeX RDF	lp decoding, min-sum algorithm, ldpc codes, message-passing algorithms
1	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Geometry, flows, and graph-partitioning algorithms.	Commun. ACM	2008	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi	Unique games on expanding constraint graphs are easy: extended abstract.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms, semidefinite programming, expander graphs
1	Sanjeev Arora, James R. Lee, Assaf Naor	Fréchet Embeddings of Negative Type Metrics.	Discrete & Computational Geometry	2007	DBLP DOI BibTeX RDF	Sparsest cut problem, Euclidean, L 1, Distortion, Metric embeddings
1	Sanjeev Arora, Satyen Kale	A combinatorial, primal-dual approach to semidefinite programs.	STOC	2007	DBLP DOI BibTeX RDF	balanced separator, matrix multiplicative weights, min UnCut, semidefinite programming, sparsest cut
1	Sanjeev Arora, Béla Bollobás, László Lovász, Iannis Tourlakis	Proving Integrality Gaps without Knowing the Linear Program.	Theory of Computing	2006	DBLP DOI BibTeX RDF
1	Sanjeev Arora, George Karakostas	A 2 + epsilon approximation algorithm for the k-MST problem.	Math. Program.	2006	DBLP DOI BibTeX RDF	k-Minimum Spanning Tree, Primal-Dual schema, Approximation algorithm
1	Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala	Local versus global properties of metric spaces.	SODA	2006	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Elad Hazan, Satyen Kale	A Fast Random Sampling Algorithm for Sparsifying Matrices.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Eden Chlamtac	New approximation guarantee for chromatic number.	STOC	2006	DBLP DOI BibTeX RDF	approximation algorithms, graph coloring, semidefinite programming, chromatic number
1	Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra	On Non-Approximability for Quadratic Programs	Electronic Colloquium on Computational Complexity (ECCC)	2005	DBLP BibTeX RDF
1	Sanjeev Arora, Bernard Chazelle	Is the thrill gone?	Commun. ACM	2005	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra	On Non-Approximability for Quadratic Programs.	FOCS	2005	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Elad Hazan, Satyen Kale	Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method.	FOCS	2005	DBLP DOI BibTeX RDF
1	Sanjeev Arora, James R. Lee, Assaf Naor	Euclidean distortion and the sparsest cut.	STOC	2005	DBLP DOI BibTeX RDF	approximation algorithms, semidefinite programming, metric embeddings, sparsest cut
1	Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.	STOC	2005	DBLP DOI BibTeX RDF	Lovász-Schrijver matrix cuts, inapproximability, integrality gaps
1	Mikhail Alecknovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy	Electronic Colloquium on Computational Complexity (ECCC)	2004	DBLP BibTeX RDF
1	Sanjeev Arora, Kevin L. Chang	Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problems.	Algorithmica	2004	DBLP DOI BibTeX RDF	Degree-Restricted Minimum Spanning Tree, Low degree, Approximation algorithm
1	Sanjeev Arora, Bo Brinkman	A Randomized Online Algorithm for Bandwidth Utilization.	J. Scheduling	2004	DBLP DOI BibTeX RDF	congestion control, online algorithms
1	Sanjeev Arora, Elad Hazan, Satyen Kale	0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time.	FOCS	2004	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Expander flows, geometric embeddings and graph partitioning.	STOC	2004	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Madhu Sudan	Improved Low-Degree Testing and its Applications.	Combinatorica	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 68Q10, 68Q17
1	Sanjeev Arora	How NP got a new definition: a survey of probabilistically checkable proofs	CoRR	2003	DBLP BibTeX RDF
1	Sanjeev Arora, Subhash Khot	Fitting algebraic curves to noisy data.	J. Comput. Syst. Sci.	2003	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Approximation schemes for NP-hard geometric optimization problems: a survey.	Math. Program.	2003	DBLP DOI BibTeX RDF
1	Sanjeev Arora, George Karakostas	Approximation Schemes for Minimum Latency Problems.	SIAM J. Comput.	2003	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Kevin L. Chang	Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem.	ICALP	2003	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Proving Integrality Gaps without Knowing the Linear Program.	FCT	2003	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Klaus Jansen, José D. P. Rolim, Amit Sahai (eds.)	Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003, Proceedings	RANDOM-APPROX	2003	DBLP BibTeX RDF
1	Sanjeev Arora, Alan M. Frieze, Haim Kaplan	A new rounding procedure for the assignment problem with applications to dense graph arrangement problems.	Math. Program.	2002	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Bo Brinkman	A randomized online algorithm for bandwidth utilization.	SODA	2002	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Béla Bollobás, László Lovász	Proving Integrality Gaps without Knowing the Linear Program.	FOCS	2002	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Subhash Khot	Fitting algebraic curves to noisy data.	STOC	2002	DBLP DOI BibTeX RDF
1	Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell	A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.	NIPS	2002	DBLP BibTeX RDF
1	Sanjeev Arora	Approximation Schemes for Geometric NP-Hard Problems: A Survey.	FSTTCS	2001	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Ravi Kannan	Learning mixtures of arbitrary gaussians.	STOC	2001	DBLP DOI BibTeX RDF	clustering, learning, gaussians, mixture distributions
1	Sanjeev Arora, George Karakostas	A 2+epsilon approximation algorithm for the k-MST problem.	SODA	2000	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Approximation algorithms that take advice.	APPROX	2000	DBLP DOI BibTeX RDF
1	Sanjeev Arora, David R. Karger, Marek Karpinski	Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems.	J. Comput. Syst. Sci.	1999	DBLP DOI BibTeX RDF
1	Susanne Albers, Sanjeev Arora, Sanjeev Khanna	Page Replacement for General Caching Problems.	SODA	1999	DBLP DOI BibTeX RDF
1	Sanjeev Arora, George Karakostas	Approximation Schemes for Minimum Latency Problems.	STOC	1999	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy	Proof verification and the hardness of approximation problems.	Electronic Colloquium on Computational Complexity (ECCC)	1998	DBLP BibTeX RDF
1	Sanjeev Arora	Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems.	J. ACM	1998	DBLP DOI BibTeX RDF	approximation algorithms, matching, traveling salesman problem, network design, Steiner problem
1	Sanjeev Arora, Shmuel Safra	Probabilistic Checking of Proofs: A New Characterization of NP.	J. ACM	1998	DBLP DOI BibTeX RDF	computations on polynomials and finite fields, proof checking, reducibility and completeness, trade-offs/relations among complexity measures, approximation algorithms, NP-completeness, error-correcting codes, hardness of approximations, probabilistic computation, interactive computation, complexity hierarchies
1	Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy	Proof Verification and the Hardness of Approximation Problems.	J. ACM	1998	DBLP DOI BibTeX RDF	optimization, NP-completeness, randomness, proof verification
1	Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn	A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP.	SODA	1998	DBLP DOI BibTeX RDF
1	Sanjeev Arora	The Approximability of NP-hard Problems.	STOC	1998	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Prabhakar Raghavan, Satish Rao	Approximation Schemes for Euclidean k-Medians and Related Problems.	STOC	1998	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Madhu Sudan	Improved low-degree testing and its applications	Electronic Colloquium on Computational Complexity (ECCC)	1997	DBLP BibTeX RDF
1	Sanjeev Arora, Ronald Fagin	On Winning Strategies in Ehrenfeucht-Fraïssé Games.	Theor. Comput. Sci.	1997	DBLP DOI BibTeX RDF
1	Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk	The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations.	J. Comput. Syst. Sci.	1997	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems.	RANDOM	1997	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems.	FOCS	1997	DBLP DOI BibTeX RDF	randomized polynomial time approximation, Euclidean TSP, optimum traveling salesman tour, Euclidean problems, nearly-linear time approximation, randomized, Steiner Tree, parallel implementations, randomised algorithms, geometric problems
1	Sanjeev Arora, Madhu Sudan	Improved Low-Degree Testing and its Applications.	STOC	1997	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs	On-Line Algorithms for Path Selection in a Nonblocking Network.	SIAM J. Comput.	1996	DBLP DOI BibTeX RDF
1	Sanjeev Arora	Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems.	FOCS	1996	DBLP DOI BibTeX RDF	polynomial time approximation, Euclidean TSP, optimum traveling salesman tour, Euclidean problems, k-TSP, Minimum degree-k, k-MST, computational geometry, spanning tree, Steiner Tree, best approximation, geometric problems
1	Sanjeev Arora, Alan M. Frieze, Haim Kaplan	A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems.	FOCS	1996	DBLP DOI BibTeX RDF	rounding procedure, dense graph arrangement, randomized procedure, fractional perfect matchings, LP rounding procedure, assignment problem, randomised algorithms, linear inequality
1	Sanjeev Arora	Reductions, Codes, PCPs, and Inapproximability.	FOCS	1995	DBLP DOI BibTeX RDF	NP-hard functions, code-like Levin reduction, complexity assumption, positive fraction, 3-colorable graph, code-like reduction, computational complexity, graph theory, error correction codes, error-correcting codes, NP-hardness, codes, inapproximability, PCPs, hardness, approximation ratio
1	Sanjeev Arora, David R. Karger, Marek Karpinski	Polynomial time approximation schemes for dense instances of NP-hard problems.	STOC	1995	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani	Simulating quadratic dynamical systems is PSPACE-complete (preliminary version).	STOC	1994	DBLP DOI BibTeX RDF
1	Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk	The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations	FOCS	1993	DBLP DOI BibTeX RDF	approximate optima, NP-hard, lattices, codes, polynomial time algorithm, linear equations, interactive proof systems, hardness, set-cover problem, binary codes
1	Sanjeev Arora, Shmuel Safra	Probabilistic Checking of Proofs; A New Characterization of NP	FOCS	1992	DBLP DOI BibTeX RDF	membership proofs, languages, time complexity, polynomial time, independent set, clique, NP
1	Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy	Proof Verification and Hardness of Approximation Problems	FOCS	1992	DBLP DOI BibTeX RDF	approximation problems, polynomial-time probabilistic oracle machine, random bits, MAXSNP-hard, metric TSP, time complexity, NP, MAX-CUT, MAX-SAT, proof verification
1	Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs	On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract)	STOC	1990	DBLP DOI BibTeX RDF

Publications of "Sanjeev Arora" ( http://dblp.L3S.de/Authors/Sanjeev_Arora )