[1]   Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber: The angular-metric traveling salesman problem. SIAM J. Comput., 29(3):697–711, 1999. [doi:10.1137/S0097539796312721]

[2]   Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu: Anonymizing tables. In Proc. 10th Internat. Conf. on Database Theory (ICDT’05), pp. 246–258, 2005. [doi:10.1007/978-3-540-30570-5_17]

[3]   Donald Aingworth, Chandra Chekuri, and Rajeev Motwani: Fast estimation of diameter and shortest paths (without matrix multiplication). In Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’96), pp. 547–553, 1996.

[4]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in FOCS’92. [doi:10.1145/278298.278306]

[5]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

[6]   László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy: Checking computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–31, 1991. [doi:10.1145/103418.103428]

[7]   László Babai, Lance Fortnow, and Carsten Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complexity, 1(1):3–40, 1991. [doi:10.1007/BF01200056]

[8]   Brian Babcock, Mayur Datar, and Rajeev Motwani: Sampling from a moving window over streaming data. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’02), pp. 633–634, 2002.

[9]   Brian Babcock, Mayur Datar, Rajeev Motwani, and Liadan O’Callaghan: Maintaining variance and k-medians over data stream windows. In Proc. 22nd Symp. on Principles of Database Systems (PODS’03), pp. 234–243, 2003. [doi:10.1145/773153.773176]

[10]   Bonnie Berger and John Rompel: Simulating (log ^cn)-wise independence in NC. J. ACM, 38(4):1026–1046, 1991. Preliminary version in FOCS’89. [doi:10.1145/115234.115347]

[11]   Sergey Brin, Rajeev Motwani, and Craig Silverstein: Beyond market baskets: Generalizing association rules to correlations. In 1997 ACM SIGMOD Internat. Conf. on Managment of Data, pp. 265–276, 1997. [doi:10.1145/253262.253327]

[12]   Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, and Shalom Tsur: Dynamic itemset counting and implication rules for market basket data. In 1997 ACM SIGMOD Internat. Conf. on Managment of Data, pp. 255–264, 1997. [doi:10.1145/253262.253325]

[13]   Andrei Z. Broder, Marcus Fontoura, Vanja Josifovski, Ravi Kumar, Rajeev Motwani, Shubha U. Nabar, Rina Panigrahy, Andrew Tomkins, and Ying Xu: Estimating corpus size via queries. In 15th Internat. Conf. on Information and Knowledge Managment (CIKM’06), pp. 594–603, 2006. [doi:10.1145/1183614.1183699]

[14]   Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, and Vivek R. Narasayya: Towards estimation error guarantees for distinct values. In Proc. 19th Symp. on Principles of Database Systems (PODS’00), pp. 268–279, 2000. [doi:10.1145/335168.335230]

[15]   Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani: Incremental clustering and dynamic information retrieval. SIAM J. Comput., 33(6):1417–1440, 2004. Preliminary version in STOC’97. [doi:10.1137/S0097539702418498]

[16]   Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, and Craig Silverstein: Constrained TSP and low-power computing. In Proc. 5th Internat. Workshop on Algorithms and Data Structures (WADS’97), pp. 104–115, 1997. [doi:10.1007/3-540-63307-3_51]

[17]   Surajit Chaudhuri, Rajeev Motwani, and Vivek R. Narasayya: On random sampling over joins. In 1999 ACM SIGMOD Internat. Conf. on Managment of Data, pp. 263–274, 1999. [doi:10.1145/304181.304206]

[18]   Chandra Chekuri, Waqar Hasan, and Rajeev Motwani: Scheduling problems in parallel query optimization. In Proc. 14th Symp. on Principles of Database Systems (PODS’95), pp. 255–265, 1995. [doi:10.1145/212433.212471]

[19]   Chandra Chekuri, Richard Johnson, Rajeev Motwani, B. Natarajan, B. Ramakrishna Rau, and Michael S. Schlansker: Profile-driven instruction level parallel scheduling with application to super blocks. In Proc. 29th Ann. IEEE/ACM Internat. Symp. on Microarchitecture (MICRO’96), pp. 58–67, 1996. [doi:10.1109/MICRO.1996.566450]

[20]   Chandra Chekuri and Rajeev Motwani: Minimizing weighted completion time on a single machine. In Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’99), pp. 873–874, 1999.

[21]   Chandra Chekuri, Rajeev Motwani, B. Natarajan, and Clifford Stein: Approximation techniques for average completion time scheduling. SIAM J. Comput., 31(1):146–166, 2001. Preliminary version in SODA’97. [doi:10.1137/S0097539797327180]

[22]   Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani: Maintaining stream statistics over sliding windows. SIAM J. Comput., 31(6):1794–1813, 2002. Preliminary version in SODA’02. [doi:10.1137/S0097539701398363]

[23]   Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman: Computing iceberg queries efficiently. In Proc. 24th Internat. Conf. on Very Large Data Bases (VLDB’98), pp. 299–310, 1998. [VLDB:645924.671338]

[24]    Tomás Feder and Rajeev Motwani: Clique partitions, graph compression and speeding-up algorithms. J. Comput. System Sci., 51(2):261–271, 1995. Preliminary version in STOC’91. [doi:10.1006/jcss.1995.1065]

[25]   Tomás Feder and Rajeev Motwani: Finding large cycles in Hamiltonian graphs. Discr. Appl. Math., 158(8):882–893, 2010. Preliminary version in SODA’05. [doi:10.1016/j.dam.2009.12.006]

[26]   Tomás Feder, Rajeev Motwani, and Carlos S. Subi: Finding long paths and cycles in sparse Hamiltonian graphs. In Proc. 32nd STOC, pp. 524–529, 2000. [doi:10.1145/335305.335368]

[27]   Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy: Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, 1996. Preliminary version in FOCS’91. [doi:10.1145/226643.226652]

[28]   Paul W. Finn, Dan Halperin, Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Christian R. Shelton, and Suresh Venkatasubramanian: Geometric manipulation of flexible ligands. In Proc. Workshop on Appl. Comp. Geometry (WACG’96), volume 1148 of LNCS, pp. 67–78. Springer, 1996. [doi:10.1007/BFb0014486]

[29]   Paul W. Finn, Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Christian R. Shelton, Suresh Venkatasubramanian, and A. Yao: Rapid: Randomized pharmacophore identification for drug design. Comput. Geom., 10(4):263–272, 1998. Preliminary version in SCG’97. [doi:10.1016/S0925-7721(98)00008-X]

[30]   Martin Gavrilov, Piotr Indyk, Rajeev Motwani, and Suresh Venkatasubramanian: Geometric pattern matching: A performance study. In Proc. 15th Ann. Symp. on Computational Geometry (SCG’99), pp. 79–85, 1999. [doi:10.1145/304893.304916]

[31]   Aristides Gionis, Piotr Indyk, and Rajeev Motwani: Similarity search in high dimensions via hashing. In Proc. 25th Internat. Conf. on Very Large Data Bases (VLDB’99), pp. 518–529. Morgan Kaufmann Publishers Inc., 1999. [VLDB:645925.671516]

[32]   Michel X. Goemans and David P. Williamson: .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proc. 26th STOC, pp. 422–431, New York, 1994. ACM Press. [doi:10.1145/195058.195216]

[33]   Michael H. Goldwasser and Rajeev Motwani: Intractability of assembly sequencing: Unit disks in the plane. In Proc. 5th Internat. Workshop on Algorithms and Data Structures (WADS’97), volume 1272 of LNCS, pp. 307–320. Springer, 1997. [doi:10.1007/3-540-63307-3_70]

[34]   Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan: Clustering data streams. In Proc. 41st FOCS, pp. 359–366, 2000. [doi:10.1109/SFCS.2000.892124]

[35]   Leonidas J. Guibas, Rajeev Motwani, and Prabhakar Raghavan: The robot localization problem in two dimensions. In Proc. 3rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’92), pp. 259–268, 1992.

[36]   Waqar Hasan and Rajeev Motwani: Coloring away communication in parallel query optimization. In Proc. 21st Internat. Conf. on Very Large Data Bases (VLDB’95), pp. 239–250, 1995.

[37]   David Hsu, Jean-Claude Latombe, and Rajeev Motwani: Path planning in expansive configuration spaces. Int. J. Comput. Geometry Appl., 9(4-5):495–512, 1999. Preliminary version in ICRA’97.

[38]   Piotr Indyk and Rajeev Motwani: Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. 30th STOC, pp. 604–613. ACM Press, 1998. [doi:10.1145/276698.276876]

[39]   Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh Vempala: Locality-preserving hashing in multidimensional spaces. In Proc. 29th STOC, pp. 618–625, 1997. [doi:10.1145/258533.258656]

[40]   Piotr Indyk, Rajeev Motwani, and Suresh Venkatasubramanian: Geometric matching under noise: Combinatorial bounds and algorithms. In Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’99), pp. 457–465, 1999.

[41]   David R. Karger, Rajeev Motwani, and G. D. S. Ramkumar: On approximating the longest path in a graph. Algorithmica, 18(1):82–98, 1997. Preliminary version in WADS’93. [doi:10.1007/BF02523689]

[42]   David R. Karger, Rajeev Motwani, and Madhu Sudan: Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246–265, 1998. Preliminary version in FOCS’94. [doi:10.1145/274787.274791]

[43]   Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, and Prabhakar Raghavan: Randomized query processing in robot path planning. J. Comput. System Sci., 57(1):50–66, 1998. Preliminary version in STOC’95. [doi:10.1006/jcss.1998.1578]

[44]   Sanjeev Khanna and Rajeev Motwani: Towards a syntactic characterization of PTAS. In Proc. 28th STOC, pp. 329–337, 1996. [doi:10.1145/237814.237979]

[45]   Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh V. Vazirani: On syntactic versus computational views of approximability. SIAM J. Comput., 28(1):164–191, 1998. Preliminary version in FOCS’94. [doi:10.1137/S0097539795286612]

[46]   Aleksandra Korolova, Rajeev Motwani, Shubha U. Nabar, and Ying Xu: Link privacy in social networks. In Proc. 24th Internat. Conf. on Data Engineering (ICDE’08), pp. 1355–1357. IEEE, 2008. [doi:10.1109/ICDE.2008.4497554]

[47]   Nathan Linial and Ori Sasson: Non-expansive hashing. Combinatorica, 18(1):121–132, 1998. Preliminary version in STOC’96. [doi:10.1007/PL00009805]

[48]   Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. [doi:10.1145/146585.146605]

[49]   Gurmeet Singh Manku and Rajeev Motwani: Approximate frequency counts over data streams. In Proc. 28th Internat. Conf. on Very Large Data Bases (VLDB’02), pp. 346–357, 2002. [doi:10.1016/B978-155860869-6/50038-X]

[50]   Rajeev Motwani, Assaf Naor, and Rina Panigrahy: Lower bounds on locality sensitive hashing. SIAM J. Discrete Math., 21(4):930–935, 2007. Preliminary version in SCG’06. [doi:10.1137/050646858]

[51]   Rajeev Motwani, Joseph Naor, and Moni Naor: The probabilistic method yields deterministic parallel algorithms. J. Comput. System Sci., 49(3):478–516, 1994. Preliminary version in FOCS’89. [doi:10.1016/S0022-0000(05)80069-8]

[52]   Rajeev Motwani, Rina Panigrahy, and Ying Xu: Estimating sum by weighted sampling. In Proc. 34th Internat. Colloq. on Automata, Languages and Programming (ICALP’07), pp. 53–64, 2007. [doi:10.1007/978-3-540-73420-8_7]

[53]   Rajeev Motwani, Steven Phillips, and Eric Torng: Non-clairvoyant scheduling. Theoret. Comput. Sci., 130(1):17–47, 1994. Preliminary version in SODA’93. [doi:10.1016/0304-3975(94)90151-1]

[54]   Rajeev Motwani and Prabhakar Raghavan: Deferred data structuring: Query-driven preprocessing for geometric search problems. In Proc. 2nd Ann. Symp. on Computational Geometry (SCG’86), pp. 303–312, 1986. [doi:10.1145/10515.10548]

[55]   Rajeev Motwani, Arvind Raghunathan, and Huzur Saran: Constructive results from graph minors: Linkless embeddings. In Proc. 29th FOCS, pp. 398–409, 1988. [doi:10.1109/SFCS.1988.21956]

[56]   Rajeev Motwani, Jennifer Widom, Arvind Arasu, Brian Babcock, Shivnath Babu, Mayur Datar, Gurmeet Singh Manku, Chris Olston, Justin Rosenstein, and Rohit Varma: Query processing, approximation, and resource management in a data stream management system. In Proc. Conf. on Innovative Data Systems Res. (CIDR’03), 2003.

[57]   Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd: The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.

[58]   Christos H. Papadimitriou and Mihalis Yannakakis: Optimization, approximation, and complexity classes. J. Comput. System Sci., 43(3):425–440, 1991. [doi:10.1016/0022-0000(91)90023-X]

[59]   Adi Shamir: IP = PSPACE. J. ACM, 39(4):869–877, 1992. [doi:10.1145/146585.146609]

[60]   Avi Wigderson: A new approximate graph coloring algorithm. In Proc. 14th STOC, pp. 325–329, 1982. [doi:10.1145/800070.802207]