Sergei Vassilvitskii   I am a currently a Research Scientist at Google. I completed my PhD at Stanford Universty under the supervision of Rajeev Motwani. Prior to that I was an undergraduate at Cornell University.   sergei at cs.stanford.edu

Teaching

• Computational Social Science (Columbia Spring 2013).
• Dealing with Massive Data (Columbia Spring 2011).
• Algorithmic Game Theory (Columbia Fall 2008).

Publications

Recent

• Ravi Kumar, Daniel Lokshtanov, Sergei Vassilvitskii, Andrea Vattani. Near-Optimal Bounds for Cross-Validation via Loss Stability. To appear in ICML 2013 (Atlanta, Georgia)
• Quang Duong, Sharad Goel, Jake Hofman, Sergei Vassilvitskii. Sharding Social Networks. In WSDM 2013 (Rome, Italy)
• Ravi Kumar, Ronny Lempel, Roy Schwartz. Rank Quantization. In WSDM 2013 (Rome, Italy)
• Preston McAfee, Sergei Vassilvitskii. An Overview of Practical Exchange Design. Current Science, Special Issue on Game Theory. Volum 103, Issue 9.
• Hu Fu, Patrick Jordan, Mohammad Mahdian, Uri Nadav, Inbal Talgam-Cohen, Sergei Vassilvitskii. Ad Auctions with Data. In SAGT 2012 (Barcelona, Spain)
• Arpita Ghosh, Mohammad Mahdian, Preston McAfee, Sergei Vassilvitskii. To Match or not to Match: Economics of Cookie Matchignn Online Advertising. EC 2012 (Valencia, Spain)
• Peiji Chen, Wenjing Ma, Srinath Mandalapu, Chandrashekhar Nagarajan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Manfai Yu. Ad Serving using a Compact Allocation Plan. EC 2012 (Valencia, Spain)
• Vijay Bharadwaj, Peiji Chen, Wenjing Ma, Chandrashekhar Nagarajan, John Tomlin, Sergei Vassilvitskii, Erik Vee, Jian Yang. SHALE: an Efficient Algorithm for Allocation of Guaranteed Display Advertising. KDD 2012 (Beijing, China)
• Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii. Scalable k-Means++. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
• Bahman Bahmani, Ravi Kumar, Sergei Vassilvitskii. Densest Subgraph in Streaming and MapReduce. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
• Kevin Lang, Benjamin Moseley, Sergei Vassilvitskii. Handling Forecast Errors while Bidding for Display Advertising. In WWW 2012 (Lyon, France)

Computational Advertising

• Preston McAfee, Sergei Vassilvitskii. An Overview of Practical Exchange Design. Current Science, Special Issue on Game Theory. Volum 103, Issue 9.
• Hu Fu, Patrick Jordan, Mohammad Mahdian, Uri Nadav, Inbal Talgam-Cohen, Sergei Vassilvitskii. Ad Auctions with Data. In SAGT 2012 (Barcelona, Spain)
• Arpita Ghosh, Mohammad Mahdian, Preston McAfee, Sergei Vassilvitskii. To Match or not to Match: Economics of Cookie Matchignn Online Advertising. EC 2012 (Valencia, Spain)
• Peiji Chen, Wenjing Ma, Srinath Mandalapu, Chandrashekhar Nagarajan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Manfai Yu. Ad Serving using a Compact Allocation Plan. EC 2012 (Valencia, Spain)
• Vijay Bharadwaj, Peiji Chen, Wenjing Ma, Chandrashekhar Nagarajan, John Tomlin, Sergei Vassilvitskii, Erik Vee, Jian Yang. SHALE: an Efficient Algorithm for Allocation of Guaranteed Display Advertising. KDD 2012 (Beijing, China)
• Kevin Lang, Benjamin Moseley, Sergei Vassilvitskii. Handling Forecast Errors while Bidding for Display Advertising. In WWW 2012 (Lyon, France)
• Patrick Jordan, Mohammad Mahdian, Sergei Vassilvitskii, Erik Vee. The Multiple Attribution Problem in Pay-Per-Conversion Advertising. In SAGT 2011 (Salerno, Italy) [ pdf ]
• Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii, Andrea Vattani. Hiring a Secretary from a Poset. In EC 2011 (San Jose, CA) [ pdf ]
• Erik Vee, Sergei Vassilvitskii, Jayavel Shanmugasundaram. Optimal Online Assignment with Forecasts. In EC 2010 (Boston, Massachusetts) [ pdf ] [ Tech Report ]
• Sharad Goel, Sebastien Lahaie, Sergei Vassilvitskii. Contract Auctions for Sponsored Search. In WINE 2009 (Rome, Italy) [ pdf ] [ Short Version ]
• Arpita Ghosh, Preston McAfee, Kishore Papineni, Sergei Vassilvitskii. Bidding for Representative Allocations for Display Advertising. In WINE 2009 (Rome, Italy) [ Full Version ]
• Esteban Arcaute, Sergei Vassilvitskii. Social Networks and Stable Matchings in the Job Market. In WINE 2009 (Rome, Italy) [ pdf ]
• Arpita Ghosh, Benjamin Rubinstein, Sergei Vassilvitskii, Martin Zinkevich. Adaptive Bidding for Display Advertising. In WWW 2009 (Madrid, Spain) [ pdf ]
• Rica Gonen, Sergei Vassilvitskii. Sponsored Search Auctions With Reserve Prices: Going Beyond Separability. In WINE 2008 (Shanghai, China) [ pdf ]
• Ning Chen, Arpita Ghosh, Sergei Vassilvitskii. Optimal Envy-Free Pricing with Metric Substitutability. In EC 2008 (Chicago). Full version in SIAM Journal on Computing. [ Conference Version ]
• Andrei Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii. The Hiring Problem and Lake Wobegon Strategies. In SODA 2008 (San Francisco) Full version in SIAM Journal on Computing. [ Full Version ] [ Conference Version ] [ slides ]
• Esteban Arcaute, Adam Kirsch, Ravi Kumar, David Liben-Nowell, Sergei Vassilvitskii. On Threshold Behavior in Query Incentive Networks. In EC 2007 (San Diego) [ pdf ] [ slides ]

MapReduce and Data Analysis

• Ravi Kumar, Daniel Lokshtanov, Sergei Vassilvitskii, Andrea Vattani. Near-Optimal Bounds for Cross-Validation via Loss Stability. To appear in ICML 2013 (Atlanta, Georgia)
• Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii. Scalable k-Means++. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
• Bahman Bahmani, Ravi Kumar, Sergei Vassilvitskii. Densest Subgraph in Streaming and MapReduce. In VLDB 2012 (Istanbul, Turkey)
• Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, Sergei Vassilvitskii. Filtering: A Method for Solving Graph Problems in MapReduce. In SPAA 2011 (San Jose, CA) [ pdf ]
• Siddharth Suri, Sergei Vassilvitskii. Counting Triangles and the Curse of the Last Reducer. In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
• Satyen Kale, Ravi Kumar, Sergei Vassilvitskii. Cross-Validation and Mean-Square Stability. In ICS 2011 (Beijing, China) [ pdf ] [ slides ]
• Sergei Vassilvitskii, Suresh Venkatasubramanian. New Developments in the Theory of Clustering. Tutorial presented at KDD 2010 (Washington DC) [ slides ]
• Ravi Kumar, Sergei Vassilvitskii. Generalized Distances between Rankings. In WWW 2010 (Ralegh, North Carolina) [ pdf ] [ slides ]
• Howard Karloff, Siddarth Suri, Sergei Vassilvitskii. A Model of Computation for MapReduce. In SODA 2010 (Austin, Texas) [ pdf]
• Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, Sergei Vassilvitskii. Finding the Jaccard Median In SODA 2010 (Austin, Texas) [ pdf ]
• Flavio Chierichetti, Ravi Kumar, Sergei Vassilvitskii. Similarity Caching. In PODS 2009 (Providence, Rhode Island) [ pdf ]
• David Arthur, Sergei Vassilvitskii. k-means++: The Advantages of Careful Seeding. In SODA 2007 (New Orleans) [ pdf ] [ slides ]
• David Arthur, Sergei Vassilvitskii. Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method. In FOCS 2006 (Berkeley). Full version in SIAM Journal on Computing. [ Conference Version ] [ slides ]
• David Athur, Sergei Vassilvitskii. How slow is the k-means method? (Original title On the Worst Case Complexity of the k-means Method). In SoCG 2006 (Sedona, Arizona) [ pdf ] [ slides ]
• Rajeev Motwani, Sergei Vassilvitskii. Distinct Value Estimators in Power Law Distributions. In ANALCO 2006 (Miami) [ pdf ] [ slides ]

Indexing

• Quang Duong, Sharad Goel, Jake Hofman, Sergei Vassilvitskii. Sharding Social Networks. In WSDM 2013 (Rome, Italy)
• Marcus Fontoura, Maxim Gurevich, Vanja Josifovski. Efficiently encoding term co-occurences in inverted indexes. In CIKM 2011 (Glasgow, UK)
• George Beskales, Marcus Fontoura, Maxim Gurevich, Sergei Vassilvitskii, Vanja Josifovski. Factorization-based lossless compression of inverted indices. In CIKM 2011 (Glasgow, UK)
• Andrei Broder, Shirshanka Das, Marcus Fontoura, Bhaskar Ghosh, Vanja Josifovski, Jayavel Shanmugasundaram and Sergei Vassilvitskii. Efficiently Evaluating Graph Constraints in Content-Based Publish/Subscribe . In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
• Marcus Fontoura, Suhas Sadanandan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Srihari Venkatesan, Jason Zien. Efficiently Evaluating Complex Boolean Expressions. In SIGMOD 2010 (Indianapolis, Indiana) [ pdf]
• Steven Whang, Chad Brower, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Ramana Yerneni, Hector Garcia-Molina. Indexing Boolean Expressions. In VLDB 2009 (Lyon, France) [ pdf]
• Flavio Chierichetti, Ravi Kumar, Sergei Vassilvitskii. Similarity Caching. In PODS 2009 (Providence, Rhode Island) [ pdf ]
• Sandeep Pandey, Andrei Broder, Flavio Chierichetti, Vanja Josifovski, Ravi Kumar, Sergei Vassilvitskii. Nearest-Neighbor Caching for Content-Match Applications. In WWW 2009 (Madrid, Spain) [ pdf ]
• Ravi Kumar, Kunal Punera, Torsten Suel, Sergei Vassilvitskii. Top-k Aggregation Using Intersections of Ranked Inputs. In WSDM 2009 (Barcelona, Spain) [ pdf ] [ slides ]
• Marcus Fontoura, Vanja Josifovski Ravi Kumar, Christopher Olston, Andrew Tomkins, Sergei Vassilvitskii. Relaxation in Text Search Using Taxonomies. In VLDB 2008 (Auckland, New Zealand) [ pdf ]

Chronological List of Publications

2013

• Ravi Kumar, Daniel Lokshtanov, Sergei Vassilvitskii, Andrea Vattani. Near-Optimal Bounds for Cross-Validation via Loss Stability. To appear in ICML 2013 (Atlanta, Georgia)
• Quang Duong, Sharad Goel, Jake Hofman, Sergei Vassilvitskii. Sharding Social Networks. In WSDM 2013 (Rome, Italy)
• Ravi Kumar, Ronny Lempel, Roy Schwartz. Rank Quantization. In WSDM 2013 (Rome in Italy)

2012

• Preston McAfee, Sergei Vassilvitskii. An Overview of Practical Exchange Design. Current Science, Special Issue on Game Theory. Volum 103, Issue 9.
• Hu Fu, Patrick Jordan, Mohammad Mahdian, Uri Nadav, Inbal Talgam-Cohen, Sergei Vassilvitskii. Ad Auctions with Data. In SAGT 2012 (Barcelona, Spain)
• Arpita Ghosh, Mohammad Mahdian, Preston McAfee, Sergei Vassilvitskii. To Match or not to Match: Economics of Cookie Matchignn Online Advertising. EC 2012 (Valencia, Spain)
• Peiji Chen, Wenjing Ma, Srinath Mandalapu, Chandrashekhar Nagarajan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Manfai Yu. Ad Serving using a Compact Allocation Plan. EC 2013 (Valencia, Spain)
• Vijay Bharadwaj, Peiji Chen, Wenjing Ma, Chandrashekhar Nagarajan, John Tomlin, Sergei Vassilvitskii, Erik Vee, Jian Yang. SHALE: an Efficient Algorithm for Allocation of Guaranteed Display Advertising. KDD 2012 (Beijing, China)
• Kevin Lang, Benjamin Moseley, Sergei Vassilvitskii. Handling Forecast Errors while Bidding for Display Advertising. In WWW 2012 (Lyon, France)
• Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii. Scalable k-Means++. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
• Bahman Bahmani, Ravi Kumar, Sergei Vassilvitskii. Densest Subgraph in Streaming and MapReduce. In VLDB 2012 (Istanbul, Turkey)

2011

• Marcus Fontoura, Maxim Gurevich, Vanja Josifovski. Efficiently encoding term co-occurences in inverted indexes. In CIKM 2011 (Glasgow, UK)
• George Beskales, Marcus Fontoura, Maxim Gurevich, Sergei Vassilvitskii, Vanja Josifovski. Factorization-based lossless compression of inverted indices. In CIKM 2011 (Glasgow, UK)
• Patrick Jordan, Mohammad Mahdian, Sergei Vassilvitskii, Erik Vee. The Multiple Attribution Problem in Pay-Per-Conversion Advertising. In SAGT 2011 (Salerno, Italy) [ pdf ]
• Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii, Andrea Vattani. Hiring a Secretary from a Poset. In EC 2011 (San Jose, CA) [ pdf]
• Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, Sergei Vassilvitskii. Filtering: A Method for Solving Graph Problems in MapReduce. In SPAA 2011 (San Jose, CA) [ pdf]
• Siddharth Suri, Sergei Vassilvitskii. Counting Triangles and the Curse of the Last Reducer. In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
• Andrei Broder, Shirshanka Das, Marcus Fontoura, Bhaskar Ghosh, Vanja Josifovski, Jayavel Shanmugasundaram and Sergei Vassilvitskii. Efficiently Evaluating Graph Constraints in Content-Based Publish/Subscribe . In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
• Satyen Kale, Ravi Kumar, Sergei Vassilvitskii. Cross-Validation and Mean-Square Stability. In ICS 2011 (Beijing, China) [ pdf ] [ slides ]

2010

• Sergei Vassilvitskii, Suresh Venkatasubramanian. New Developments in the Theory of Clustering. Tutorial presented at KDD 2010 (Washington DC) [ slides ]
• Marcus Fontoura, Suhas Sadanandan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Srihari Venkatesan, Jason Zien. Efficiently Evaluating Complex Boolean Expressions. In SIGMOD 2010 (Indianapolis, Indiana) [ pdf]
• Erik Vee, Sergei Vassilvitskii, Jayavel Shanmugasundaram. Optimal Online Assignment with Forecasts. In EC 2010 (Boston, Massachusetts) [ pdf] [ Tech Report ]
• Ravi Kumar, Sergei Vassilvitskii. Generalized Distances between Rankings. In WWW 2010 (Ralegh, North Carolina) [ pdf ] [ slides ]
• Howard Karloff, Siddarth Suri, Sergei Vassilvitskii. A Model of Computation for MapReduce. In SODA 2010 (Austin, Texas) [ pdf ]
• Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, Sergei Vassilvitskii. Finding the Jaccard Median In SODA 2010 (Austin, Texas) [ pdf ]

2009

• Sharad Goel, Sebastien Lahaie, Sergei Vassilvitskii. Contract Auctions for Sponsored Search. In WINE 2009 (Rome, Italy) [ pdf] [ Short Version ]
• Arpita Ghosh, Preston McAfee, Kishore Papineni, Sergei Vassilvitskii. Bidding for Representative Allocations for Display Advertising. In WINE 2009 (Rome, Italy) [ Full Version ]
• Esteban Arcaute, Sergei Vassilvitskii. Social Networks and Stable Matchings in the Job Market. In WINE 2009 (Rome, Italy) [ pdf ]
• Zeinab Abbassi, Sihem Amer-Yahia, Laks Lakshmanan, Sergei Vassilvitskii, Cong Yu. Getting Recommender Systems to Think Outside the Box. In RecSys 2009 (New York) [ pdf ]
• Steven Whang, Chad Brower, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Ramana Yerneni, Hector Garcia-Molina. Indexing Boolean Expressions. In VLDB 2009 (Lyon, France) [ pdf]
• Flavio Chierichetti, Ravi Kumar, Sergei Vassilvitskii. Similarity Caching. In PODS 2009 (Providence, Rhode Island) [ pdf ]
• Sandeep Pandey, Andrei Broder, Flavio Chierichetti, Vanja Josifovski, Ravi Kumar, Sergei Vassilvitskii. Nearest-Neighbor Caching for Content-Match Applications. In WWW 2009 (Madrid, Spain) [ pdf ]
• Arpita Ghosh, Benjamin Rubinstein, Sergei Vassilvitskii, Martin Zinkevich. Adaptive Bidding for Display Advertising. In WWW 2009 (Madrid, Spain) [ pdf ]
• Ravi Kumar, Kunal Punera, Torsten Suel, Sergei Vassilvitskii. Top-k Aggregation Using Intersections of Ranked Inputs. In WSDM 2009 (Barcelona, Spain) [ pdf ] [ slides ]

2008

• Rica Gonen, Sergei Vassilvitskii. Sponsored Search Auctions With Reserve Prices: Going Beyond Separability. In WINE 2008 (Shanghai, China) [ pdf ]
• Marcus Fontoura, Vanja Josifovski Ravi Kumar, Christopher Olston, Andrew Tomkins, Sergei Vassilvitskii. Relaxation in Text Search Using Taxonomies. In VLDB 2008 (Auckland, New Zealand) [ pdf ]
• Ning Chen, Arpita Ghosh, Sergei Vassilvitskii. Optimal Envy-Free Pricing with Metric Substitutability. In EC 2008 (Chicago). Full version in SIAM Journal on Computing. [ Full Version ] [ Conference Version ]
• Andrei Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii. The Hiring Problem and Lake Wobegon Strategies. In SODA 2008 (San Francisco). Full version in SIAM Journal on Computing. [ Full Version ] [ Conference Version ] [ slides ]

2007

• Esteban Arcaute, Adam Kirsch, Ravi Kumar, David Liben-Nowell, Sergei Vassilvitskii. On Threshold Behavior in Query Incentive Networks. In EC 2007 (San Diego) [ pdf ] [ slides ]
• David Arthur, Sergei Vassilvitskii. k-means++: The Advantages of Careful Seeding. In SODA 2007 (New Orleans) [ pdf ] [ slides ]

2006

• David Arthur, Sergei Vassilvitskii. Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method. In FOCS 2006 (Berkeley). Full version in Full version in SIAM Journal on Computing. [ Conference Version ] [ slides ]
• Sergei Vassilvitskii, Eric Brill. Using Web Graph Distance For Relevance Feedback in Web Search. In SIGIR 2006 (Seattle) [ pdf ] [ slides ]
• David Athur, Sergei Vassilvitskii. How slow is the k-means method? (Original title On the Worst Case Complexity of the k-means Method). In SoCG 2006 (Sedona, Arizona) [ pdf ] [ slides ]
• Rajeev Motwani, Sergei Vassilvitskii. Distinct Value Estimators in Power Law Distributions. In ANALCO 2006 (Miami) [ pdf ] [ slides ]

2004

• Sergei Vassilvitskii, Mihalis Yannakakis. Efficiently Computing Succinct Trade-off Curves. In ICALP 2004 (Turku, Finland). Full version in Journal of Theoretical Compute Science. [ Full Version ] [ Conference Version ] [ slides ]

2002

• Sergei Vassilvitskii, Mark Yim, John W. Suh. A Complete, Local and Parallel Reconfiguration Algorithm for Cube Style Modular Robots. In ICRA 2002 (Washington DC). [ pdf ]
• Sergei Vassilvitskii, Jeremy Kubica, Eleanor G. Rieffel, John W. Suh, Mark Yim. On the General Reconfiguration Problem for Expanding Cube Style Modular Robots. In ICRA 2002 (Washington DC) [ pdf ]