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


Existence of Fair Resolute Voting Rules
with Manik Dhar and Clayton Thomas
Manuscript (2026)
[arXiv]


Improved Parallel Repetition for GHZ-Supported Games via Spreadness
with Yang P. Liu and Shachar Lovett
Manuscript (2026)
[arXiv] [ECCC]


Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
Manuscript (2025)
[arXiv] [ECCC]


An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
with Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, and Dor Minzer
Symposium on Theory of Computing (STOC 2026)
[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 IIT Bombay