Kunal Mittal
New York University
Address: 251 Mercer St, New York, NY 10012
Email: kunal dot mittal at nyu dot edu
Hi! I am a postdoctoral associate in the theory group at NYU, where I am hosted by Subhash Khot. I obtained my Ph.D. in Computer Science from Princeton University, where I was extremely fortunate to be advised by Ran Raz. Prior to that, I received my undergraduate degree in Computer Science and Engineering from IIT Bombay, where I had the pleasure to work with Nutan Limaye and S Akshay.
I am interested in complexity theory, information theory, combinatorics, and analysis of boolean functions.
Research Work
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
with Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, and Dor Minzer
Manuscript (2025)
[arXiv] [ECCC]
Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
Manuscript (2025)
[arXiv] [ECCC]
Biased Linearity Testing in the 1% Regime
with Subhash Khot
Computational Complexity Conference (CCC 2025)
[arXiv] [ECCC] [CCC Talk]
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
with Pritam Chandra, Ankit Garg, Neeraj Kayal, and Tanmay Sinha
Innovations in Theoretical Computer Science (ITCS 2024)
[arXiv] [ECCC]
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
with Uma Girish, Ran Raz, and Wei Zhan
International Conference on Randomization and Computation (RANDOM 2022)
[arXiv] [ECCC]
Parallel Repetition For All 3-Player Games Over Binary Alphabet
with Uma Girish, Justin Holmgren, Ran Raz, and Wei Zhan
Symposium on Theory of Computing (STOC 2022)
[arXiv] [ECCC] [IAS CSDM Talk]
Parallel Repetition for the GHZ Game: A Simpler Proof
with Uma Girish, Justin Holmgren, Ran Raz, and Wei Zhan
International Conference on Randomization and Computation (RANDOM 2021)
[arXiv] [ECCC] [RANDOM Talk]
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
with Ran Raz
Innovations in Theoretical Computer Science (ITCS 2021)
[arXiv] [ECCC] [ITCS Talk]
Homogeneous ABP complexity of Elementary Symmetric Polynomials
with Nutan Limaye and Mukesh Pareek
Manuscript (2019)
[PDF]
Dissertation
Parallel Repetition of Multiplayer Games: New Bounds and Applications
Ph.D. Dissertation (2025)
[DataSpace]
Other Writings
A Short Proof of the Kahn-Kalai-Linial Inequality
[PDF]
Teaching Assistant
Princeton University
- Spring '22 - COS 585: Information Theory and Applications
- Spring '21 - COS 340: Reasoning about Computation
- Fall '20 - COS 340: Reasoning about Computation
- Spring '19 - CS 310: Automata Theory
- Fall '18 - CS 101: Computer Programming and Utilization
- Spring '18 - CS 207(M): Discrete Structures
- Fall '17 - CS 213/293, Data Structures and Algorithms
- Feb-Dec '17 - CS 213.3x, Data Structures and Algorithms