Recent Publications
Eliciting Properties of Probability DistributionsLambert, Pennock and Shoham
Proceedings of the 9th ACM Conference on Electronic Commerce (EC), 2008.
Self-Financed Wagering Mechanisms for Forecasting
Lambert, Langford, Wortman, Chen, Reeves, Shoham and Pennock
Proceedings of the 9th ACM Conference on Electronic Commerce (EC), 2008.
Complexity of Combinatorial Market Makers
Chen, Fortnow, Lambert, Pennock and Wortman
Proceedings of the 9th ACM Conference on Electronic Commerce (EC), 2008.
Link Privacy in Social Networks
Korolova, Motwani, Nabar and Xu
Proceedings of the 21st International Conference on Data Engineering (ICDE), 2008.
Reputation Markets
Yan and Van Roy
Proceedings of ACM SIGCOMM Netecon, 2008.
Advertisement Allocation for Generalized Second Pricing Schemes
Goel, Mahdian, Nazerzadeh and Saberi
4th Workshop on Ad Auctions, 2008.
Dynamic Cost-Per-Action Mechanisms and Applications to Online Advertising
Nazerzadeh, Saberi and Vohra
Proceedings of the 17th International World Wide Web Conference (WWW), 2008.
Price Based Protocols For Fair Resource Allocation: Convergence Time Analysis and Extension to Leontief Utilities
Goel and Nazerzadeh
Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.
Stochastic Kronecker Graphs
Mahdian and Xu
5th Workshop on Algorithms and Models for the Web-Graph (WAW), 2007.
Searchability in Random Graphs
Arcaute, Chen, Kumar, Liben-Nowell, Mahdian, Nazerzadeh and Xu
5th Workshop on Algorithms and Models for the Web-Graph (WAW), 2007.
Estimating Sum by Weighted Sampling
Motwani, Panigrahy and Xu
Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), 2007.
Allocating Online Advertisement Space with Unreliable Estimates
Mahdian, Nazerzadeh and Saberi
Proceedings of the 8th ACM Conference on Electronic Commerce (EC), 2007.
Approximating Nash Equilibria Using Small-Support Strategies
Feder, Nazerzadeh and Saberi
Proceedings of the 8th ACM Conference on Electronic Commerce (EC), 2007.
Lower Bounds on Locality Sensitive Hashing
Motwani, Naor and Panigrahy
SIAM Journal on Discrete Mathematics, 21, 2007.
Preliminary Version: 22nd Annual ACM Symposium on Computational Geometry 2006.
Querying Priced Information in Databases: the Conjunctive Case
Carmo, Feder, Kohayakawa, Motwani, O'Callaghan, Panigrahy and Thomas
ACM Transactions on Algorithms 3(1), 2007.
Tracing the Path: new Model and Algorithms for Recommendation Systems
Motwani and Vassilvitskii
Workshop on Web Personalization, Recommender Systems and Intelligent User Interfaces (colocated with ICDE), 2007.
Estimating Corpus Size via Queries
Broder, Fontura, Josfovski, Kumar, Motwani, Nabar, Panigrahy, Tomkins and Xu
Proceedings of the 15th ACM Conference on Information and Knowledge Management (CIKM), 2006.
Keyword Generation for Search Engine Advertising
Joshi and Motwani
ICDM Workshop on Foundations of Data Mining, 2006.
Query Optimization over Web Services
Srivastava, Motwani, Munagala and Widom
Proceedings of the 32nd International Conference on Very Large Databases (VLDB), 2006.
Balanced Allocations on Graphs
Kenthapadi and Panigrahy
SODA 2006.
Evolution of Page Popularity under Random Web Graph Models
Motwani and Xu
Proceedings of the ACM Symposium on Principles of Databases (PODS) 2006.
Truthful Auctions for Pricing Search Keywords
Aggarwal, Goel, and Motwani
ACM Conference on Electronic Commerce 2006.
Analyzing BitTorrent and Related Peer-to-Peer Networks
Arthur and Panigrahy
SODA 2006.
Distinct Value Estimation under Zipfian Distributions
Motwani and Vassilvitskii
ANALCO 2006.
Achieving Anonymity via Clustering in a Metric Space
Aggarwal, Feder, Kenthapadi, Panigrahy, Thomas and Zhu
PODS 2006.
Sublinear Projective Clustering With Outliers
Mishra, Motwani, and Vassilvitskii
Dagstuhl Workshop on Sublinear Algorithms, 2005.
Avoiding Ballot Stuffing in eBay-like Reputation Systems
Bhattacharjee and Goel
ACM SIGCOMM workshop on Economics of peer-to-peer systems 2005.
Achieving Stability in Networks of Input-Queued Switches using a Local Online Scheduling Policy
Nabar, Kumar, Bayati, Keshavarzian
GLOBECOM 2005.
Decentralized Algorithms using both Local and Random Probes for P2P Load Balancing
Kenthapadi and Manku
SPAA 2005
Privacy Preserving OLAP
Agrawal, Srikant, and Thomas
ACM SIGMOD Conference on Management of Data (SIGMOD), 2005.
Simulatable Auditing
Kenthapadi, Mishra, and Nissim
ACM Conference on Principles of Database Systems (PODS), 2005.
Derandomization of Auctions
Aggarwal, Fiat, Goldberg, Hartline, Immorlica, Karlin and Sudan
Symposium on Theory of Computing (STOC), Baltimore, May 2005.
Robust identification of fuzzy duplicates
Chaudhuri, Ganti, and Motwani
International Conference on Data Engineering (ICDE), 2005.
Efficient Hashing with Lookups in two Memory Accesses
Panigrahy
ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005.
Anonymizing Tables
Aggarwal, Feder, Kenthapadi, Motwani, Panigrahy, Thomas, and Zhu
International Conference on Database Theory (ICDT05), January 2005.
Making Eigenvector-based Reputation Systems Robust to Collusion
Zhang, Goel, Govindan, Mason and Van Roy
Workshop on Algorithms and Models for the Web Graph(WAW04), 2004.
The Price of Validity in Dynamic Networks
Bawa, Gionis, Motwani, and Garcia-Molina
ACM SIGMOD Conference on Management of Data, 2004.
Towards Protocol Equilibrium With Oblivious Routers
Dutta, Goel and Heidemann
IEEE Infocom, 2004.
Enabling Privacy for the Paranoids
Agarwal, Bawa, Ganesan, Garcia-Molina, Kenthapadi, Mishra, Motwani, Srivastava, Thomas, Widom, and Xu
International Conference on Very Large Data Bases (VLDB04), August 2004.
Modeling Correlations in Web-Traces and Implications for Designing Replacement Policies
Psounis, Zhu, Prabhakar, and Motwani
Computer Networks 45 (2004): 379-398.
Combining request scheduling with web caching
Feder, Motwani, Panigrahy, Seiden, van Stee, and Zhu
Theoretical Computer Science 324(2-3): 201-218 (2004)
Algorithms for Multi-Product Pricing
Aggarwal, Feder, Motwani, and Zhu
International Colloquium on Automata, Languages and Programming (ICALP04), July 2004.
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model
Bhattacharjee and Goel
IEEE Foundations of Computer Science, 2003.
The Design of a Distributed Rating Scheme for Peer-to-peer Systems
Dutta, Goel, Govindan and Zhang
Workshop on Economic Issues in Peer-to-Peer Systems, June 5-6, 2003.
Challenges in Web Search Engines
Henzinger, Motwani, and Silverstein
Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), 2003.
Earlier version: SIGIR Forum 36 (2002): 11-22.
Incrementally Improving Lookup Latency in Distributed Hash Table Systems
Zhang, Goel and Govindan
ACM Sigmetrics, 2003.
Oblivious AQM and Nash Equilibria
Dutta, Goel and Heidemann
IEEE Infocom, 2003.
Past Publications
Switch Scheduling via Edge Randomized ColoringAggarwal, Motwani, Shah, and Zhu
IEEE Symposium on Foundations of Computer Science (FOCS), 2003.
The Load Rebalancing Problem
Aggarwal, Motwani, and Zhu
ACM Annual Symposium on Parallelism in Algorithms and Architectures, 2003.
Clustering Data Streams: Theory and Practice
Guha, Meyerson, Mishra, Motwani, and O'Callaghan
IEEE Transactions on Knowledge and Data Engineering, 15 (2003): 515-528.
Exact Sampling of TCP Window States
Goel and Mitzenmacher
IEEE Infocom, 2002.
Using the Small-World Model to Improve Freenet Performance
Zhang, Goel and Govindan
IEEE Infocom, 2002.
Web Caching With Request Reordering
Feder, Motwani, Panigrahy, and Zhu
ACM-SIAM Symposium on Discrete Algorithms, 2002.
High-Performance Clustering of Streams and Large Data Sets
O'Callaghan, Mishra, Meyerson, Motwani, and Guha
Proceedings of the 18th International Conference on Data Engineering (ICDE), 2002.
Mining the Stock Market: Cluster Discovery
Gavrilov, Angelov, Indyk, and Motwani
ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2000.
Clustering Data Streams
Guha, Mishra, Motwani, and O'Callaghan
IEEE Symposium on Foundations of Computer Science (FOCS), 2000.
Similarity Search in High Dimensions via Hashing
Gionis, Indyk, and Motwani
International Conference on Very Large Data Bases (VLDB), 1999.
The Dynamic Servers Problem
Charikar and Halperin
ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998.
The PageRank Citation Ranking: Bringing Order to the Web
Brin, Page, Motwani, and Winograd
Technical Report, Stanford Digital Libraries, 1998.
What can you do with a Web in your Pocket?
Page, Brin, Motwani, and Winograd
Bulletin of the Technical Committee on Data Engineering, 21(1998): 37-47.
Extracting Schema from Semistructured Data
Nestorov, Abiteboul, and Motwani
ACM SIGMOD Conference on Management of Data, 1998.
Computing iceberg queries efficiently
Fang, Shivakumar, Garcia-Molica, Motwani, Ullman
International Conference on Very Large Data Bases (VLDB), 1998.
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Indyk and Motwani
ACM Symposium on Theory of Computing (STOC), 1998.
Incremental Clustering and Dynamic Information Retrieval
Charikar, Chekuri, Feder, and Motwani
ACM Symposium on Theory of Computing (STOC), 1997, pp. 626-635.
Storage management for evolving databases
Kleinberg, Motwani, Raghavan, and Venkatasubramanian
IEEE Symposium on Foundations of Computer Science (FOCS), 1997, pp. 353-363.