About me

I am a postdoctoral fellow at the Simons Institute, Berkeley hosted by Prof. Umesh Vazirani. I completed my PhD in Computer Science at Columbia University advised by Prof. Henry Yuen.

My research focuses on quantum computing and complexity, with an emphasis on understanding polynomial optimization and constraint satisfaction problems in the noncommutative setting.

You can download my CV here. A short talk on the theme of my research can be found here. Here is a long talk on noncommutative rounding schemes. And here is my QIP 2022 plenary talk. You can find a Q&A with me here.

Recent Talks

• January 9: Theory Seminar, NYU
• January 7: ITCS 2025, Columbia University
• December 5: Quantum Pod Seminar, Simons Institute
• December 3: IQUIST Seminar, University of Illinois Urbana-Champaign slides video
• December 2: Quantum Working Group Seminar, University of Illinois Urbana-Champaign
• November 22: Theory Lunch, University of Washington slides
• November 14: Quantum Computing Seminar, Harvard slides
• November 13: MIT
• October 31: Post-FOCS Mini Theory Workshop at the University of Chicago/TTIC slides
• October 29: FOCS 2024 slides
• April 23: Probabilistic Operator Algebra Seminar, UC Berkeley slides

Publications

• A quantum unique games conjecture
  H. Mousavi, T. Spirig
  Conference on Quantum Information Processing (QIP) 2025
  Innovations in Theoretical Computer Science (ITCS) 2025
  arXiv:2409.20028

• Approximation algorithms for noncommutative CSPs
  E. Culf, H. Mousavi, T. Spirig
  Conference on Quantum Information Processing (QIP) 2025
  Symposium on Foundations of Computer Science (FOCS) 2024
  arXiv:2312.16765

• Synchronous values of games
  J. Helton, H. Mousavi, S. Nezhadi, V. Paulsen, T. Russel
  Annales Henri Poincaré 2024
  Tsirelson Memorial Workshop 2022
  arXiv:2109.14741

• Nonlocal games, compression theorems, and the arithmetical hierarchy
  H. Mousavi, S. Nezhadi, H. Yuen
  Conference on Quantum Information Processing (QIP) 2022 plenary talk
  Symposium on Theory of Computing (STOC) 2022
  arXiv:2110.04651

• On the complexity of zero gap MIP*
  H. Mousavi, S. Nezhadi, H. Yuen
  International Colloquium on Automata, Languages and Programming (ICALP) 2020
  Theory of Quantum Computation, Communication and Cryptography (TQC) 2020
  arXiv:2002.10490

• A generalization of CHSH and the algebraic structure of optimal strategies
  D. Cui, A. Mehta, H. Mousavi, S. Nezhadi
  Conference on Quantum Information Processing (QIP) 2020
  Quantum Journal 2020
  arXiv:1911.01593

• Decision algorithms for Fibonacci-automatic words, III: Enumeration and abelian properties
  C. Fei Du, H. Mousavi, L. Schaeffer, J. Shallit
  International Journal of Foundations of Computer Science (27:943–963) 2016
  link

• Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability
  C. Fei Du, H. Mousavi, E. Rowland, L. Schaeffer, J. Shallit
  Theoretical Computer Science (657:146–162) 2017
  arXiv:1406.0670

• Decision algorithms for Fibonacci-automatic words, I: Basic results
  H. Mousavi, L. Schaeffer, J. Shallit
  Theoretical Informatics and Applications (50:39–66) 2016
  link

• A new approach to the paperfolding sequences
  D. Goc, H. Mousavi, L. Schaeffer, J. Shallit
  11th Conference on Computability in Europe CIE 2015
  link

• Mechanical proofs of properties of the tribonacci word
  H. Mousavi, J. Shallit
  11th International Conference WORDS 2015
  arXiv:1407.5841

• Shortest repetition-free words accepted by automata
  J. Shallit
  15th International Workshop, DCFS 2013
  arXiv:1304.2959

• On the number of unbordered factors
  D. Goc, J. Shallit
  7th International Conference LATA 2013
  arXiv:1211.1301

• Repetition avoidance in circular factors
  H. Mousavi, J. Shallit
  17th International Conference DLT 2013
  arXiv:1212.0052

• Filtrations of formal languages by arithmetic progressions
  H. Mousavi, J. Shallit
  Fundamenta Informaticae (123:135–142) 2013
  arXiv:1112.3758

Preprints and Manuscripts

• Lower bounds on the length of regular expressions, 2017, arXiv:1712.00811
• Automatic theorem proving in Walnut, 2016, arXiv:1603.06017

Automated Theorem Proving

Walnut, a software I developed in 2013, is an automated theorem prover designed to handle first-order statements in Presburger arithmetic with automata. Jeffrey Shallit maintains a list of research papers that have utilized Walnut. In 2022, Shallit authored a book “The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut,” providing an in-depth exploration of Walnut’s applications in combinatorics on words.

Some Running and Cycling Photos

Wuling Pass, Taiwan, Dolomites, Vrsic-pass, Slovenia, Julian Alps, Austrian Alps, Lake Como, Swiss Alps, Northern California, Yosemite, New York City Marathon