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.

Research Publications

  • Sample-efficient proper PAC learning with approximate differential privacy

    • Badih Ghazi, Noah Golowich, Ravi Kumar and Pasin Manurangsi

    • [arXiv]

  • Robust and Private Learning of Halfspaces

    • Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Thao Nguyen

    • [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 (to appear).

    • [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 (to appear).

    • 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 (to appear).

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

    • [PDF]

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