Princeton University

Address: 35 Olden St, Princeton, NJ 08540

Email: kmittal at cs dot princeton dot edu

Hi! I am a PhD student in the Computer Science Theory Group at Princeton University, where I am fortunate to be advised by Ran Raz. Prior to this, 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.

**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

(2019)

[PDF]

- Spring '22 - Teaching Assistant for COS 585: Information Theory and Applications
- Spring '21 - Teaching Assistant for COS 340: Reasoning about Computation
- Fall '20 - Teaching Assistant for COS 340: Reasoning about Computation

- Spring '19 - Teaching Assistant for CS 310: Automata Theory
- Fall '18 - Teaching Assistant for CS 101: Computer Programming and Utilization
- Spring '18 - Teaching Assistant for CS 207(M): Discrete Structures
- Fall '17 - Teaching Assistant for CS 213/293, Data Structures and Algorithms
- Feb-Dec '17 - Teaching Assistant for CS 213.3x, Data Structures and Algorithms