Sergei Vassilvitskii

Sergei Vassilvitskii

I am a Distinguished Scientist and Senior Research Director at Google New York. My team is responsible for incubating BigQuery Machine Learning, developing battery saving features in Android, and is now working on the Privacy Sandbox.

Previously I was a Research Scientist at Yahoo! Research and an Adjunct Assistant Professor at Columbia University. 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).

Recent Publications

T. Lavastida, M. Dinitz, S. Im, B. Moseley. Controlling Tail Risk in Online Ski-Rental SODA 2024 (Alexandria, Virginia)
S. Im, R. Kumar, S. Lattanzi, B. Moseley, S. Vassilvitskii. Massively Parallel Computation: Algorithms and Applications. Foundations and Trends in Optimization.
N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, A. Thakurta How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy. Tutorials at: ICML 2023, KDD 2023
R. Busa-Fekete, A. Munoz Medina, U. Syed, S. Vassilvitskii Label differential privacy and private training data release. ICML 2023 (Honolulu, Hawaii)
S. Davies, B. Moseley, S. Vassilvitskii, Y. Wang Predictive Flows for Faster Ford-Fulkerson. ICML 2023 (Honolulu, Hawaii)
S. Lattanzi, O. Svensson, S. Vassilvitskii Speeding Up Bellman Ford via Minimum Violation Permutations. ICML 2023 (Honolulu, Hawaii)
M. Khodak, K. Amin, T. Dick, S. Vassilvitskii Learning-augmented private algorithms for multiple quantile release. ICML 2023 (Honolulu, Hawaii)
K. Amin, M. Joseph, M. Ribiero, S. Vassilvitskii. Easy Differentially Private Linear Regression. ICLR 2023 (Kingali, Rwanda)
CJ Carey, T. Dick, A. Epasto, A. Javanmard, J. Karlin, S. Kumar, A. Munoz Medina, V. Mirrokni, G. Henrique Nunes, S. Vassilvitskii, P. Zhong. Measuring Re-identification Risk SIGMOD 2023.
A. Epasto, J. Mao, A. Munoz Medina, V. Mirrokni, S. Vassilvitskii, P. Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estimators ITCS 2023.

All Publications

Google Scholar DBLP Chronological List

By topic: Algorithms with Predictions Privacy Algorithmic Machine Learning Computational Advertising MapReduce and Data Analysis Indexing

Algorithms with Predictions

S. Davies, B. Moseley, S. Vassilvitskii, Y. Wang Predictive Flows for Faster Ford-Fulkerson. ICML 2023 (Honolulu, Hawaii)
S. Lattanzi, O. Svensson, S. Vassilvitskii Speeding Up Bellman Ford via Minimum Violation Permutations. ICML 2023 (Honolulu, Hawaii)
M. Khodak, K. Amin, T. Dick, S. Vassilvitskii Learning-augmented private algorithms for multiple quantile release. ICML 2023 (Honolulu, Hawaii)
M. Khodak, N. Balcan, A. Talwalkar, S. Vassilvitskii. Learning Predictions for Algorithms with Predictions NeurIPS 2022.
M. Dinitz, S. Im, T. Lavastida, B. Moseley, S. Vassilvitskii. Algorithms with Prediction Portfolios NeurIPS 2022.
M. Mitzenmacher, S. Vassilvitskii. Algoirthms with Predictions Communications of the ACM, 2022.
M. Dinitz, S. Im, T. Lavastida, B. Moseley, S. Vassilvitskii. Faster Matchings via Learned Duals NeurIPS 2021 (Virtual)
P. Dütting, S. Lattanzi, R. Paes Leme, S. Vassilvitskii. Secretaries with Advice. EC 2021 (Virtual)
B. Moseley, S. Vassilvitskii, Y. Wang. Hierarchical Clustering in General Metric Spaces using Approximate Nearest Neighbors. AISTATS 2021 (Virtual)
M. Mitzenmacher, S. Vassilvitskii. Algorithms with Predictions.
T. Lavastida, B. Moseley, S. Lattanzi, S. Vassilvitskii. Online Scheduling via Learned Weights. SODA 2020 (Salt Lake City)
T. Lykouris, S. Vassilvitskii. Competitive Caching with Machine Learned Advice. ICML 2018 (Stockholm).
A. Medina Munoz, S. Vassilvitskii. Revenue Optimization with Approximate Bid Predictions. NIPS 2017 (Los Angeles, CA).

Privacy

N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, A. Thakurta How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy. Tutorials at: ICML 2023, KDD 2023
R. Busa-Fekete, A. Munoz Medina, U. Syed, S. Vassilvitskii Label differential privacy and private training data release. ICML 2023 (Honolulu, Hawaii)
CJ Carey, T. Dick, A. Epasto, A. Javanmard, J. Karlin, S. Kumar, A. Munoz Medina, V. Mirrokni, G. Henrique Nunes, S. Vassilvitskii, P. Zhong. Measuring Re-identification Risk SIGMOD 2023.
K. Amin, M. Joseph, M. Ribiero, S. Vassilvitskii. Easy Differentially Private Linear Regression. ICLR 2023 (Kingali, Rwanda)
A. Epasto, J. Mao, A. Munoz Medina, V. Mirrokni, S. Vassilvitskii, P. Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estimators ITCS 2023.
N. Ponomareva, J. Bastings, S. Vassilvitskii. Training Text-to-Text Transformers with Privacy Guarantees ACL 2022.
V. Cohen-Addad, A. Epasto, S. Lattanzi, V. Mirrokni, A. Munoz Medina, D. Saulpic, C. Schwiegelshohn, S. Vassilvitskii. Scalable Differentially Private Clustering via Hierarchically Separated Trees. KDD 2021
H. Esfandiari, V. Mirrokni, U. Syed, S. Vassilvitskii. Label differential privacy via clustering AISTATS 2022 (Virtual)
A. Muñoz Medina, U. Syed, S. Vassilvitskii, E. Vitercik. Private optimization without constraint violations. AISTATS 2021 (Virtual)
K. Amin, T. Dick, A. Kulesza, A. Munoz Medina, S. Vassilvitskii. Differentially Private Covariance Estimation. NeurIPS 2019 (Vancouver)
K. Amin, A. Kulesza, A. Munoz Medina, S. Vassilvitskii. Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy. ICML 2019 (Long Beach)

Algorithmic Machine Learning

M. Dinitz, S. Im, T. Lavastida, B. Moseley, S. Vassilvitskii. Faster Matchings via Learned Duals NeurIPS 2021 (Virtual)
S. Lattanzi, B. Moseley, S. Vassilvitskii, Y. Wang, R. Zhou. Robust Online Correlation Clustering NeurIPS 2021 (Virtual)
B. Moseley, S. Vassilvitskii, Y. Wang. Hierarchical Clustering in General Metric Spaces using Approximate Nearest Neighbors. AISTATS 2021 (Virtual)
A. Muñoz Medina, U. Syed, S. Vassilvitskii, E. Vitercik. Private optimization without constraint violations. AISTATS 2021 (Virtual)
P. Dütting, S. Lattanzi, R. Paes Leme, S. Vassilvitskii. Secretaries with Advice. EC 2021 (Virtual)
M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Sliding Window Algorithms for k-Clustering Problems. NeurIPS 2020 (Virtual)
S. Ahmadian, A. Epasto, M. Knittel, R. Kumar, M. Mahdian, B. Moseley, P. Pham, S. Vassilvitskii, Y. Wang. Fair Hierarchical Clustering.. NeurIPS 2020 (Virtual)
T. Lavastida, B. Moseley, S. Lattanzi, S. Vassilvitskii. Online Scheduling via Learned Weights. SODA 2020 (Salt Lake City)
A. Bhaskara, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Residual Based Sampling for Online Low Rank Approximation. FOCS 2019 (Baltimore)
K. Amin, T. Dick, A. Kulesza, A. Munoz Medina, S. Vassilvitskii. Differentially Private Covariance Estimation. NeurIPS 2019 (Vancouver)
K. Amin, A. Kulesza, A. Munoz Medina, S. Vassilvitskii. Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy. ICML 2019 (Long Beach)
J. Gillenwater, A. Kulesza, Z. Mariet, S. Vassilvitskii. A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes.. ICML 2019 (Long Beach)
F. Chierichetti, R. Kumar, S. Lattanzi, S. Vassilvitskii. Matroids, Matchings, and Fairness. AISTATS 2019 (Okinawa, Japan).
M. R. Karimi, A. Krause, S. Lattanzi, S. Vassilvitskii. Consistent Online Optimization: Convex and Submodular. AISTATS 2019 (Okinawa, Japan).
J. Gillenwater, A. Kulesza, Z. Mariet, S. Vassilvitskii. Maximizing Induced Cardinality Under a Determinantal Point Process. NeurIPS 2018 (Montreal, CA).
A. Medina Munoz, S. Vassilvitskii, D. Yin. Online Learning for Non-Stationary A/B Tests. CIKM 2018 (Torino, Italy)
T. Lykouris, S. Vassilvitskii. Competitive Caching with Machine Learned Advice. ICML 2018 (Stockholm).
A. Medina Munoz, S. Vassilvitskii. Revenue Optimization with Approximate Bid Predictions. NIPS 2017 (Los Angeles, CA).
E. Balkanski, U. Syed, S. Vassilvitskii. Statistical Cost Sharing.. NIPS 2017 (Los Angeles, CA).
F. Chierichetti, R. Kumar, S. Lattanzi., S. Vassilvitskii. Fair Clustering Through Fairlets. NIPS 2017 (Los Angeles, CA).
S. Lattanzi, S. Vassilvitskii. Consistent k-Clustering. ICML 2017 (Sydney, Australia)
S. Gupta, R. Kumar, K. Lu, B. Moseley, S. Vassilvitskii. Local Search Methods for k-Means with Outliers. VLDB 2017 (Munich, Germany).
A. Abdullah, A. McGregor, R. Kumar, S. Vassilvitskii, S. Venkatasubramanian. Sketching, Embedding, and Dimensionality Reduction in Information Spaces. AISTATS 2016 (Cadiz, Spain).
R. Kumar, D. Lokshtanov, S. Vassilvitskii, A. Vattani. Near-Optimal Bounds for Cross-Validation via Loss Stability. ICML 2013 (Atlanta, Georgia)
B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii. Scalable k-Means++. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
R. Gupta, R. Kumar, S. Vassilvitskii. On Mixtures of Markov Chains. NIPS 2016 (Barcelona, Spain).
S. Kale, R. Kumar, S. Vassilvitskii. Cross-Validation and Mean-Square Stability. In ICS 2011 (Beijing, China) [ pdf ] [ slides ]
S. Vassilvitskii, S. Venkatasubramanian. New Developments in the Theory of Clustering. Tutorial presented at KDD 2010 (Washington DC) [ slides ]
F. Chierichetti, R. Kumar, S. Pandey, S. Vassilvitskii. Finding the Jaccard Median In SODA 2010 (Austin, Texas) [ pdf ]
D. Arthur, S. Vassilvitskii. k-means++: The Advantages of Careful Seeding. In SODA 2007 (New Orleans) [ pdf ] [ slides ]
D. Arthur, S. 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 ]
D. Arthur, S. 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 ]

Computational Advertising

S. Lahaie, A. Medina Munoz, B. Sivan, S. Vassilvitskii. Testing Incentive Compatibility in Display Ad Auctions. WWW 2018 (Lyon).
A. Medina Munoz, S. Vassilvitskii. Revenue Optimization with Approximate Bid Predictions. NIPS 2017 (Los Angeles, CA).
E. Balkanski, U. Syed, S. Vassilvitskii. Statistical Cost Sharing. NIPS 2017 (Los Angeles, CA).
P. Hummel, R. P. McAfee, S. Vassilvitskii. Incentivizing Advertiser Networks to Submit Multiple Bids. International Journal of Game Theory.
H. Heidari, M. Mahdian, U. Syed, S. Vassilvitskii, S. Yazdanbod. Pricing a Low-regret Seller. ICML 2016 (New York, NY).
R. Paes Leme, M. Pal, S. Vassilvitskii. A Field Guide to Personalized Reserve Prices. WWW 2016 (Montreal, Canada).
R. Cavallo, P. McAfee, S. Vassilvitskii. Display Advertising Auctions with Arbitrage. ACM Transactions on Economics and Computation.
M. Mahdian, O. Schrijvers, S. Vassilvitskii. Algorithmic Cartography: Placing Points of Interest and Ads on Maps. KDD 2015 (Sydney, Australia).
K. Bhawalkar, P. Hummel, S. Vassilvitskii. Value of Targeting. SAGT 2014 (Patras, Greece).
S. Ieong, M., Mahdian. Advertising in a Stream. In WWW 2014 (Seoul, Korea).
P. McAfee, S. Vassilvitskii. An Overview of Practical Exchange Design. Current Science, Special Issue on Game Theory. Volum 103, Issue 9.
H. Fu, P. Jordan, M. Mahdian, U. Nadav, I. Talgam-Cohen, S. Vassilvitskii. Ad Auctions with Data. In SAGT 2012 (Barcelona, Spain)
A. Ghosh, M. Mahdian, P. McAfee, S. Vassilvitskii. To Match or not to Match: Economics of Cookie Matchignn Online Advertising. EC 2012 (Valencia, Spain)
P. Chen, W. Ma, Srinath Mandalapu, C. Nagarajan, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, M. Yu. Ad Serving using a Compact Allocation Plan. EC 2012 (Valencia, Spain)
J. Yang, E. Vee, S. Vassilvitskii, J. Tomlin, J. Shanmugasundaram, T. Anastasakos, O. Kennedy. Inventory ALlocation for Online Graphical Display Advertising using Multi-objective Optimization. ICORES 2012.
V. Bharadwaj, P. Chen, W. Ma, C. Nagarajan, J. Tomlin, S. Vassilvitskii, E. Vee, J. Yang. SHALE: an Efficient Algorithm for Allocation of Guaranteed Display Advertising. KDD 2012 (Beijing, China)
K. Lang, B. Moseley, S. Vassilvitskii. Handling Forecast Errors while Bidding for Display Advertising. In WWW 2012 (Lyon, France)
P. Jordan, M. Mahdian, S. Vassilvitskii, E. Vee. The Multiple Attribution Problem in Pay-Per-Conversion Advertising. In SAGT 2011 (Salerno, Italy) [ pdf ]
R. Kumar, S. Lattanzi, S. Vassilvitskii, A. Vattani. Hiring a Secretary from a Poset. In EC 2011 (San Jose, CA) [ pdf ]
E. Vee, S. Vassilvitskii, J. Shanmugasundaram. Optimal Online Assignment with Forecasts. In EC 2010 (Boston, Massachusetts) [ pdf ] [ Tech Report ]
S. Goel, S. Lahaie, S. Vassilvitskii. Contract Auctions for Sponsored Search. In WINE 2009 (Rome, Italy) [ pdf ] [ Short Version ]
A. Ghosh, P. McAfee, K. Papineni, S. Vassilvitskii. Bidding for Representative Allocations for Display Advertising. In WINE 2009 (Rome, Italy) [ Full Version ]
E. Arcaute, S. Vassilvitskii. Social Networks and Stable Matchings in the Job Market. In WINE 2009 (Rome, Italy) [ pdf ]
A. Ghosh, B. Rubinstein, S. Vassilvitskii, M. Zinkevich. Adaptive Bidding for Display Advertising. In WWW 2009 (Madrid, Spain) [ pdf ]
R. Gonen, S. Vassilvitskii. Sponsored Search Auctions With Reserve Prices: Going Beyond Separability. In WINE 2008 (Shanghai, China) [ pdf ]
N. Chen, A. Ghosh, S. Vassilvitskii. Optimal Envy-Free Pricing with Metric Substitutability. In EC 2008 (Chicago). Full version in SIAM Journal on Computing. [ Conference Version ]
A. Broder, A. Kirsch, R. Kumar, M. Mitzenmacher, E. Upfal, S. 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 ]
E. Arcaute, A. Kirsch, R. Kumar, D. Liben-Nowell, S. Vassilvitskii. On Threshold Behavior in Query Incentive Networks. In EC 2007 (San Diego) [ pdf ] [ slides ]

MapReduce and Data Analysis

S. Im, R. Kumar, S. Lattanzi, B. Moseley, S. Vassilvitskii. Massively Parallel Computation: Algorithms and Applications. Foundations and Trends in Optimization.
B. Moseley, S. Vassilvitskii, Y. Wang. Hierarchical Clustering in General Metric Spaces using Approximate Nearest Neighbors. AISTATS 2021 (Virtual)
A. Muñoz Medina, U. Syed, S. Vassilvitskii, E. Vitercik. Private optimization without constraint violations. AISTATS 2021 (Virtual)
M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Sliding Window Algorithms for k-Clustering Problems. NeurIPS 2020 (Virtual)
S. Ahmadian, A. Epasto, M. Knittel, R. Kumar, M. Mahdian, B. Moseley, P. Pham, S. Vassilvitskii, Y. Wang. Fair Hierarchical Clustering.. NeurIPS 2020 (Virtual)
A. Bhaskara, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Residual Based Sampling for Online Low Rank Approximation. FOCS 2019 (Baltimore)
M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Better Sliding Window Algorithms to Maximize Subwadditive and Diversity Objectives. PODS 2019 (Amsterdam, Netherlands).
F. Chierichetti, R. Kumar, S. Lattanzi, S. Vassilvitskii. Matroids, Matchings, and Fairness. AISTATS 2019 (Okinawa, Japan).
M. R. Karimi, A. Krause, S. Lattanzi, S. Vassilvitskii. Consistent Online Optimization: Convex and Submodular. AISTATS 2019 (Okinawa, Japan).
F. Chierichetti, R. Kumar, S. Lattanzi., S. Vassilvitskii. Fair Clustering Through Fairlets. NIPS 2017 (Los Angeles, CA).
U. Syed, S. Vassilvitskii. SQML: Large-scale in-database machine learning with pure SQL. SOCC 2017 (Santa Clara, CA).
S. Lattanzi, S. Vassilvitskii. Consistent k-Clustering. ICML 2017 (Sydney, Australia)
A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Submodular Optimization over Sliding Windows. WWW 2017 (Perth, Australia).
A. Archer, S. Lattanzi, P. Likarish, S. Vassilvitskii. Indexing Private-Public Graphs. WWW 2017 (Perth, Australia).
S. Gupta, R. Kumar, K. Lu, B. Moseley, S. Vassilvitskii. Local Search Methods for k-Means with Outliers. VLDB 2017 (Munich, Germany).
R. Gupta, R. Kumar, S. Vassilvitskii. On Mixtures of Markov Chains. NIPS 2016 (Barcelona, Spain).
A. Abdullah, A. McGregor, R. Kumar, S. Vassilvitskii, S. Venkatasubramanian. Sketching, Embedding, and Dimensionality Reduction in Information Spaces. AISTATS 2016 (Cadiz, Spain).
R. Kumar, Mohammd Mahdian, Bo Pang, A. Tomkins, S. Vassilvitskii. Driven By Food: Modeling Geographic Choice. WSDM 2015 (Shanghai, China) [ pdf ]
R. Kumar, A. Tomkins, S. Vassilvitskii, E. Vee. Inverting a Steady-State. WSDM 2015 (Shanghai, China). [ pdf ]
R. Kiveris, S. Lattanzi, V. Mirrokni, V. Rastogi, S. Vassilvitskii. Connected Components in MapReduce and Beyond. SOCC 2014 (Seattle, Washington).
S. Ravi, S. Vassilvitskii, V. Rastogi. Parallel Algorithms for Unsupervised Tagging. Presented at ACL 2014 (Baltimore, MD). Paper in TACL
A. Anderson, R. Kumar, A. Tomkins, S. Vassilvitskii. Dynamics of Repeat Consumption. In WWW 2014 (Seoul, Korea).
A. Broder, L. Garcia-Pueyo, V. Josifovski, S. Vassilvitskii, S. Venkatesan. Scalable k-means. In WSDM 2014 (New York)
R. Kumar, B. Moseley, S. Vassilvitskii, A. Vattani. Fast Greedy Algorithms in MapReduce and Streaming. In SPAA 2013 (Montreal, Canada).
R. Kumar, D. Lokshtanov, S. Vassilvitskii, A. Vattani. Near-Optimal Bounds for Cross-Validation via Loss Stability. ICML 2013 (Atlanta, Georgia)
B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii. Scalable k-Means++. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
B. Bahmani, R. Kumar, S. Vassilvitskii. Densest Subgraph in Streaming and MapReduce. In VLDB 2012 (Istanbul, Turkey)
S. Lattanzi, B. Moseley, S. Suri., S. Vassilvitskii. Filtering: A Method for Solving Graph Problems in MapReduce. In SPAA 2011 (San Jose, CA) [ pdf ]
S. Suri., S. Vassilvitskii. Counting Triangles and the Curse of the Last Reducer. In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
S. Kale, R. Kumar, S. Vassilvitskii. Cross-Validation and Mean-Square Stability. In ICS 2011 (Beijing, China) [ pdf ] [ slides ]
S. Vassilvitskii, S. Venkatasubramanian. New Developments in the Theory of Clustering. Tutorial presented at KDD 2010 (Washington DC) [ slides ]
R. Kumar, S. Vassilvitskii. Generalized Distances between Rankings. In WWW 2010 (Ralegh, North Carolina) [ pdf ] [ slides ]
H. Karloff, S. Suri, S. Vassilvitskii. A Model of Computation for MapReduce. In SODA 2010 (Austin, Texas) [ pdf]
F. Chierichetti, R. Kumar, S. Pandey, S. Vassilvitskii. Finding the Jaccard Median In SODA 2010 (Austin, Texas) [ pdf ]
F. Chierichetti, R. Kumar, S. Vassilvitskii. Similarity Caching. In PODS 2009 (Providence, Rhode Island) [ pdf ]
D. Arthur, S. Vassilvitskii. k-means++: The Advantages of Careful Seeding. In SODA 2007 (New Orleans) [ pdf ] [ slides ]
D. Arthur, S. 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 ]
D. Arthur, S. 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 ]
R. Motwani, S. Vassilvitskii. Distinct Value Estimators in Power Law Distributions. In ANALCO 2006 (Miami) [ pdf ] [ slides ]

Indexing

Q. Duong, S. Goel, J. Hofman, S. Vassilvitskii. Sharding Social Networks. In WSDM 2013 (Rome, Italy)
M. Fontoura, M. Gurevich, V. Josifovski. Efficiently encoding term co-occurences in inverted indexes. In CIKM 2011 (Glasgow, UK)
G. Beskales, M. Fontoura, M. Gurevich, S. Vassilvitskii, V. Josifovski. Factorization-based lossless compression of inverted indices. In CIKM 2011 (Glasgow, UK)
A. Broder, S. Das, M. Fontoura, B. Ghosh, V. Josifovski, J. Shanmugasundaram and S. Vassilvitskii. Efficiently Evaluating Graph Constraints in Content-Based Publish/Subscribe . In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
M. Fontoura, S. Sadanandan, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, S. Venkatesan, Jason Zien. Efficiently Evaluating Complex Boolean Expressions. In SIGMOD 2010 (Indianapolis, Indiana) [ pdf]
S. Whang, C. Brower, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, Ramana Yerneni, Hector Garcia-Molina. Indexing Boolean Expressions. In VLDB 2009 (Lyon, France) [ pdf]
F. Chierichetti, R. Kumar, S. Vassilvitskii. Similarity Caching. In PODS 2009 (Providence, Rhode Island) [ pdf ]
S. Pandey, A. Broder, F. Chierichetti, V. Josifovski, R. Kumar, S. Vassilvitskii. Nearest-Neighbor Caching for Content-Match Applications. In WWW 2009 (Madrid, Spain) [ pdf ]
R. Kumar, K. Punera, T. Suel, S. Vassilvitskii. Top-k Aggregation Using Intersections of Ranked Inputs. In WSDM 2009 (Barcelona, Spain) [ pdf ] [ slides ]
M. Fontoura, V. Josifovski R. Kumar, C. Olston, A. Tomkins, S. Vassilvitskii. Relaxation in Text Search Using Taxonomies. In VLDB 2008 (Auckland, New Zealand) [ pdf ]

Chronological List of Publications

2024

T. Lavastida, M. Dinitz, S. Im, B. Moseley. Controlling Tail Risk in Online Ski-Rental SODA 2024 (Alexandria, Virginia)

2023

S. Im, R. Kumar, S. Lattanzi, B. Moseley, S. Vassilvitskii. Massively Parallel Computation: Algorithms and Applications. Foundations and Trends in Optimization.
N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, A. Thakurta How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy. Tutorials at: ICML 2023, KDD 2023
R. Busa-Fekete, A. Munoz Medina, U. Syed, S. Vassilvitskii Label differential privacy and private training data release. ICML 2023 (Honolulu, Hawaii)
S. Davies, B. Moseley, S. Vassilvitskii, Y. Wang Predictive Flows for Faster Ford-Fulkerson. ICML 2023 (Honolulu, Hawaii)
S. Lattanzi, O. Svensson, S. Vassilvitskii Speeding Up Bellman Ford via Minimum Violation Permutations. ICML 2023 (Honolulu, Hawaii)
M. Khodak, K. Amin, T. Dick, S. Vassilvitskii Learning-augmented private algorithms for multiple quantile release. ICML 2023 (Honolulu, Hawaii)
K. Amin, M. Joseph, M. Ribiero, S. Vassilvitskii. Easy Differentially Private Linear Regression. ICLR 2023 (Kingali, Rwanda)
A. Epasto, J. Mao, A. Munoz Medina, V. Mirrokni, S. Vassilvitskii, P. Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estimators ITCS 2023.

2022

M. Khodak, N. Balcan, A. Talwalkar, S. Vassilvitskii. Learning Predictions for Algorithms with Predictions NeurIPS 2022.
M. Dinitz, S. Im, T. Lavastida, B. Moseley, S. Vassilvitskii. Algorithms with Prediction Portfolios NeurIPS 2022.
V. Cohen-Addad, A. Epasto, S. Lattanzi, V. Mirrokni, A. Munoz Medina, D. Saulpic, C. Schwiegelshohn, S. Vassilvitskii. Scalable Differentially Private Clustering via Hierarchically Separated Trees. KDD 2022
M. Mitzenmacher, S. Vassilvitskii. Algoirthms with Predictions Communications of the ACM, 2022.
N. Ponomareva, J. Bastings, S. Vassilvitskii. Training Text-to-Text Transformers with Privacy Guarantees ACL 2022.
H. Esfandiari, V. Mirrokni, U. Syed, S. Vassilvitskii. Label differential privacy via clustering AISTATS 2022 (Virtual)

2021

M. Dinitz, S. Im, T. Lavastida, B. Moseley, S. Vassilvitskii. Faster Matchings via Learned Duals NeurIPS 2021 (Virtual)
S. Lattanzi, B. Moseley, S. Vassilvitskii, Y. Wang, R. Zhou. Robust Online Correlation Clustering NeurIPS 2021 (Virtual)
B. Moseley, S. Vassilvitskii, Y. Wang. Hierarchical Clustering in General Metric Spaces using Approximate Nearest Neighbors. AISTATS 2021 (Virtual)
A. Muñoz Medina, U. Syed, S. Vassilvitskii, E. Vitercik. Private optimization without constraint violations. AISTATS 2021 (Virtual)
P. Dütting, S. Lattanzi, R. Paes Leme, S. Vassilvitskii. Secretaries with Advice. EC 2021 (Virtual)

2020

M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Sliding Window Algorithms for k-Clustering Problems. NeurIPS 2020 (Virtual)
S. Ahmadian, A. Epasto, M. Knittel, R. Kumar, M. Mahdian, B. Moseley, P. Pham, S. Vassilvitskii, Y. Wang. Fair Hierarchical Clustering.. NeurIPS 2020 (Virtual)
T. Lavastida, B. Moseley, S. Lattanzi, S. Vassilvitskii. Online Scheduling via Learned Weights SODA 2020 (Salt Lake City)

2019

A. Bhaskara, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Residual Based Sampling for Online Low Rank Approximation. FOCS 2019 (Baltimore)
K. Amin, T. Dick, A. Kulesza, A. Munoz Medina, S. Vassilvitskii. Differentially Private Covariance Estimation. NeurIPS 2019 (Vancouver)
K. Amin, A. Kulesza, A. Munoz Medina, S. Vassilvitskii. Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy. ICML 2019 (Long Beach)
J. Gillenwater, A. Kulesza, Z. Mariet, S. Vassilvitskii. A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes.. ICML 2019 (Long Beach)
F. Chierichetti, R. Kumar, S. Lattanzi, S. Vassilvitskii. Matroids, Matchings, and Fairness. AISTATS 2019 (Okinawa, Japan).
M. R. Karimi, A. Krause, S. Lattanzi, S. Vassilvitskii. Consistent Online Optimization: Convex and Submodular. AISTATS 2019 (Okinawa, Japan).
M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Better Sliding Window Algorithms to Maximize Subwadditive and Diversity Objectives. PODS 2019 (Amsterdam, Netherlands).

2018

J. Gillenwater, A. Kulesza, Z. Mariet, S. Vassilvitskii. Maximizing Induced Cardinality Under a Determinantal Point Process. NeurIPS 2018 (Montreal, CA).
A. Medina Munoz, S. Vassilvitskii, D. Yin. Online Learning for Non-Stationary A/B Tests. CIKM 2018 (Torino, Italy)
T. Lykouris, S. Vassilvitskii. Competitive Caching with Machine Learned Advice. ICML 2018 (Stockholm).
S. Lahaie, A. Medina Munoz, B. Sivan, S. Vassilvitskii. Testing Incentive Compatibility in Display Ad Auctions. WWW 2018 (Lyon).

2017

A. Medina Munoz, S. Vassilvitskii. Revenue Optimization with Approximate Bid Predictions. NIPS 2017 (Los Angeles, CA).
E. Balkanski, U. Syed, S. Vassilvitskii. Statistical Cost Sharing. NIPS 2017 (Los Angeles, CA).
F. Chierichetti, R. Kumar, S. Lattanzi., S. Vassilvitskii. Fair Clustering Through Fairlets. NIPS 2017 (Los Angeles, CA).
U. Syed, S. Vassilvitskii. SQML: Large-scale in-database machine learning with pure SQL. SOCC 2017 (Santa Clara, CA).
S. Lattanzi, S. Vassilvitskii. Consistent k-Clustering. ICML 2017 (Sydney, Australia)
A. Epasto, S. Lattanzi, S. Vassilvitskii, M. Zadimoghaddam. Submodular Optimization over Sliding Windows. WWW 2017 (Perth, Australia).
A. Archer, S. Lattanzi, P. Likarish, S. Vassilvitskii. Indexing Private-Public Graphs. WWW 2017 (Perth, Australia).
S. Gupta, R. Kumar, K. Lu, B. Moseley, S. Vassilvitskii. Local Search Methods for k-Means with Outliers. VLDB 2017 (Munich, Germany).

2016

R. Gupta, R. Kumar, S. Vassilvitskii. On Mixtures of Markov Chains. NIPS 2016 (Barcelona, Spain).
Best Paper Award. T. Roughgarden, S. Vassilvitskii, J. Wang. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). SPAA 2016 (Asilomar, CA).
P. Hummel, R. P. McAfee, S. Vassilvitskii. Incentivizing Advertiser Networks to Submit Multiple Bids. International Journal of Game Theory.
H. Heidari, M. Mahdian, U. Syed, S. Vassilvitskii, S. Yazdanbod. Pricing a Low-regret Seller. ICML 2016 (New York, NY).
R. Paes Leme, M. Pal, S. Vassilvitskii. A Field Guide to Personalized Reserve Prices. WWW 2016 (Montreal, Canada).
A. Abdullah, A. McGregor, R. Kumar, S. Vassilvitskii, S. Venkatasubramanian. Sketching, Embedding, and Dimensionality Reduction in Information Spaces. AISTATS 2016 (Cadiz, Spain).

2015

R. Cavallo, P. McAfee, S. Vassilvitskii. Display Advertising Auctions with Arbitrage. ACM Transactions on Economics and Computation.
M. Mahdian, O. Schrijvers, S. Vassilvitskii. Algorithmic Cartography: Placing Points of Interest and Ads on Maps. In KDD 2015 (Sydney, Australia).
R. Kumar, M. Mahdian, B. Pang, A. Tomkins, S. Vassilvitskii. Driven By Food: Modeling Geographic Choice. To Appear at WSDM 2015 (Shanghai, China) [ pdf ]
Best Paper Award. R. Kumar, A. Tomkins, S. Vassilvitskii, E. Vee. Inverting a Steady-State. To Appear at WSDM 2015 (Shanghai, China). [ pdf ]

2014

R. Kiveris, S. Lattanzi, V. Mirrokni, V. Rastogi, S. Vassilvitskii. Connected Components in MapReduce and Beyond. To Appear at SOCC 2014 (Seattle, Washington).
K. Bhawalkar, P. Hummel, S. Vassilvitskii. Value of Targeting. To Appear at SAGT 2014 (Patras, Greece) .
S. Ravi, S. Vassilvitskii, V. Rastogi. Parallel Algorithms for Unsupervised Tagging. Presented at ACL 2014 (Baltimore, MD). Paper in TACL
A. Anderson, R. Kumar, A. Tomkins, S. Vassilvitskii. Dynamics of Repeat Consumption. In WWW 2014 (Seoul, Korea).
S. Ieong, M., Mahdian. Advertising in a Stream. In WWW 2014 (Seoul, Korea).
A. Broder, L. Garcia-Pueyo, V. Josifovski, S. Vassilvitskii, S. Venkatesan. Scalable k-means. In WSDM 2014 (New York)

2013

Best Paper Award. R. Kumar, B. Moseley, S. Vassilvitskii, A. Vattani. Fast Greedy Algorithms in MapReduce and Streaming. In SPAA 2013 (Montreal, Canada).
R. Kumar, D. Lokshtanov, S. Vassilvitskii, A. Vattani. Near-Optimal Bounds for Cross-Validation via Loss Stability. ICML 2013 (Atlanta, Georgia)
Q. Duong, S. Goel, J. Hofman, S. Vassilvitskii. Sharding Social Networks. WSDM 2013 (Rome, Italy)
R. Kumar, Ronny Lempel, Roy Schwartz. Rank Quantization. WSDM 2013 (Rome, Italy)

2012

P. McAfee, S. Vassilvitskii. An Overview of Practical Exchange Design. Current Science, Special Issue on Game Theory. Volum 103, Issue 9.
H. Fu, P. Jordan, M. Mahdian, U. Nadav, I. Talgam-Cohen, S. Vassilvitskii. Ad Auctions with Data. In SAGT 2012 (Barcelona, Spain)
A. Ghosh, M. Mahdian, P. McAfee, S. Vassilvitskii. To Match or not to Match: Economics of Cookie Matchignn Online Advertising. EC 2012 (Valencia, Spain)
J. Yang, E. Vee, S. Vassilvitskii, J. Tomlin, J. Shanmugasundaram, T. Anastasakos, O. Kennedy. Inventory ALlocation for Online Graphical Display Advertising using Multi-objective Optimization. ICORES 2012.
P. Chen, W. Ma, Srinath Mandalapu, C. Nagarajan, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, M. Yu. Ad Serving using a Compact Allocation Plan. EC 2013 (Valencia, Spain)
V. Bharadwaj, P. Chen, W. Ma, C. Nagarajan, J. Tomlin, S. Vassilvitskii, E. Vee, J. Yang. SHALE: an Efficient Algorithm for Allocation of Guaranteed Display Advertising. KDD 2012 (Beijing, China)
K. Lang, B. Moseley, S. Vassilvitskii. Handling Forecast Errors while Bidding for Display Advertising. In WWW 2012 (Lyon, France)
B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii. Scalable k-Means++. In VLDB 2012 (Istanbul, Turkey) [ pdf ]
B. Bahmani, R. Kumar, S. Vassilvitskii. Densest Subgraph in Streaming and MapReduce. In VLDB 2012 (Istanbul, Turkey)

2011

M. Fontoura, M. Gurevich, V. Josifovski. Efficiently encoding term co-occurences in inverted indexes. In CIKM 2011 (Glasgow, UK)
G. Beskales, M. Fontoura, M. Gurevich, S. Vassilvitskii, V. Josifovski. Factorization-based lossless compression of inverted indices. In CIKM 2011 (Glasgow, UK)
P. Jordan, M. Mahdian, S. Vassilvitskii, E. Vee. The Multiple Attribution Problem in Pay-Per-Conversion Advertising. In SAGT 2011 (Salerno, Italy) [ pdf ]
R. Kumar, S. Lattanzi, S. Vassilvitskii, A. Vattani. Hiring a Secretary from a Poset. In EC 2011 (San Jose, CA) [ pdf]
S. Lattanzi, B. Moseley, S. Suri., S. Vassilvitskii. Filtering: A Method for Solving Graph Problems in MapReduce. In SPAA 2011 (San Jose, CA) [ pdf]
S. Suri., S. Vassilvitskii. Counting Triangles and the Curse of the Last Reducer. In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
A. Broder, S. Das, M. Fontoura, B. Ghosh, V. Josifovski, J. Shanmugasundaram and S. Vassilvitskii. Efficiently Evaluating Graph Constraints in Content-Based Publish/Subscribe . In WWW 2011 (Hyderabad, India) [ pdf ] [ slides ]
S. Kale, R. Kumar, S. Vassilvitskii. Cross-Validation and Mean-Square Stability. In ICS 2011 (Beijing, China) [ pdf ] [ slides ]

2010

S. Vassilvitskii, S. Venkatasubramanian. New Developments in the Theory of Clustering. Tutorial presented at KDD 2010 (Washington DC) [ slides ]
M. Fontoura, S. Sadanandan, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, S. Venkatesan, Jason Zien. Efficiently Evaluating Complex Boolean Expressions. In SIGMOD 2010 (Indianapolis, Indiana) [ pdf]
E. Vee, S. Vassilvitskii, J. Shanmugasundaram. Optimal Online Assignment with Forecasts. In EC 2010 (Boston, Massachusetts) [ pdf] [ Tech Report ]
R. Kumar, S. Vassilvitskii. Generalized Distances between Rankings. In WWW 2010 (Ralegh, North Carolina) [ pdf ] [ slides ]
H. Karloff, S. Suriri, S. Vassilvitskii. A Model of Computation for MapReduce. In SODA 2010 (Austin, Texas) [ pdf ]
F. Chierichetti, R. Kumar, S. Pandey, S. Vassilvitskii. Finding the Jaccard Median In SODA 2010 (Austin, Texas) [ pdf ]

2009

S. Goel, S. Lahaie, S. Vassilvitskii. Contract Auctions for Sponsored Search. In WINE 2009 (Rome, Italy) [ pdf] [ Short Version ]
A. Ghosh, P. McAfee, K. Papineni, S. Vassilvitskii. Bidding for Representative Allocations for Display Advertising. In WINE 2009 (Rome, Italy) [ Full Version ]
E. Arcaute, S. Vassilvitskii. Social Networks and Stable Matchings in the Job Market. In WINE 2009 (Rome, Italy) [ pdf ]
Z. Abbassi, S. Amer-Yahia, L. Lakshmanan, S. Vassilvitskii, C. Yu. Getting Recommender Systems to Think Outside the Box. In RecSys 2009 (New York) [ pdf ]
S. Whang, C. Brower, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, Ramana Yerneni, Hector Garcia-Molina. Indexing Boolean Expressions. In VLDB 2009 (Lyon, France) [ pdf]
F. Chierichetti, R. Kumar, S. Vassilvitskii. Similarity Caching. In PODS 2009 (Providence, Rhode Island) [ pdf ]
S. Pandey, A. Broder, F. Chierichetti, V. Josifovski, R. Kumar, S. Vassilvitskii. Nearest-Neighbor Caching for Content-Match Applications. In WWW 2009 (Madrid, Spain) [ pdf ]
A. Ghosh, B. Rubinstein, S. Vassilvitskii, M. Zinkevich. Adaptive Bidding for Display Advertising. In WWW 2009 (Madrid, Spain) [ pdf ]
R. Kumar, K. Punera, T. Suel, S. Vassilvitskii. Top-k Aggregation Using Intersections of Ranked Inputs. In WSDM 2009 (Barcelona, Spain) [ pdf ] [ slides ]

2008

R. Gonen, S. Vassilvitskii. Sponsored Search Auctions With Reserve Prices: Going Beyond Separability. In WINE 2008 (Shanghai, China) [ pdf ]
M. Fontoura, V. Josifovski R. Kumar, C. Olston, A. Tomkins, S. Vassilvitskii. Relaxation in Text Search Using Taxonomies. In VLDB 2008 (Auckland, New Zealand) [ pdf ]
N. Chen, A. Ghosh, S. Vassilvitskii. Optimal Envy-Free Pricing with Metric Substitutability. In EC 2008 (Chicago). Full version in SIAM Journal on Computing. [ Full Version ] [ Conference Version ]
A. Broder, A. Kirsch, R. Kumar, M. Mitzenmacher, E. Upfal, S. 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

E. Arcaute, A. Kirsch, R. Kumar, D. Liben-Nowell, S. Vassilvitskii. On Threshold Behavior in Query Incentive Networks. In EC 2007 (San Diego) [ pdf ] [ slides ]
D. Arthur, S. Vassilvitskii. k-means++: The Advantages of Careful Seeding. In SODA 2007 (New Orleans) [ pdf ] [ slides ]

2006

D. Arthur, S. 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 ]
S. Vassilvitskii, E. Brill. Using Web Graph Distance For Relevance Feedback in Web Search. In SIGIR 2006 (Seattle) [ pdf ] [ slides ]
D. Arthur, S. 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 ]
R. Motwani, S. Vassilvitskii. Distinct Value Estimators in Power Law Distributions. In ANALCO 2006 (Miami) [ pdf ] [ slides ]

2004

S. Vassilvitskii, M. 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

S. Vassilvitskii, M. Yim, J. W. Suh. A Complete, Local and Parallel Reconfiguration Algorithm for Cube Style Modular Robots. In ICRA 2002 (Washington DC). [ pdf ]
S. Vassilvitskii, J. Kubica, E. G. Rieffel, J. W. Suh, M. Yim. On the General Reconfiguration Problem for Expanding Cube Style Modular Robots. In ICRA 2002 (Washington DC) [ pdf ]