Rajeev Motwani' Publications

Rajeev Motwani's Publications



-----

Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright ¨ by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

-----

* Publications

* Books & Book Chapters

  • Books
  • Book Chapters
    •

    * Applications

  • Databases, Data Mining, and Information Retrieval
  • Caching and Scheduling
  • Compiler Optimization

    * Physical and Geometric Computing

  • Drug Design
  • Robotics
  • Computational Geometry

    • * Algorithms and Complexity

  • Randomness and Randomized Algorithms
  • Approximation Algorithms and Complexity
  • Online Algorithms
  • Combinatorial Algorithms
  • Combinatorics and Graph Theory
    •  -----

    Return to Rajeev Motwani's home page .

    -----

    * Books & Book Chapters

    Books

  • Approximation Algorithms, Book in preparation. (Preliminary Version: Techincal Report No. STAN-CS-92-1435, Department of Computer Science, Stanford University.)
  • Introduction to Automata and Language Theory, Addison-Wesley, 2000. (with J.E. Hopcroft and J.D. Ullman)
    See also the Book Support Web Page.
  • Randomized Algorithms, Cambridge University Press, 1995. (with P. Raghavan)
    See also the Book Support Web Page.
  • Database Theory - ICDT 2003, Springer-Verlag, 2003. (with D. Calvanese and M. Lenzerini )
  • SIAM Data Mining, SIAM, 2002. (with R. Grossman, J. Han, V. Kumar, and H. Mannila)
  • Foundations of Computer Science, IEEE Computer Society, 1998.

    • Book Chapters

  • A Survey of Query Auditing Techniques for Data Privacy., Privacy-Preserving Data Mining: Models and Algorithms (edited by Charu Aggarwal and Philip S. Yu), Springer, 2008. (with S. Nabar, K. Kenthapadi, and N. Mishra)
  • Load Shedding in Data Stream Systems., Data Streams: Models and Algorithms (edited by Charu Aggarwal), Springer, 2007. (with B. Babcock and M. Datar)
  • The Sliding Window Computation Model and Results., Data Streams: Models and Algorithms (edited by Charu Aggarwal), Springer, 2007. (with M. Datar)
  • Asymptotic Polynomial Time Approximation Schemes., Handbook of Approximation Algorithms and Metaheuristics (edited by Teofilo F. Gonzalez), Chapman&Hall/CRC, 2007. (with L. O'Callaghan and A. Zhu)
  • Probabilistic Algorithms, Handbook of Discrete and Combinatorial Mathematics (edited by Ken Rosen), CRC Press, 1999. (with P. Raghavan)
  • An Overview of Randomized Algorithms. (with P. Raghavan) Probabilistic Methods in Algorithmic Discrete Mathematics, Ed. Habib, M, McDiarmid, C., Ramirez-Alfonsin, J., and Reed, B., (Springer, 1998).
  • Coloring Away Communication in Parallel Query Optimization. (with W. Hasan) Readings in Database Systems, 3rd Edition, Ed. Stonebraker, M., and Hellerstein, J., (Morgan-Kaufmann Publishers, 1998).
  • Randomized Algorithms, Algorithms and Theory of Computation Handbook (edited by Mikhail Atallah), CRC Press, 1998. (with P. Raghavan)
  • Randomization in Approximation Algorithms, Approximation Algorithms (edited by Dorit Hochbaum), PWS Publishers, 1995. (with J. Naor and P. Raghavan)
  • Randomized Algorithms, The Computer Science and Engineering Handbook (edited by A. Tucker), CRC Press, 1996. (with P. Raghavan)
    • -----

    * Applications

    Databases, Data Mining, and Information Retrieval

  • Link Privacy in Social Networks. (with Korolova, Nabar, and Xu) Proceedings of the Seventeenth ACM Conference on Information and Knowledge Management (CIKM), 2008.
  • Efficient Algorithms for Masking and Finding Quasi-Identifiers. (with Y. Xu) SIAM International Workshop on Practical Privacy-Preserving Data Mining 2008.
  • Auditing SQL Queries. (with Thomas and Nabar) Proceedings of the 21st International Conference on Data Engineering (ICDE), 2008.
  • Link Privacy in Social Networks. (Abbreviated Version) (with Korolova, Nabar, and Xu) Proceedings of the 21st International Conference on Data Engineering (ICDE), 2008.
  • Lower bounds on Locality Sensitive Hashing. (with A. Naor and R. Panigrahy)
    SIAM Journal on Discrete Mathematics. 21(2007): 930-935.
    Preliminary version: Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 2006
  • Querying Priced Information in Databases: the Conjunctive Case. (with Carmo, Feder, Kohayakawa, Laber, O'Callaghan, Panigrahy, and Thomas) ACM Transactions on Algorithms 3(1), 2007
  • Tracing the Path: New Model and Algorithms for Collaborative Filtering. (with S. Vassilvitskii) Proceedings of the 3rd IEEE International Workshop on Web Personalization, Recommender Systems and Intelligent User Interfaces (ICDE 2007).
  • Auditing a Batch of SQL Queries. (with D. Thomas and S. Nabar) Third International Workshop on Privacy Data Management (ICDE 2007).
  • Estimating Corpus Size via Queries. (with Broder, Fontura, Josfovski, Kumar, Nabar, Panigrahy, Tomkins, and Xu) Proceedings of the Fifteenth ACM Conference on Information and Knowledge Management (CIKM), 2006.
  • Keyword Generation for Search Engine Advertising. (with A. Joshi) Proceedings of the ICDM Workshop on Foundations of Data Mining, 2006.
  • Towards Robustness in Query Auditing. (with K. Kenthapadi, B. Marthi, N. Mishra, and S. Nabar)
    Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), 2006.
  • Query Optimization over Web Services. (with U. Srivastava, K. Munagala, and J. Widom)
    Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), 2006.
  • Evolution of Page Popularity under Random Web Graph Models. (with Y. Xu)
    Proceedings of the ACM Symposium on Principles of Databases (PODS), 2006.
  • Truthful auctions for pricing search keywords. (with G. Aggarwal and A. Goel)
    Proceedings of the 2006 ACM Conference on Electronic Commerce, 2006.
  • Distinct Value Estimation for Power Law Distributions. (with S. Vassilvitskii)
    Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO 06), 2006
  • Robust identification of fuzzy duplicates. (with S. Chaudhuri and V. Ganti)
    Proceedings of the 21st International Conference on Data Engineering (ICDE), 2005.
  • Adaptive Caching for Continuous Queries. (with S. Babu, K. Munagala, and J. Widom)
    Proceedings of the 21st International Conference on Data Engineering (ICDE), 2005.
  • Two Can Keep a Secret: A Distributed Architecture for Secure Database Services. (with G. Aggarwal, M. Bawa, P. Ganesan, H. Garcia-Molina, K. Kenthapadi, U. Srivastava, D. Thomas, and Y. Xu)
    Proceedings of the Conference on Innovative Data Systems Research (CIDR), 2005.
  • The Pipelined Set Cover Problem. (with K. Munagala, S. Babu, and J. Widom)
    Proceedings of the Tenth International Conference on Database Theory (ICDT), 2005.
  • Algorithms for the Database Layout Problem. (with G. Aggarwal, T. Feder, R. Panigrahy, and A. Zhu)
    Proceedings of the Tenth International Conference on Database Theory (ICDT), 2005.
  • Anonymizing Tables. (with G. Aggarwal, T. Feder, K. Kenthapadi, R. Panigrahy, D. Thomas, and A. Zhu)
    Proceedings of the Tenth International Conference on Database Theory (ICDT), 2005.
  • Operator Scheduling in Data Stream Systems. (with B. Babcock, S. Babu, M. Datar, and D. Thomas)
    The VLDB Journal, 13 (2004): 333-353.
  • Enabling Privacy for the Paranoids. (with G. Aggarwal, M. Bawa, P. Ganesan, H. Garcia-Molina, K. Kenthapadi, N. Mishra, U. Srivastava, D. Thomas, J. Widom, and Y. Xu)
    Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), 2004.
  • The Price of Validity in Dynamic Networks. (with M. Bawa, A. Gionis, and H. Garcia-Molina)
    Joural of Computer and System Sciences (Special Issue on Database Theory 2004) 73 (2007): 245-264.
    Preliminary Version: Proceedings of the 2004 ACM SIGMOD Conference on Management of Data, 2004.
  • Adaptive Ordering of Pipelined Stream Filters. (with S. Babu, S. Munagala, J. Niishizawa, and J. Widom)
    Proceedings of the 2004 ACM SIGMOD Conference on Management of Data, 2004.
  • Aggregating Correlated Data in Sensor Networks. (with M. Enachescu, A. Goel, and R. Govindan)
    Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2004).
  • Scale Free Aggregation in Sensor Networks. (with M. Enachescu, A. Goel, and R. Govindan)
    Theoretical Computer Science, 2007.
    Preliminary Version: Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2004.
  • Load Shedding Techniques for Aggregation Queries in Stream Systems. (with B. Babcock and M. Datar)
    Proceedings of the 20th International Conference on Data Engineering, 2004.
  • Caching Queues in Memory Buffers. (with D. Thomas)
    Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004.
  • Chain: Operator Scheduling for Memory Minimization in Stream Systems. (with B. Babcock, S. Babu,  and M. Datar)
    Proceedings of the 2003 ACM SIGMOD Conference on Management of Data, 2003.
  • Robust and Efficient Fuzzy Match for Online Data Cleaning. (with S. Chaudhuri, K. Ganjam, and V. Ganti)
    Proceedings of the 2003 ACM SIGMOD Conference on Management of Data, 2003.
  • Maintaining Variance and K-Medians over Data Stream Windows. (with B. Babcock, M. Datar, and L. O'Callaghan)
    Proceedings of the ACM Symposium on Principles of Databases (PODS), 2003.
  • Load shedding techniques for data stream systems. (with B. Babcock and M. Datar)
    Workshop on Management and Processing of Data Streams (FCRC 2003).
  • STREAM: The Stanford Stream Data Manager. (with the STREAM Group)
    Bulletin of the Technical Committee on Data Engineering 26 (2003): 19-26.
  • Clustering Data Streams: Theory and Practice. (with S. Guha, A. Meyerson, N. Mishra, and L. O'Callaghan)
    IEEE Transactions on Knowledge and Data Engineering, 15 (2003): 515-528.
  • Query Processing, Approximation, and Resource Management in a Data Stream Management System. (with J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein,  and R. Varma)
    Proceedings of the Conference on Innovative Data Systems Research (CIDR), 2003.
  • Challenges in Web Search Engines. (with M. Henzinger and C. Silverstein)
    Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), 2003.
    Earlier version: SIGIR Forum 36 (2002): 11-22.
  • Computing Shortest Paths with Uncertainty. (with T. Feder, L. O'Callaghan, C. Olston, and R. Panigrahy)
    Journal of Algorithms, 62(1):1-18 (2007).
    Preliminary Version: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, 2003.
  • Models and Issues in Data Stream Systems. (with B. Babcock, S. Babu, M. Datar, and J.Widom)
    Proceedings of the ACM Symposium on Principles of Database System (PODS), 2002.
  • Approximate Frequency Counts over Streaming Data. (with G.S. Manku)
    Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), 2002.
  • Maintaining Stream Statistics over Sliding Windows. (with M. Datar, A. Gionis, and P. Indyk)
    SIAM Journal on Computing, 31 (2002): 1794-1813.
    Preliminary version: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
  • Sampling From a Moving Window Over Streaming Data. (with B. Babcock and M. Datar)
    Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
  • High-Performance Clustering of Streams and Large Data Sets. (with L. O'Callaghan, N. Mishra, A. Meyerson, and S. Guha)
    Proceedings of the 18th International Conference on Data Engineering, 2002.
  • Overcoming Limitations of Sampling for Aggregation Queries. (with S. Chaudhuri, G. Das, M. Datar, and V. Narasayya)
    Proceedings of the 17th International Conference on Data Engineering, 2001.
  • Clustering Data Streams. (with S. Guha, N. Mishra, and L. O'Callaghan)
    Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000.
  • Mining the Stock Market: Cluster Discovery. (with M. Gavrilov, D. Angelov, and P. Indyk)
    Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2000.
  • Towards Estimation Error Guarantees for Distinct Values. (with M. Charikar, S. Chaudhuri, and V. Narasayya)
    Proceedings of the Nineteenth ACM Symposium on Principles of Database System, 2000.
  • Computing the Median with Uncertainty. (with T. Feder, R. Panigrahy, C. Olston, and J. Widom)
    SIAM Journal on Computing, 32(2003): 538-547.
    Proceedings of the 32nd Annual ACM Symposium on Theory of Computing    , 2000.
  • Dynamic Miss-Counting Algorithms: Finding Implication and Similarity Rules with Confidence Pruning. (with S. Fujiwara and J.D. Ullman)
    Proceedings of the 16th International Conference on Data Engineering (ICDE). 2000.
  • Finding Interesting Associations without Support Pruning. (with E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, J.D. Ullman, and C. Yang)
    IEEE Transactions on Knowledge and Data Engineering,, 13(2001): 64-78.
    Preliminary Version: Proceedings of the 16th International Conference on Data Engineering (ICDE), 2000.
  • On Sampling and Relational Operators. (with S. Chaudhuri)
    Bulletin of the Technical Committee on Data Engineering., 22 (1999): 35-40.
  • Similarity Search in High Dimensions via Hashing. (with A. Gionis and P. Indyk)
    Proceedings of the 25th International Conference on Very Large Data Bases (VLDB), 1999.
  • On Random Sampling over Joins. (with S. Chaudhuri and V. Narasayya)
    Proceedings of the 1999 ACM SIGMOD Conference on Management of Data, 1999.
  • What can you do with a Web in your Pocket? (with S. Brin, L. Page, and T. Winograd)
    Bulletin of the Technical Committee on Data Engineering, 21(1998): 37-47.
  • Scalable Techniques for Mining Causal Structures. (with S. Brin, C. Silverstein, and J.D. Ullman)
    Data Mining and Knowledge Discovery, 4(2000): 163-192.
    Proceedings of the 24th International Conference on Very Large Data Bases (VLDB), 1998.
  • Computing iceberg queries efficiently. (with M. Fang, N. Shivakumar, H. Garcia-Molica, and J.D. Ullman)
    Proceedings of the 24th International Conference on Very Large Data Bases (VLDB), 1998.
  • Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. (with P. Indyk)
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998.
  • Random Sampling for Histogram Construction: How much is enough? (with S. Chaudhuri and V. Narasayya)
    Proceedings of the 1998 ACM SIGMOD Conference on Management of Data, 1998.
  • Extracting Schema from Semistructured Data. (with S. Nestorov and S. Abiteboul)
    Proceedings of the 1998 ACM SIGMOD Conference on Management of Data, 1998.
  • Query Flocks: A Generalization of Association Rule Mining. (with D. Tsur, J.D. Ullman, S. Abiteboul, C. Clifton, S. Nestorov and A. Rosenthal)
    Proceedings of the 1998 ACM SIGMOD Conference on Management of Data, 1998.
  • Position Abstract on Data Mining.
    UW/Microsoft Summer Research Institute on Data Mining 1997.
  • The PageRank Citation Ranking: Bringing Order to the Web. (with S. Brin, L. Page, and T. Winograd)
    Technical Report, Stanford Digital Libraries, 1998.
  • Inferring Structure in Semistructured Data. (with S. Nestorov and S. Abiteboul)
    Workshop on Management of Semistructured Data, PODS/SIGMOD, 1997, pp 42-48.
    Special Issue on Management of Semistructured Data, SIGMOD Record. 26, 1997.
  • Storage management for evolving databases. (with J. Kleinberg, P. Raghavan, and S. Venkatasubramanian)
    Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 353-363.
  • Dynamic Itemset Counting and Implication Rules for Market Basket Data. (with S. Brin, S. Tsur, and J.D. Ullman)
    1997 ACM SIGMOD Conference on Management of Data, 1997, pp. 255-264.
  • Beyond Market Baskets: Generalizing Association Rules to Correlations. (with S. Brin and C. Silverstein)
    Data Mining and Knowledge Discovery    , 2 (1998), pp. 39-68.
    Preliminary Version: ACM SIGMOD Conference on Management of Data, 1997, pp. 265-276.
  • Scheduling Problems in Parallel Query Optimization. (with C. Chekuri and W. Hasan)
    Proceedings of the Fourteenth ACM Symposium on Principles of Database Systems (PODS), 1995, pp. 255-265.
  • Coloring Away Communication in Parallel Query Optimization. (with W. Hasan)
    Proceedings of the 21st International Conference on Very Large Data Bases (VLDB), 1995, pp. 239-250.
    Readings in Database Systems, 3rd Edition, Ed. Stonebraker, M., and Hellerstein, J., (Morgan-Kaufmann Publishers, 1998).
  • Optimization Algorithms for Exploiting the Parallelism-Communication Trade-off in Pipelined Parallelism. (with W. Hasan)
    Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 1994, pp. 36-47.
  • Modeling Communication in Parallel Query Optimization. (with C. Chekuri and W. Hasan)
    In preparation.
    Preliminary version: Technical Report HPL-94-50, HP Laboratories, 1994.

    • Caching and Scheduling

  • On Identifying Stable Ways to Configure Systems. (with G. Aggarwal, M. Datar, and N. Mishra)
    Proceedings of the International Conference on Autonomic Computing (ICAC-04), 2004.
  • Switch Scheduling via Randomized Edge Coloring. (with G. Aggarwal, D. Shah, and A. Zhu)
    Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.
  • Modeling Correlations in Web-Traces and Implications for Designing Replacement Policies. (with K. Psounis, A. Zhu, and B. Prabhakar)
    Computer Networks, (2004).
  • Combining Request Scheduling with Web Caching. (with T. Feder, R. Panigrahy, S. Seiden, R. van Stee, and A. Zhu)
    Theoretical Computer Science (Special Issue in Memory of Steve Seiden), (2004).
  • The Load Rebalancing Problem. (with G. Aggarwal and A. Zhu)
    Journal of Algorithms 60(2006): 42-59.
    Preliminary Version: Proceedings of the ACM Annual Symposium on Parallelism in Algorithms and Architectures, 2003.
  • Web Caching With Request Reordering. (with T. Feder, R. Panigrahy, and A. Zhu)
    Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
  • Minimizing Weighted Completion Time on a Single Machine. (with C. Chekuri)
    Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999.
  • Precedence Constrained Scheduling to Minimize Weighted Completion Time on a Single Machine. (with C. Chekuri)
    Discrete Applied Mathematics, 98 (1999): 29-38. (Editor's Choice, Edition 1999.)
    Preliminary version: Technical Report STAN-CS-TN-97-58, Department of Computer Science, Stanford University, 1997.
  • Approximation Techniques for Average Completion Time Scheduling. (with C. Chekuri, B.K. Natarajan, and C. Stein)
    Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.
    Full Version
  • Online Scheduling with Lookahead: Multipass Assembly Lines. (with V. Saraswat and E. Torng)
    Preliminary version: Technical Report CPS-94-41, Department of Computer Science, Michigan State University, August 1994.
    INFORMS Journal on Computing, Volume 10, Number 3, pages 331-340, Summer 1998.
  • Scheduling Problems in Parallel Query Optimization. (with C. Chekuri and W. Hasan)
    Proceedings of the Fourteenth ACM Symposium on Principles of Database Systems (PODS), 1995, pp. 255-265.
  • Non-Clairvoyant Scheduling. (with S. Phillips and E. Torng)
    Theoretical Computer Science (Special Issue on Dynamic and On-Line Algorithms), 130 (1994), pp. 17-47.
    Preliminary Version: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 422-431.
  • A New Performance Metric for the Evaluation of Hard-Real-Time Scheduling Algorithms. (with E. Torng)
    Technical Report CPS-94-44, Department of Computer Science, Michigan State University (1994).

    •      Compiler Optimization

    -----

    * Physical and Geometric Computing

    Drug Design

  • Geometric Pattern Matching: A Performance Study. (with M. Gavrilov, P. Indyk and S. Venkatasubramanian)
    Proceedings of the Fifteenth Annual ACM Symposium on Computational Geometry, 1999.
  • Geometric Matching under Noise: Combinatorial Bounds and Algorithms. (with P. Indyk and S. Venkatasubramanian)
    Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999.
  • Search Techniques for Rational Drug Design. (with P. Finn, L. Kavraki, J-C. Latombe, and S. Venkatasubramanian)
    IASTED International Conference on Intelligent Information Systems, 1997.
  • RAPID: Randomized Pharmacophore Identificationin Drug Design. (with P. Finn, L. Kavraki, J-C. Latombe, C. Shelton, S. Venkatasubramanian, and A. Yao)
    Computational Geometry: Theory and Applications 10 (1998): 263-272.
    Preliminary version: Thirteenth Annual ACM Symposium on Computational Geometry, pp. 324-333, 1997.
  • Efficient Clustering of Molecular Conformations. (with B. Cook and L. Kavraki)
    Second CGC Workshop on Computational Geometry. 1997.
  • Geometric Manipulation of Flexible Molecules. (with P. Finn, D. Halperin, L. Kavraki, J-C. Latombe, C.~Shelton, and S. Venkatasubramanian)
    Preliminary version: Proceedings of ACM Workshop on Applied Computational Geometry, pp. 67-78, 1996.
    Applied Computational Geometry: Towards Geometric Engineering, Ed. Lin, M.C., and Manocha, D., pp. 67-78, (Springer-Verlag Lecture Notes in Computer Science, volume 1148, 1996).
  • The Dynamic Servers Problem. (with M. Charikar and D. Halperin)
    Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.
  • Dynamic Maintenance of Kinematic Structures. (with D. Halperin and J-C. Latombe)
    2nd International Workshop on Algorithmic Foundations of Robotics (WAFR), 1996, pp. 155-170.

    • Robotics

  • Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling Techniques. (with D. Hsu, L.E. Kavraki, and J-C. Latombe)
    Third IEEE Workshop on Randomized Parallel Computing, 1998.
    Advances in Randomized Parallel Computing, Ed. P.M. Pardalos and S. Rajasekaran, pp. 159-182, (Kluwer Academic Publishers, Boston, MA, 1999).
  • On Finding Narrow Passages with Probabilistic Roadmap Planners. (with D. Hsu, L.E. Kavraki, J-C. Latombe, and S. Sorkin)
    3rd International Workshop on Algorithmic Foundations of Robotics, 1998.
  • Motion Planning with Visibility Constraints: Building an Autonomous Observer. (with H.H. Gonzalez-Banos, L, Guibas, J-C. Latombe, S.M. LaValle, D. Lin, and C. Tomasi)
    Proceedings of the 8th International Symposium on Robotics Research Hayama, Japan, October 1997, pp. 95-101.
  • The Dynamic Servers Problem. (with M. Charikar and D. Halperin)
    Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.
  • Dynamic Maintenance of Kinematic Structures. (with D. Halperin and J-C. Latombe)
    2nd International Workshop on Algorithmic Foundations of Robotics (WAFR), 1996, pp. 155-170.
  • Path Planning and Expansive Configuration Spaces. (with D. Hsu and J-C. Latombe)
    Special issue on the CGC Workshop on Computational Geometry, International Journal of Computational Geometry and Applications, 9(1999): 495-512.
    IEEE International Conference on Robotics and Automation, 1997, pp. 2719-2726.
  • Nonholonomic Motion Planning for Pushing a Disk Among Obstacles. (with P. Agarwal, J-C. Latombe, and P. Raghavan)
    IEEE International Conference on Robotics and Automation, 1997, pp. 3124-3129.
  • Finding an Unpredictable Target in a Workspace with Obstacles. (with L.J. Guibas, J-C. Latombe, S.M. Lavalle, and D. Lin)
    IEEE International Conference on Robotics and Automation, 1997, pp. 737-742.
  • Visibility-Based Pursuit-Evasion in a Polygonal Environment. (with L.J. Guibas, J-C. Latombe, S.M. Lavalle, and D. Lin)
    Proceedings of the Workshop on Algorithms and Data Structures, 1997.
  • A Visibility-Based Pursuit-Evasion Problem. (with L.J. Guibas, J-C. Latombe, S.M. Lavalle, and D. Lin)
    Special issue on the CGC Workshop on Computational Geometry, International Journal of Computational Geometry and Applications, 9(1999): 471-494.
    • IEEE International Conference on Robotics and Automation, 1997, pp. 737-742.
  • On the Complexity of Assembly Planning. (with M. Goldwasser)
    Special issue on the CGC Workshop on Computational Geometry, International Journal of Computational Geometry and Applications, 9(1999): 371-418.
  • Intractability of Assembly Sequencing: Unit Disk in the Plane. (with M. Goldwasser)
    Proceedings of the Workshop on Algorithms and Data Structures, 1997.
  • Complexity Measures for Assembly Sequences. (with M. Goldwasser and J-C. Latombe)
    IEEE International Conference on Robotics and Automation, 1996, pp. 1851-1857.
    Preliminary Version: Technical Report No. STAN-CS-TN-95-25, Department of Computer Science, Stanford University.
  • The Robot Localization Problem. (with L. Guibas and P. Raghavan)
    Algorithmic Foundations of Robotics (edited by K. Goldberg, D. Halperin, J-C. Latombe, and R. Wilson), A. K. Peters (Boston), 1995, pp. 269-282.
  • Approximation Algorithms for Robot Grasp and Delivery. (with P. Chalasani and A. Rao)
    2nd International Workshop on Algorithmic Foundations of Robotics (WAFR), 1996, pp. 347-362.
    Preliminary version: Los Alamos Unclassified Report LA-UR 95-2582, Los Alamos National Laboratory, New Mexico (1995).
  • Approximating Capacitated Routing and Delivery Problems. (with P. Chalasani)
    SIAM Journal on Computing, 28 (1999): 2133-2149.
    Preliminary version: Technical Report STAN-CS-TN-95-24, Department of Computer Science, Stanford University (1995).
  • A Random Sampling Framework for Path Planning. (with J. Barraquand, L. Kavraki, J-C. Latombe, T-Y. Li, and P. Raghavan)
    International Journal of Robotics Research, 16, 1997.
    Proceedings of the 7th International Symposium on Robotics Research, G.~Giralt and G.~Hirzinger (eds.), Springer, New York, NY, 1996, pp.~249-264.
  • Randomized Query Processing in Robot Path Planning. (with L. Kavraki, J-C. Latombe, and P. Raghavan)
    Special Issue for the STOC conference, Journal of Computer and System Sciences, 57(1998): 50-60.
    Preliminary Version: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 1995, pp. 353-362.

    • Computational Geometry

  • On the Graph Turnpike Problem. (with T. Feder)
    Information Processing Letters 109 (2009): 774-776.
  • Lower bounds on Locality Sensitive Hashing. (with A. Naor and R. Panigrahy)
    SIAM Journal on Discrete Mathematics. 21(2007): 930-935.
    Preliminary version: Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 2006
  • Similarity Search in High Dimensions via Hashing. (with A. Gionis and P. Indyk)
    Proceedings of the 25th International Conference on Very Large Data Bases (VLDB), 1999.
  • Geometric Pattern Matching: A Performance Study. (with M. Gavrilov, P. Indyk and S. Venkatasubramanian)
    Proceedings of the Fifteenth Annual ACM Symposium on Computational Geometry, pp 79-85, 1999.
  • Geometric Matching under Noise: Combinatorial Bounds and Algorithms. (with P. Indyk and S. Venkatasubramanian)
    Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999.
  • Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. (with P. Indyk)
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998.
  • Search Techniques for Rational Drug Design. (with P. Finn, L. Kavraki, J-C. Latombe, and S. Venkatasubramanian)
    IASTED International Conference on Intelligent Information Systems, 1997.
  • RAPID: Randomized Pharmacophore Identificationin Drug Design. (with P. Finn, L. Kavraki, J-C. Latombe, C. Shelton, S. Venkatasubramanian, and A. Yao) Computational Geometry: Theory and Applications 10 (1998): 263-272.
    Preliminary version: Thirteenth Annual ACM Symposium on Computational Geometry, pp. 324-333, 1997.
  • Geometric Manipulation of Flexible Molecules. (with P. Finn, D. Halperin, L. Kavraki, J-C. Latombe, C.~Shelton, and S. Venkatasubramanian)
    Preliminary version: Proceedings of ACM Workshop on Applied Computational Geometry, pp. 67-78, 1996.
    Applied Computational Geometry: Towards Geometric Engineering, Ed. Lin, M.C., and Manocha, D., pp. 67-78, (Springer-Verlag Lecture Notes in Computer Science, volume 1148, 1996).
  • The Robot Localization Problem in Two Dimensions. (with L. Guibas and P. Raghavan)
    SIAM Journal on Computing 26 (1997);1120-1138.
    Preliminary Version: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 259-268.
  • Perfect Graphs and Orthogonally Convex Covers. (with A. Raghunathan and H. Saran)
    SIAM Journal on Discrete Mathematics, 2 (1989), pp. 371-392.
  • Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach. (with A. Raghunathan and H. Saran)
    Special Issue for Symposium on Computational Geometry, Journal of Computer and System Sciences, 40 (1989), pp. 19-48.
    Preliminary Version: Fourth Annual ACM Symposium on Computational Geometry, 1988, pp. 211-223.
  • Deferred Data Structuring. (with R.M. Karp and P. Raghavan)
    SIAM Journal on Computing, 17 (1988), pp. 883-902.
  • Deferred Data Structuring: Query-driven Preprocessing for Geometric Search Problems. (with P. Raghavan)
    Proceedings of the Second Annual ACM Symposium on Computational Geometry, 1986, pp. 303-312.
    • -----

    * Algorithms and Complexity

    Randomness and Randomized Algorithms

  • Estimating Sum via Weighted Sampling. (with R. Panigrahy and Y. Xu)
    Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), 2007
  • Lower bounds on Locality Sensitive Hashing. (with A. Naor and R. Panigrahy)
    SIAM Journal on Discrete Mathematics. 21(2007): 930-935.
    Preliminary version: Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 2006
  • Fractional Matching via Balls-and-Bins. (with R. Panigrahy and Y. Xu)
    Proceedings of the 10th International Workshop on Randomization and Computation (RANDOM06), 2006
  • Evolution of Page Popularity under Random Web Graph Models. (with Y. Xu)
    Proceedings of the ACM Symposium on Principles of Databases (PODS), 2006.
  • A Simple Approach for Pricing Equity Options with Markov Switching State Variables. (with D. Aingworth and S. Das)
    Quantitative Finance, 2006.
  • Distinct Value Estimation for Power Law Distributions. (with S. Vassilvitskii)
    Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO 06), 2006
  • Aggregating Correlated Data in Sensor Networks. (with M. Enachescu, A. Goel, and R. Govindan)
    Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2004).
  • Scale Free Aggregation in Sensor Networks. (with M. Enachescu, A. Goel, and R. Govindan)
    Theoretical Computer Science, 2007.
    Preliminary Version: Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2004.
  • Switch Scheduling via Randomized Edge Coloring. (with G. Aggarwal, D. Shah, and A. Zhu)
    Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.
  • Approximate Frequency Counts over Streaming Data. (with G.S. Manku)
    Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), 2002.
  • Sampling From a Moving Window Over Streaming Data. (with B. Babcock and M. Datar)
    Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
  • Overcoming Limitations of Sampling for Aggregation Queries. (with S. Chaudhuri, M. Datar, and V. Narasayya)
    Proceedings of the 17th International Conference on Data Engineering, 2001.
  • Towards Estimation Error Guarantees for Distinct Values. (with M. Charikar, S. Chaudhuri, and V. Narasayya)
    Proceedings of the Nineteenth ACM Symposium on Principles of Database System, 2000.
  • Similarity Search in High Dimensions via Hashing. (with A. Gionis and P. Indyk)
    Proceedings of the 25th International Conference on Very Large Data Bases (VLDB), 1999.
  • On Random Sampling over Joins. (with S. Chaudhuri and V. Narasayya)
    Proceedings of the 1999 ACM SIGMOD Conference on Management of Data, pp 263-274, 1999.
  • Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. (with P. Indyk)
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998.
  • Random Sampling for Histogram Construction: How much is enough? (with S. Chaudhuri and V. Narasayya)
    Proceedings of the 1998 ACM SIGMOD Conference on Management of Data, 1998.
  • Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling Techniques. (with D. Hsu, L.E. Kavraki, and J-C. Latombe)
    Third IEEE Workshop on Randomized Parallel Computing, 1998.
  • On Finding Narrow Passages with Probabilistic Roadmap Planners. (with D. Hsu, L.E. Kavraki, J-C. Latombe, and S. Sorkin)
    3rd International Workshop on Algorithmic Foundations of Robotics, 1998.
  • Randomized Algorithms. (with P. Raghavan)
    Cambridge University Press, 1995.
  • Probabilistic Algorithms. (with P. Raghavan)
    Handbook of Discrete and Combinatorial Mathematics (edited by Ken Rosen and Andrew Odlyzko), CRC Press, 1998.
  • A Survey of Randomized Algorithms. (with P. Raghavan)
    50th Anniversary Issue of ACM Computing Surveys, 28 (1996):33-37.
  • Randomized Algorithms.
    Handbook of Computer Science and Engineering (edited by A. Tucker), (with P. Raghavan)
    CRC Press, 1996, pp. 141-161.
  • Approximating Probability Distributions Using Small Sample Spaces. (with Y. Azar and J. Naor)
    Combinatorica 18(1998): 151-171.
  • Locality-Preserving Hashing in Multidimensional Spaces. (with P. Indyk, P. Raghavan, and S. Vempala)
    Preliminary Version: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997. pp. 618-625.
  • Derandomization via Approximation: An NC Algorithm for Minimum Cuts. (with D. Karger)
    SIAM Journal on Computing. 26(1997): 255-272.
    Preliminary Version: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994, pp. 497-506.
  • A Random Sampling Framework for Path Planning. (with J. Barraquand, L. Kavraki, J-C. Latombe, T-Y. Li, and P. Raghavan)
    International Journal of Robotics Research, 16, 1997.
    Proceedings of the 7th International Symposium on Robotics Research, G.~Giralt and G.~Hirzinger (eds.), Springer, New York, NY, 1996, pp.~249-264.
  • Randomized Query Processing in Robot Path Planning. (with L. Kavraki, J-C. Latombe, and P. Raghavan)
    Special issue for the STOC conference, Journal of Computer and System Sciences, 57(1998): 50-60.
    Preliminary Version: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 1995, pp. 353-362.
  • The Probabilistic Method Yields Deterministic Parallel Algorithms. (with J. Naor and M. Naor)
    Special issue for the FOCS conference, Journal of Computer and System Sciences, 49 (1994), pp. 478-516.
    Preliminary Version: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 8-13.
  • Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. (with A. Kamath, K. Palem, and P. Spirakis)
    Random Structures and Algorithms, 7 (1995), pp.~59-80.
    Preliminary Version: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 592-603.
  • Average-case Analysis of Algorithms for Matchings and Related Problems.
    Journal of the ACM, 41 (1994), pp. 1329-1356.
    Preliminary Version: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 550-561.
  • Probabilistic Analysis of Network Flow Algorithms. (with R.M. Karp and N. Nisan)
    Mathematics of Operations Research, 18 (1993), pp. 71-97.
  • Stable Husbands. (with D.E. Knuth and B. Pittel)
    Random Structures and Algorithms, 1 (1990), pp. 1-14.
    Preliminary Version: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 397-404.

    • Approximation Algorithms and Complexity

  • Querying Priced Information in Databases: the Conjunctive Case. (with Carmo, Feder, Kohayakawa, Laber, O'Callaghan, Panigrahy, and Thomas) ACM Transactions on Algorithms 3(1), 2007
  • A Simple Approach for Pricing Equity Options with Markov Switching State Variables. (with D. Aingworth and S. Das)
    Quantitative Finance, 2006.
  • Finding Large Cycles in Hamiltonian Graphs. (with T. Feder)
    Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.
  • The Pipelined Set Cover Problem. (with K. Munagala, S. Babu, and J. Widom)
    Proceedings of the Tenth International Conference on Database Theory (ICDT), 2005.
  • Algorithms for the Database Layout Problem. (with G. Aggarwal, T. Feder, R. Panigrahy, and A. Zhu)
    Proceedings of the Tenth International Conference on Database Theory (ICDT), 2005.
  • Anonymizing Tables. (with G. Aggarwal, T. Feder, K. Kenthapadi, R. Panigrahy, D. Thomas, and A. Zhu)
    Proceedings of the Tenth International Conference on Database Theory (ICDT), 2005.
  • Algorithms for Multi-Product Pricing. (with G. Aggarwal, T. Feder, and A. Zhu)
    Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004.
  • Switch Scheduling via Randomized Edge Coloring. (with G. Aggarwal, D. Shah, and A. Zhu)
    Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.
  • The Load Rebalancing Problem. (with G. Aggarwal and A. Zhu)
    Journal of Algorithms 60(2006): 42-59.
    Preliminary Version: Proceedings of the ACM Annual Symposium on Parallelism in Algorithms and Architectures, 2003.
  • Representing Graph Metrics with Fewest Edges. (with T. Feder, A. Meyerson, L. O'Callaghan, and R. Panigrahy)
    Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, 2003.
  • Computing Shortest Paths with Uncertainty. (with T. Feder, L. O'Callaghan, C. Olston, and R. Panigrahy)
    Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, 2003.
  • Clustering Data Streams: Theory and Practice. (with S. Guha, A. Meyerson, N. Mishra, and L. O'Callaghan)
    IEEE Transactions on Knowledge and Data Engineering, 15 (2003): 515-528.
  • High-Performance Clustering of Streams and Large Data Sets. (with L. O'Callaghan, N. Mishra, A. Meyerson, and S. Guha)
    Proceedings of the 18th International Conference on Data Engineering, 2002.
  • Clustering Data Streams. (with S. Guha, N. Mishra, and L. O'Callaghan)
    Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000.
  • Finding Long Paths and Cycles in Sparse Hamiltonian Graphs. (with T. Feder, and C. Subi)
    Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
  • Computing the Median with Uncertainty. (with T. Feder, R. Panigrahy, C. Olston, and J. Widom)
    SIAM Journal on Computing, 32(2003): 538-547.
    Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
  • Accurate Approximations for Asian Options. (with D. Aingworth and J. Oldham)
    Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000.
  • Minimizing Weighted Completion Time on a Single Machine. (with C. Chekuri)
    Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999.
  • Precedence Constrained Scheduling to Minimize Weighted Completion Time on a Single Machine. (with C. Chekuri)
    Discrete Applied Mathematics, 98 (1999): 29-38.
    Preliminary version: Technical Report STAN-CS-TN-97-58, Department of Computer Science, Stanford University, 1997.
  • The Dynamic Servers Problem. (with M. Charikar and D. Halperin)
    Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.
  • Storage management for evolving databases. (with J. Kleinberg, P. Raghavan, and S. Venkatasubramanian)
    Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 353-363.
  • Approximation Algorithms.
    Preliminary Version: Technical Report No. STAN-CS-92-1435, Department of Computer Science, Stanford University.
  • Randomization in Approximation Algorithms. (with J. Naor and P. Raghavan)
    Approximation Algorithms (edited by Dorit Hochbaum), PWS Publishers, 1996.
  • Intractability of Assembly Sequencing: Unit Disk in the Plane. (with M. Goldwasser)
    Proceedings of the Workshop on Algorithms and Data Structures, 1997.
  • Incremental Clustering and Dynamic Information Retrieval. (with M. Charikar, C. Chekuri, and T. Feder)
    SIAM Journal on Computing 33(2004): 1417-1440.
    Preliminary Version: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 626-635.
  • Approximation Techniques for Average Completion Time Scheduling. (with C. Chekuri, B.K. Natarajan, and C. Stein)
    Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.
    Full Version
  • The Angular-Metric Traveling Salesman Problem. (with A. Aggarwal, D. Coppersmith, S. Khanna, and B. Schieber)
    SIAM Journal on Computing, 29 (2000): 697-711.
    Preliminary Version: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.
  • Towards a Syntactic Characterization of PTAS. (with S. Khanna)
    Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996.
  • Approximation Algorithms for Robot Grasp and Delivery. (with P. Chalasani and A. Rao)
    2nd International Workshop on Algorithmic Foundations of Robotics (WAFR), 1996, pp. 347-362.
    Preliminary version: Los Alamos Unclassified Report LA-UR 95-2582, Los Alamos National Laboratory, New Mexico (1995).
  • Approximating Capacitated Routing and Delivery Problems. (with P. Chalasani)
    SIAM Journal on Computing, 28 (1999): 2133-2149.
    Preliminary version: Technical Report STAN-CS-TN-95-24, Department of Computer Science, Stanford University (1995).
  • Constrained TSP and Low-Power Computing. (with M. Charikar, P. Raghavan, and C. Silverstein)
    Proceedings of the Workshop on Algorithms and Data Structures, 1997.
  • On Syntactic versus Computational Views of Approximability.
    SIAM Journal on Computing, 28 (1998) 164-191.
    Preliminary Version: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 819-830. (with S. Khanna, M. Sudan, and U. Vazirani)
    Also available as: ECCC Report No. TR95-023, Electronic Colloquim on Computational Complexity, http://www.eccc.uni-trier.de/eccc/, 1995.
  • Approximate Graph Coloring by Semidefinite Programming. (with D. Karger and M. Sudan)
    Journal of the ACM 45 (1998): pp. 246-265.
    Preliminary Version: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 2-13.
  • On Approximating the Longest Path in a Graph. (with D. Karger and G. Ramkumar)
    Algorithmica (Special issue on Approximation Algorithms). 18 (1997): 82-98
    Preliminary Version: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science (Springer-Verlag), vol. 709, 1993, pp. 421-430.
  • Proof Verification and Intractability of Approximation Problems. (with S. Arora, C. Lund, M. Sudan, and M. Szegedy)
    Journal of the ACM, 45 (1998): 501-555.
    Preliminary Version: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 14-23.
  • Approximation Algorithms for the Largest Common Subtree Problem. (with S. Khanna and F.F. Yao)
    Preliminary version: Report No. STAN-CS-95-1545, Department of Computer Science, Stanford University (1995).
  • On Exact and Approximate Cut Covers of Graphs. (with J. Naor)
    Technical Report STAN-CS-TN-94-11, Department of Computer Science, Stanford University (1994).

    • Online Algorithms

  • On Identifying Stable Ways to Configure Systems. (with G. Aggarwal, M. Datar, and N. Mishra)
    Proceedings of the International Conference on Autonomic Computing (ICAC-04), 2004.
  • Caching Queues in Memory Buffers. (with D. Thomas)
    Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004.
  • Switch Scheduling via Edge Randomized Coloring. (with G. Aggarwal, D. Shah, and A. Zhu)
    Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.
  • Modeling Correlations in Web-Traces and Implications for Designing Replacement Policies. (with K. Psounis, A. Zhu, and B. Prabhakar)
    Computer Networks, (2004).
  • Combining Request Scheduling with Web Caching. (with T. Feder, R. Panigrahy, S. Seiden, R. van Stee, and A. Zhu)
    Theoretical Computer Science (Special Issue in Memory of Steve Seiden), (2004).
  • Web Caching With Request Reordering. (with T. Feder, R. Panigrahy, and A. Zhu)
    Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
  • The Dynamic Servers Problem. (with M. Charikar and D. Halperin)
    Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.
  • Storage management for evolving databases. (with J. Kleinberg, P. Raghavan, and S. Venkatasubramanian)
    Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 353-363.
  • Constrained TSP and Low-Power Computing. (with M. Charikar, P. Raghavan, and C. Silverstein)
    Proceedings of the Workshop on Algorithms and Data Structures, 1997.
  • Online Scheduling with Lookahead: Multipass Assembly Lines. (with V. Saraswat and E. Torng)
    Preliminary version: Technical Report CPS-94-41, Department of Computer Science, Michigan State University, August 1994.
    INFORMS Journal on Computing, Volume 10, Number 3, pages 331-340, Summer 1998.
  • Non-Clairvoyant Scheduling. (with S. Phillips and E. Torng)
    Theoretical Computer Science (Special Issue on Dynamic and On-Line Algorithms), 130 (1994), pp. 17-47.
    Preliminary Version: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 422-431.
  • A New Performance Metric for the Evaluation of Hard-Real-Time Scheduling Algorithms. (with E. Torng)
    Technical Report CPS-94-44, Department of Computer Science, Michigan State University (1994).
  • The Greedy Algorithm is Optimal for On-Line Edge Coloring. (with A. Bar-Noy and J. Naor)
    Information Processing Letters, 44 (1992), pp. 251-253.

    • Combinatorial Algorithms

  • On the Graph Turnpike Problem. (with T. Feder)
    Information Processing Letters 109(2009): 774-776.
  • Truthful auctions for pricing search keywords. (with G. Aggarwal and A. Goel)
    Proceedings of the 2006 ACM Conference on Electronic Commerce.
  • Representing Graph Metrics with Fewest Edges. (with T. Feder, A. Meyerson, L. O'Callaghan, and R. Panigrahy)
    Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, 2003.
  • Computing Shortest Paths with Uncertainty. (with T. Feder, L. O'Callaghan, C. Olston, and R. Panigrahy)
    Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, 2003.
  • A Combinatorial Algorithm for MAX CSP. (with M. Datar, T. Feder, A. Gionis, and R. Panigrahy)
    Information Processing Letters 85 (2003): 307-315.
  • Maintaining Stream Statistics over Sliding Windows. (with M. Datar, A. Gionis, and P. Indyk)
    SIAM Journal on Computing, 31 (2002): 1794-1813.
    Preliminary version: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
  • Computing the Median with Uncertainty. (with T. Feder, R. Panigrahy, C. Olston, and J. Widom)
    SIAM Journal on Computing, 32(2003): 538-547.
    Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
  • Worst-case Time Bounds for Coloring and Satisfiability Problems. (with T. Feder)
    Journal of Algorithms 45 (2002): 192-201.
  • The Dynamic Servers Problem. (with M. Charikar and D. Halperin)
    Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.
  • Dynamic Maintenance of Kinematic Structures. (with D. Halperin and J-C. Latombe)
    2nd International Workshop on Algorithmic Foundations of Robotics (WAFR), 1996, pp. 155-170.
  • Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication). (with D. Aingworth and C. Chekuri)
    Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996.
  • Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication). (with D. Aingworth, C. Chekuri, and P. Indyk)
    SIAM Journal on Computing, 28 (1999): 1167-1181.
  • On Certificates and Lookahead in Dynamic Graph Problems. (with S. Khanna and R. Wilson)
    Algorithmica, 21 (1998): 377-394.
    Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996.
    Preliminary version: Technical Report SAND94-3128, Sandia National Laboratories (1995).
  • On Diameter Verification and Boolean Matrix Multiplication. (with J. Basch and S. Khanna)
    Technical Report No. STAN-CS-95-1544, Department of Computer Science, Stanford University (1995).
  • Clique Partitions, Graph Compression and Speeding-up Algorithms. (with T. Feder)
    Special Issue for the STOC conference, Journal of Computer and System Sciences, 51 (1995): 261-272.
    Preliminary Version: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 123-133.
  • Realization of Matrices and Directed Graphs.
    Journal of Algorithms, 27 (1998), pp. 61-74.
  • The Set Maxima Problem: Some Linear-time Algorithms. (with A. Bar-Noy and J. Naor)
    SIAM Journal on Discrete Mathematics, 5 (1992), pp. 1-9.
  • The Greedy Algorithm is Optimal for On-Line Edge Coloring. (with A. Bar-Noy and J. Naor)
    Information Processing Letters, 44 (1992), pp. 251-253.
  • Deferred Data Structuring. (with R.M. Karp and P. Raghavan)
    SIAM Journal on Computing, 17 (1988), pp. 883-902.
  • Deferred Data Structuring: Query-driven Preprocessing for Geometric Search Problems. (with P. Raghavan)
    Proceedings of the Second Annual ACM Symposium on Computational Geometry, 1986, pp. 303-312.

    • Combinatorics and Graph Theory

  • Approximating the Longest Cycle Problem in Sparse Graphs. (with T. Feder, and C. Subi)
    SIAM Journal on Computing, 31 (2002): 1596-1607.
  • Finding Long Paths and Cycles in Sparse Hamiltonian Graphs. (with T. Feder, and C. Subi)
    Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
  • Object Accessibility for Java is Decidable. (with R. Panigrahy, V. Saraswat, and S. Venkatasubrmanian)
    Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
  • Complexity of Partition Problems. (with T. Feder, P. Hell, and S. Klein)
    SIAM Journal on Discrete Mathematics, 16 (2003), pp. 449-478.
    Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp 464-472, 1999.
    Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999 (abstract only).
  • The difference between a graph and its square. (with D. Aingworth and F. Harary)
    Utilitas Mathematica, 54 (1998), pp. 223-228.
  • Computing Roots of Graphs is Hard. (with M. Sudan)
    Discrete Applied Mathematics, 54 (1994), pp. 81-88.
  • Perfect Graphs and Orthogonally Convex Covers. (with A. Raghunathan and H. Saran)
    SIAM Journal on Discrete Mathematics, 2 (1989), pp. 371-392.
  • Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach. (with A. Raghunathan and H. Saran)
    Special Issue for Symposium on Computational Geometry, Journal of Computer and System Sciences, 40 (1989), pp. 19-48.
    Preliminary Version: Fourth Annual ACM Symposium on Computational Geometry, 1988, pp. 211-223.
  • Constructive Results from Graph Minors: Linkless Embeddings. (with A. Raghunathan and H. Saran)
    Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 398-411.
    • -----

    Return to top .

    -----

    Return to Rajeev Motwani's home page .

    -----