☰

Sanjeev Arora - Publications

Affiliations: 
Computer Science Princeton University, Princeton, NJ 
Area:
Uses of randomness in complexity theory and algorithms; Efficient algorithms for finding approximate solutions to NP-hard problems (or proving that they don't exist); Cryptography.
Tree Info Similar researchers PubMed Report error

26 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2018 Arora S, Ge R, Halpern Y, Mimno D, Moitra A, Sontag D, Wu Y, Zhu M. Learning topic models -- provably and efficiently Communications of the Acm. 61: 85-93. DOI: 10.1145/3186262  0.479
2016 Arora S, Kale S. A combinatorial, primal-dual approach to semidefinite programs Journal of the Acm. 63. DOI: 10.1145/2837020  0.473
2016 Arora S, Ge R, Kannan R, Moitra A. Computing a Nonnegative Matrix Factorization---Provably Siam Journal On Computing. 45: 1582-1611. DOI: 10.1137/130913869  0.563
2015 Arora S, Barak B, Steurer D. Subexponential algorithms for unique games and related problems Journal of the Acm. 62. DOI: 10.1145/2775105  0.725
2013 Sachdeva R, Sachdeva S, Arora S. Sternal tuberculosis. Annals of Medical and Health Sciences Research. 3: S21-3. PMID 24349840 DOI: 10.4103/2141-9248.121213  0.461
2012 Arora S, Hazan E, Kale S. The Multiplicative Weights Update Method: A Meta-Algorithm and Applications Theory of Computing. 8: 121-164. DOI: 10.4086/Toc.2012.V008A006  0.58
2012 Arora S, Daskalakis C, Steurer D. Message-passing algorithms and improved LP decoding Ieee Transactions On Information Theory. 58: 7260-7271. DOI: 10.1109/Tit.2012.2208584  0.68
2011 Arora S, Barak B, Brunnermeier M, Ge R. Computational complexity and information asymmetry in financial products Communications of the Acm. 54: 101-107. DOI: 10.1145/1941487.1941511  0.564
2011 Alekhnovich M, Arora S, Tourlakis I. Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy Computational Complexity. 20: 615-648. DOI: 10.1007/S00037-011-0027-Z  0.73
2010 Arora S, Hazan E, Kale S. O(√log n) approximation to sparsest cut in õ(n2) time Siam Journal On Computing. 39: 1748-1771. DOI: 10.1137/080731049  0.636
2009 Arora S, Rao S, Vazirani U. Expander flows, geometric embeddings and graph partitioning Journal of the Acm. 56. DOI: 10.1145/1502793.1502794  0.682
2008 Arora S, Rao S, Vazirani U. Geometry, flows, and graph-partitioning algorithms Communications of the Acm. 51: 96-105. DOI: 10.1145/1400181.1400204  0.662
2007 Arora S, Lee JR, Naor A. Fréchet embeddings of negative type metrics Discrete and Computational Geometry. 38: 726-739. DOI: 10.1007/S00454-007-9007-0  0.3
2006 Arora S, Bollobás B, Lovász L, Tourlakis I. Proving Integrality Gaps without Knowing the Linear Program Theory of Computing. 2: 19-51. DOI: 10.4086/Toc.2006.V002A002  0.687
2005 Arora S, Kannan R. Learning Mixtures Of Separated Nonspherical Gaussians Annals of Applied Probability. 15: 69-92. DOI: 10.1214/105051604000000512  0.385
2004 Arora S, Chang KL. Approximation schemes for degree-restricted MST and red-blue separation problems Algorithmica. 40: 189-210. DOI: 10.1007/S00453-004-1103-4  0.336
2003 Arora S, Karakostas G. Approximation schemes for minimum latency problems Siam Journal On Computing. 32: 1317-1337. DOI: 10.1137/S0097539701399654  0.662
2003 Arora S. Approximation schemes for NP-hard geometric optimization problems: a survey Mathematical Programming. 97: 43-69. DOI: 10.1007/S10107-003-0438-Y  0.424
2003 Arora S, Sudan M. Improved low-degree testing and its applications Combinatorica. 23: 365-426. DOI: 10.1007/S00493-003-0025-0  0.656
2002 Arora S, Frieze AM, Kaplan H. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems Mathematical Programming. 92: 1-36. DOI: 10.1007/S101070100271  0.505
1999 Arora S, Karger D, Karpinski M. Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems Journal of Computer and System Sciences. 58: 193-210. DOI: 10.1006/Jcss.1998.1605  0.488
1998 Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems Journal of the Acm. 45: 753-782. DOI: 10.1145/290179.290180  0.425
1998 Arora S, Lund C, Motwani R, Sudan M, Szegedy M. Proof verification and the hardness of approximation problems Journal of the Acm. 45: 501-555. DOI: 10.1145/278298.278306  0.661
1998 Arora S, Safra S. Probabilistic checking of proofs: a new characterization of NP Journal of the Acm. 45: 70-122. DOI: 10.1145/273865.273901  0.322
1997 Arora S, Fagin R. On winning strategies in Ehrenfeucht-Fraïssé games Theoretical Computer Science. 174: 97-121. DOI: 10.1016/S0304-3975(96)00015-1  0.363
1996 Arora S, Leighton FT, Maggs BM. On-line Algorithms for Path Selectionin a Nonblocking Network Siam Journal On Computing. 25: 600-625. DOI: 10.1137/S0097539791221499  0.379
Show low-probability matches.