Badih Ghazi

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), and ICLR 2024 (area chair).

Research Publications

• Summary Reports Optimization in the Privacy Sandbox Attribution Reporting API

  • Hidayet Aksu, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon, Avinash Varadarajan

  • [arXiv]

• 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

  • [arXiv]

• 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.

  • [Link to PDF]

• 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

  • Abstract 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.

  • [Link to PDF]

• 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]

• 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

• Faster Privacy Accounting via Evolving Discretization

  • Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi

  • International Conference on Machine Learning (ICML) 2022.

  • [Link to PDF]

• 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.

  • [Link to PDF]

• Private Aggregation of Trajectories

  • Badih Ghazi, Neel Kamal, Ravi Kumar, Pasin Manurangsi, Annika Zhang

  • Proceedings on Privacy Enhancing Technologies (PoPETs) 2022.

  • [Link to PDF]

• 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.

  • [Link to PDF]

• 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.

  • [Link to PDF]

• 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. 

  • [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]