Badih Ghazi
Google, Mountain View, CA
badihghazi@gmail.com
I am a Research Scientist in the Algorithms team at Google Research.
My current research interests include algorithmic aspects of differential privacy, digital advertising, and machine learning.
I completed my Ph.D. in February 2018 at the Electrical Engineering and Computer Science department at MIT where I was very fortunate to be advised by Madhu Sudan and Ronitt Rubinfeld.
From September 2015 to February 2018, I was a visiting student at the Theory of Computation Group at Harvard.
Previously, I got my M.S. in EECS also from MIT, and my B.Eng. in Computer and Communications Engineering from the American University of Beirut, where I was very lucky to work with Louay Bazzi.
During academic year 2017-2018, I was supported by an IBM Ph.D. Fellowship. During academic year 2012-2013, I was supported by an MIT Irwin and Joan Jacobs Presidential Fellowship.
I am serving on the program committees of Random 2021, NeurIPS 2021 (area chair), PETS 2022, SODA 2022, TPDP 2022, UpML 2022, FSTTCS 2022, NeurIPS 2022 (area chair), PETS 2023, FORC 2023, ICML 2023 (area chair), NeurIPS 2023 (area chair), PETS 2024, The Web Conference 2024 (senior area chair for the Responsible Web), ICLR 2024 (area chair), CCS 2024, NeurIPS 2024 (area chair), ALT 2025 (area chair), AAAI 2025 (Senior Program Committee), STOC 2025, and ICLR 2025 (area chair).
Research Publications
Differentially Private Optimization with Sparse Gradients
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Conference on Neural Information Processing Systems (NeurIPS) 2024
Scalable DP-SGD: Shuffling vs. Poisson Subsampling
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
Conference on Neural Information Processing Systems (NeurIPS) 2024
Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning
Lynn Chua, Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Daogao Liu, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
Conference on Language Modeling (COLM) 2024
[arXiv]
On Convex Optimization with Semi-Sensitive Features
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
Annual Conference on Learning Theory (COLT) 2024.
[arXiv]
Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
Conference on Information-Theoretic Cryptography (ITC) 2024.
[arXiv]
Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
International Conference on Machine Learning (ICML) 2024.
[arXiv]
How Private are DP-SGD Implementations?
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
International Conference on Machine Learning (ICML) 2024, Oral Presentation.
[arXiv]
Differentially Private Optimization with Sparse Gradients
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Presented at Symposium on the Foundations of Responsible Computing (FORC) 2024.
[arXiv]
Summary Reports Optimization in the Privacy Sandbox Attribution Reporting API
Hidayet Aksu, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon, Avinash Varadarajan
Proceedings on Privacy Enhancing Technologies (PoPETs) 2024
[arXiv]
LabelDP-Pro: Learning with Label Differential Privacy via Projections
Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
International Conference on Learning Representations (ICLR) 2024.
Training Differentially Private Ad Prediction Models with Semi-Sensitive Features
Lynn Chua, Qiliang Cui, Badih Ghazi, Charlie Harrison, Pritish Kamath, Walid Krichene, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash Varadarajan, Chiyuan Zhang
Presented at the AAAI Workshop on Privacy-Preserving Artificial Intelligence (PPAI) 2024.
[arXiv]
Differentially Private Ad Conversion Measurement
John Delaney, Badih Ghazi, Charlie Harrison, Christina Ilvento, Ravi Kumar, Pasin Manurangsi, Martin Pal, Karthik Prabhakar, Mariana Raykova
Presented at Symposium on the Foundations of Responsible Computing (FORC) 2022.
Proceedings on Privacy Enhancing Technologies (PoPETs) 2024
User-Level Differential Privacy With Few Examples Per User
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
Conference on Neural Information Processing Systems (NeurIPS) 2023, Oral Presentation.
[arXiv]
Optimal Unbiased Randomizers for Regression with Label Differential Privacy
Ashwinkumar Badanidiyuru, Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan, Chiyuan Zhang
Conference on Neural Information Processing Systems (NeurIPS) 2023.
[arXiv]
On Computing Pairwise Statistics with Local Differential Privacy
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
Conference on Neural Information Processing Systems (NeurIPS) 2023.
Sparsity-Preserving Differentially Private Training
Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
Conference on Neural Information Processing Systems (NeurIPS) 2023.
[arXiv]
On Differentially Private Sampling from Gaussian and Product Distributions
Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
Conference on Neural Information Processing Systems (NeurIPS) 2023.
[arXiv]
Optimizing Hierarchical Queries for the Attribution Reporting API
Matthew Dawson, Badih Ghazi, Pritish Kamath, Kapil Kumar, Ravi Kumar, Bo Luan, Pasin Manurangsi, Nishanth Mundru, Harikesh Nair, Adam Sealfon, Shengyu Zhu
AdKDD 2023.
[arXiv]
On User-Level Private Convex Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi, Chiyuan Zhang
International Conference on Machine Learning (ICML) 2023.
[arXiv]
Ticketed Learning--Unlearning Schemes
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, Chiyuan Zhang
Annual Conference on Learning Theory (COLT) 2023.
Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 2023.
Differentially Private Aggregation via Imperfect Shuffling
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
Conference on Information-Theoretic Cryptography (ITC) 2023.
Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 2023.
Separating Computational and Statistical Differential Privacy (Under Plausible Assumptions)
Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
IEEE Symposium on Foundations of Computer Science (FOCS) 2023
[arXiv]
On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Kewen Wu
International Colloquium on Automata, Languages and Programming (ICALP) 2023.
[arXiv]
Regression with Label Differential Privacy
Badih Ghazi, Pritish Kamath, Ethan Leeman, Pasin Manurangsi, Ravi Kumar, Avinash Varadarajan, Chiyuan Zhang
International Conference on Learning Representations (ICLR) 2023.
[arXiv]
Private Ad Modeling with DP-SGD
Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash Varadarajan, Chiyuan Zhang
Presented at the AAAI Workshop on Privacy-Preserving Artificial Intelligence (PPAI) 2023.
AdKDD 2023.
[arXiv]
Differentially Private Heatmaps
Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, Nachiappan Valliappan
Conference on Artificial Intelligence (AAAI) 2023.
[arXiv]
Algorithms with More Granular Differential Privacy Guarantees
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke
Innovations in Theoretical Computer Science (ITCS) 2023.
[arXiv]
Private Counting of Distinct and k-Occurring Items in Time Windows
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
Innovations in Theoretical Computer Science (ITCS) 2023.
[arXiv]
Differentially Private Data Release over Multiple Tables
Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
ACM Principles of Database Systems (PODS) 2023.
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023.
Large-Scale Differentially Private BERT
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, Pasin Manurangsi
Findings of Conference on Empirical Methods in Natural Language Processing (EMNLP) 2022.
[arXiv]
Anonymized Histograms in Intermediate Privacy Models
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Conference on Neural Information Processing Systems (NeurIPS) 2022.
[arXiv]
Private Isotonic Regression
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Conference on Neural Information Processing Systems (NeurIPS) 2022.
[arXiv]
Faster Privacy Accounting via Evolving Discretization
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
International Conference on Machine Learning (ICML) 2022.
Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Proceedings on Privacy Enhancing Technologies (PoPETs) 2022.
Private Aggregation of Trajectories
Badih Ghazi, Neel Kamal, Ravi Kumar, Pasin Manurangsi, Annika Zhang
Proceedings on Privacy Enhancing Technologies (PoPETs) 2022.
Distributed, Private, Sparse Histograms in the Two-Server Model
James Bell, Adria Gascon, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, Phillipp Schoppmann
ACM Conference on Computer and Communications Security (CCS) 2022.
Private Rank Aggregation in Central and Local Models
Daniel Alabi, Badih Ghazi, Ravi Kumar and Pasin Manurangsi
Conference on Artificial Intelligence (AAAI) 2022.
[arXiv]
Multiparty Reach and Frequency Histogram: Private, Secure and Practical
Badih Ghazi, Ravi Kumar, Ben Kreuter, Pasin Manurangsi, Jiayu Peng, Evgeny Skvortsov, Yao Wang, Craig Wright
Proceedings on Privacy Enhancing Technologies (PoPETs) 2022.
Deep Learning with Label Differential Privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang
Conference on Neural Information Processing Systems (NeurIPS) 2021.
Theory and Practice of Differential Privacy (TPDP) 2021.
[arXiv]
User-Level Differentially Private Learning via Correlated Sampling
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
Conference on Neural Information Processing Systems (NeurIPS) 2021.
Theory and Practice of Differential Privacy (TPDP) 2021.
[arXiv]
Locally Private k-Means in One Round
Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
International Conference on Machine Learning (ICML) 2021, Oral Presentation.
Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 2021.
[arXiv]
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha
International Conference on Machine Learning (ICML) 2021.
Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 2021.
[arXiv]
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Badih Ghazi, Ravi Kumar and Pasin Manurangsi
Annual Conference on Learning Theory (COLT) 2021.
[arXiv]
Sample-efficient proper PAC learning with approximate differential privacy
Badih Ghazi, Noah Golowich, Ravi Kumar and Pasin Manurangsi
ACM Symposium on Theory of Computing (STOC) 2021.
[arXiv]
Robust and Private Learning of Halfspaces
Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Thao Nguyen
International Conference on Artificial Intelligence and Statistics (AISTATS) 2021, Oral Presentation.
[arXiv]
Near-Tight Closure Bounds for Littlestone and Threshold Dimensions
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
International Conference on Algorithmic Learning Theory (ALT) 2021, Best Student Paper Award.
[arXiv]
On Distributed Differential Privacy and Counting Distinct Elements
Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
Innovations in Theoretical Computer Science (ITCS) 2021.
[arXiv]
On the Power of Multiple Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker
Eurocrypt 2021.
Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 2020.
[arXiv]
Differentially Private Clustering: Tight Approximation Ratios
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
Conference on Neural Information Processing Systems (NeurIPS) 2020, Oral Presentation.
Theory and Practice of Differential Privacy (TPDP) 2020.
[arXiv]
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Rasmus Pagh
International Conference on Machine Learning (ICML) 2020.
Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 2020.
[arXiv]
Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
Information-Theoretic Cryptography (ITC) 2020.
[arXiv]
Private Aggregation from Fewer Anonymous Messages
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
Eurocrypt 2020.
[arXiv]
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model
Badih Ghazi, Rasmus Pagh, Ameya Velingker
Theory and Practice of Differential Privacy (TPDP) 2019.
[arXiv]
Recursive Sketches for Modular Deep Learning
Badih Ghazi, Rina Panigrahy, Joshua R. Wang
International Conference on Machine Learning (ICML) 2019.
[arXiv]
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.
[arXiv]
Dimension Reduction for Polynomials over Gaussian Space and Applications
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
Computational Complexity Conference (CCC) 2018.
[PDF]
Resource-Efficient Common Randomness and Secret-Key Schemes
Badih Ghazi, TS Jayram
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018.
[PDF]
The Power of Shared Randomness in Uncertain Communication
Badih Ghazi, Madhu Sudan
International Colloquium on Automata, Languages and Programming (ICALP) 2017.
[PDF]
Compression in a Distributed Setting
Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan
Innovations in Theoretical Computer Science (ITCS) 2017.
[PDF]
On the Power of Learning from k-Wise Queries
Vitaly Feldman, Badih Ghazi
Innovations in Theoretical Computer Science (ITCS) 2017.
[PDF]
Optimality of Correlated Sampling
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
Theory of Computing (TOC), 2020.
[PDF]
Decidability of Non-Interactive Simulation of Joint Distributions
Badih Ghazi, Pritish Kamath, Madhu Sudan
IEEE Symposium on Foundations of Computer Science (FOCS) 2016.
[PDF]
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
IEEE Symposium on Foundations of Computer Science (FOCS) 2016.
SIAM Journal on Computing (SICOMP) 2018.
[PDF]
Communication with Contextual Uncertainty
Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
Computational Complexity (CC) 2017.
[PDF]
Communication Complexity of Permutation-Invariant Function
Badih Ghazi, Pritish Kamath, Madhu Sudan
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
[PDF]
On the NP-hardness of Bounded Distance Decoding of Reed-Solomon Codes
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
IEEE International Symposium on Information Theory (ISIT) 2015.
[PDF]
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes
Badih Ghazi, Euiwoong Lee
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2015.
IEEE Transactions on Information Theory 2017.
[PDF]
The Information Complexity of Hamming Distance
Eric Blais, Joshua Brody, Badih Ghazi
International Workshop on Randomization and Computation (RANDOM) 2014.
[PDF]
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, Lixin Shi
Allerton Conference on Communication, Control, and Computing (Allerton) 2013.
[PDF]
MRS Sparse-FFT: Reducing Acquisition Time and Artifacts for In Vivo 2D Correlation Spectroscopy
Lixin Shi, Ovidiu Andronesi, Haitham Hassanieh, Badih Ghazi, Dina Katabi, and Elfar Adalsteinsson
International Society for Magnetic Resonance in Medicine Annual Meeting & Exhibition (ISMRM), 2013 .
[PDF]
Linear Programming Decoding of Spatially Coupled Codes
Louay Bazzi, Badih Ghazi, Rudiger Urbanke
IEEE International Symposium on Information Theory (ISIT) 2013.
IEEE Transactions on Information Theory 2014.
[PDF]