Uma Girish

Postdoctoral Research Scientist
Computer Science, Columbia University
ug2150 (at) columbia (dot) edu

About Me

I am a postdoctoral research scientist at Columbia University hosted by Henry Yuen. I obtained a PhD at Princeton University, where I was extremely fortunate to be advised by Ran Raz.

Previously, I obtained an M.Sc. and B.Sc. from Chennai Mathematical Institute, advised by Piyush Srivastava. I was a visiting student at TIFR, Mumbai, thanks to the generous support of Jaikumar Radhakrishnan and Prahladh Harsha.

Research & Publications

I'm broadly interested in quantum computing and analysis of Boolean functions. I'm especially interested in provable exponential speedups of quantum over classical, eliminating intermediate measurements and parallel repetition.

Quantum Advantages over Classical

The Power of Adaptivity in Quantum Query Algorithms

with Makrand Sinha, Avishay Tal and Kewen Wu.

In STOC 2024, QIP 2024. Arxiv

Trade-offs between Entanglement and Communication

with Srinivasan Arunachalam.

In CCC 2023, QIP 2024. Arxiv

One Clean Qubit Suffices for Quantum Communication Advantage

with Srinivasan Arunachalam and Noam Lifshitz.

In TQC 2024. Arxiv

Fourier Growth of Communication Protocols for XOR Functions

with Makrand Sinha, Avishay Tal and Kewen Wu.

In FOCS 2023. Arxiv

Fourier Growth of Parity Decision Trees

with Avishay Tal and Kewen Wu.

In CCC 2021. ECCC, Arxiv.

Lower Bounds for XOR of Forrelations

with Ran Raz and Wei Zhan.

In APPROX/RANDOM 2021. ECCC, Arxiv.

Quantum versus Randomized Communication Complexity, with Efficient Players

with Ran Raz and Avishay Tal.

In QIP 2020, ITCS 2021. ECCC, Arxiv.

Space-Bounded Computation

Quantum Logspace Computations are Verifiable

with Ran Raz and Wei Zhan.

In SOSA 2024. Arxiv

Is Untrusted Randomness Helpful?

with Ran Raz and Wei Zhan.

In ITCS 2023. Proceedings

Eliminating Intermediate Measurements using Pseudorandom Generators

with Ran Raz.

In ITCS 2022. ECCC, Arxiv.

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

with Ran Raz and Wei Zhan.

In QIP 2021, ICALP 2021. ECCC, Arxiv.

Parallel Repetition

Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

with Kunal Mittal, Ran Raz and Wei Zhan.

APPROX/RANDOM 2022. ECCC

Parallel Repetition For All 3-Player Games Over Binary Alphabet

with Justin Holmgren, Kunal Mittal, Ran Raz and Wei Zhan.

In STOC 2022. ECCC, Arxiv.

Parallel Repetition for the GHZ Game: A Simpler Proof

with Justin Holmgren, Kunal Mittal, Ran Raz and Wei Zhan.

In APPROX/RANDOM 2021. ECCC, Arxiv.

Selected Talks

Fourier Growth of Communication Protocols for XOR Functions

Simons Institute for the Theory of Computing, Berkeley. Link to video.

Parallel Repetition for the GHZ Game: A Simpler Proof

Institute for Advanced Study, Princeton. Link to video.

Quantum Logspace Algorithm for Powering Contraction Matrices

Institute for Quantum Computing (IQC), Waterloo Link to video.

Teaching

  • TA in COS340: Reasoning about Computation, Fall 2020.
  • TA in COS585: Information Theory and Applications, Fall 2019.