Badih Ghazi


Google, Mountain View, CA

badihghazi@gmail.com

I am a Research Scientist in the Algorithms & Optimization Team at Google.

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

  • On the Power of Multiple Anonymous Messages
    • Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker
    • Abstract presented at Symposium on the Foundations of Responsible Computing (FORC) 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.
  • 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]