About Me

I am a Simons Quantum Postdoctoral Fellow, hosted by Umesh Vazirani. Previously, I completed my Ph.D. at IRIF, Université de Paris advised by Frédéric Magniez and Miklos Santha.

Research Interest

My main research interest is to understand the impact of quantum mechanics on algorithm design and computational complexity theory. I have contributed to new quantum algorithms for optimization, statistical analysis, streaming data, random sampling and graph problems. I have worked on lower bounds in query complexity with applications to cryptography. I am also interested in computational learning theory and communication complexity.

scholar cv yt


  1. Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
    Arjan Cornelissen, Yassine Hamoudi, Sofiene Jerbi
    Preprint (2021).
    [PDF] [arXiv]

  2. Classical and Quantum Dynamic Programming for Subset-Sum and Variants
    Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, Miklos Santha
    Preprint (2021).
    [PDF] [arXiv]

  3. Quantum Sub-Gaussian Mean Estimator
    Yassine Hamoudi
    Proceedings of the 29th European Symposium on Algorithms (ESA 2021).
    [PDF] [arXiv] [Conference]

  4. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
    Yassine Hamoudi, Frédéric Magniez
    Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021).
    medal Outstanding Paper Award.
    [PDF] [arXiv] [Conference]

  5. Quantum Algorithms for Hedging and the Learning of Ising Models
    Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, Miklos Santha
    Physical Review A, vol. 103, p. 012418 (2021).
    [PDF] [arXiv] [Journal]

  6. Quantum and Classical Algorithms for Approximate Submodular Function Minimization
    Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, Miklos Santha
    Quantum Information & Computation, vol. 19, pp. 1325–1349 (2019).
    [PDF] [arXiv] [Journal]

  7. Quantum Chebyshev’s Inequality and Applications
    Yassine Hamoudi, Frédéric Magniez
    Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019).
    [PDF] [arXiv] [Conference]

  8. Simultaneous Multiparty Communication Complexity of Composed Functions
    Yassine Hamoudi
    Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
    [PDF] [arXiv] [Conference]

Other Manuscripts


Teaching Assistant


I was in charge of organizing the Algorithms and Complexity seminar at IRIF from 2017 to 2021.

I have been a conference reviewer for: FOCS (x2), FSTTCS (x2), ICALP (x2), ITCS (x1), MFCS (x2), QIP (x3), SAC (x1), SODA (x3), STACS (x2).

I have been a journal reviewer for: Algorithmica, IJQI, Quantum, Transactions on Computers.

Theme's credit