Badih Ghazi


I am a Research Scientist at Google in the Algorithms Group.

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.

My research has been in theoretical computer science in general, and in error-correcting codes, computational complexity and communication under uncertainty in particular.

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.
 


 

 

Contact Information

Badih Ghazi
Google, Mountain View, CA 94043 , USA
Phone: +1 (617) 999-7010
Email: my-first-name-my-last-name at gmail.com

 

Badih

 

Publications

  • Badih Ghazi, Pritish Kamath, Prasad Raghavendra
    Dimension Reduction for Polynomials over Gaussian Space and Applications
    Computational Complexity Conference (CCC) 2018 (to appear).
    [Abstract] [PDF]

  • Badih Ghazi, TS Jayram
    Resource-Efficient Common Randomness and Secret-Key Schemes
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018.
    [Abstract] [PDF]

  • Badih Ghazi, Madhu Sudan
    The Power of Shared Randomness in Uncertain Communication
    International Colloquium on Automata, Languages and Programming (ICALP) 2017.
    [Abstract] [PDF]

  • Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan
    Compression in a Distributed Setting
    Innovations in Theoretical Computer Science (ITCS) 2017.
    [Abstract] [PDF]

  • Vitaly Feldman, Badih Ghazi
    On the Power of Learning from k-Wise Queries
    Innovations in Theoretical Computer Science (ITCS) 2017.
    [Abstract] [PDF]

  • Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
    Optimality of Correlated Sampling
    Manuscript 2016.
    [Abstract] [PDF]

  • Badih Ghazi, Pritish Kamath, Madhu Sudan
    Decidability of Non-Interactive Simulation of Joint Distributions
    IEEE Symposium on Foundations of Computer Science (FOCS) 2016.
    [Abstract] [PDF]

  • Venkata Gandikota, Badih Ghazi, Elena Grigorescu
    NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem
    IEEE Symposium on Foundations of Computer Science (FOCS) 2016.
    SIAM Journal on Computing (SICOMP) 2018 (to appear).
    [Abstract] [PDF]

  • Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan
    Communication with Contextual Uncertainty
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
    Computational Complexity (CC) 2017.
    [Abstract] [PDF]

  • Badih Ghazi, Pritish Kamath, Madhu Sudan
    Communication Complexity of Permutation-Invariant Functions
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
    [Abstract] [PDF]

  • Venkata Gandikota, Badih Ghazi, Elena Grigorescu
    On the NP-hardness of Bounded Distance Decoding of Reed-Solomon Codes
    IEEE International Symposium on Information Theory (ISIT) 2015.
    [Abstract] [PDF]

  • Badih Ghazi, Euiwoong Lee
    LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2015.
    IEEE Transactions on Information Theory 2017.
    [Abstract] [PDF]

  • Eric Blais, Joshua Brody, Badih Ghazi
    The Information Complexity of Hamming Distance
    International Workshop on Randomization and Computation (RANDOM) 2014.
    [Abstract] [PDF]

  • Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, Lixin Shi
    Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
    Allerton Conference on Communication, Control, and Computing (Allerton) 2013.
    [Abstract] [PDF]

  • Lixin Shi, Ovidiu Andronesi, Haitham Hassanieh, Badih Ghazi, Dina Katabi, and Elfar Adalsteinsson
    MRS Sparse-FFT: Reducing Acquisition Time and Artifacts for In Vivo 2D Correlation Spectroscopy
    International Society for Magnetic Resonance in Medicine Annual Meeting & Exhibition (ISMRM), 2013 .
    [PDF]

  • Louay Bazzi, Badih Ghazi, Rudiger Urbanke
    Linear Programming Decoding of Spatially Coupled Codes
    IEEE International Symposium on Information Theory (ISIT) 2013.
    IEEE Transactions on Information Theory 2014.
    [Abstract] [PDF]