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 machine learning, differential privacy, error-correcting codes and communication under uncertainty.

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, FSTTCS 2022, NeurIPS 2022 (area chair), and PETS 2023.

Research Publications

  • Differentially Private Ad Conversion Measurement

    • John Delaney, Badih Ghazi, Charlie Harrison, Christina Ilvento, Ravi Kumar, Pasin Manurangsi, Martin Pal, Karthik Prabhakar, Mariana Raykova

    • Abstract to be presented at Symposium on the Foundations of Responsible Computing (FORC) 2022

  • 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

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

    • 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

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

    • [arXiv]

  • User-Level Differentially Private Learning via Correlated Sampling

    • Badih Ghazi, Ravi Kumar, Pasin Manurangsi

    • Conference on Neural Information Processing Systems (NeurIPS) 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]