About me

I am a postdoctoral fellow at the Simons Institute at 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.

Recent & Planned Talks

• December 5: Simons Quantum Pod Seminar
• December 3: IQUIST Seminar at the University of Illinois Urbana-Champaign
• November 22: Theory Seminar at the University of Washington
• October 31: Post-FOCS Mini Theory Workshop at the University of Chicago/TTIC
• October 29: 65th IEEE Symposium on Foundations of Computer Science (FOCS) 2024

Publications

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

• Approximation algorithms for noncommutative CSPs
  E. Culf, H. Mousavi, T. Spirig
  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 factorsm
  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.