Adrian She

Introduction

I am a recent PhD graduate within the theoretical computer science research group at the University of Toronto, which comprise of faculty and students from the Departments of Computer Science and Mathematics. I am also recently a Course Instructor in the Departments of Mathematics and Computer Science.

I was fortunate to be advised by Toni Pitassi and Henry Yuen. Previously, I obtained a B.Sc. in mathematics and computer science, with a minor in physics at the University of British Columbia, where I was fortunate to be advised by numerous faculty through its undergraduate research (USRA) program. I was supported by an NSERC Canada Graduate Scholarship.

My research interests currently include:

• Quantum algorithms and complexity theory : To what extent do quantum computers provide a computational advantage over classical computers? Conversely, what are the limitations of quantum computing? These questions can be explored for various computational models (eg. query complexity, communication complexity, NISQ devices) and are particularly exciting to work on, given that the first generation of quantum computers are currently being built. I am especially interested in algebraic methods such as the polynomial method and representation theory methods for proving lower bounds.
• Proof complexity : Does every mathematical theorem have a short proof? Proof complexity aims to formalize the previous question, which can be studied in various proof systems. For example, Hilbert's Nullstellensatz is a proof system for certifying that a system of polynomial equations has no solution. There are profound connections between proof complexity with major open problems in computational complexity (eg. P versus NP), as well as optimization algorithms used in practical applications and automated theorem proving.

I also maintain a general interest in other areas of discrete mathematics and theoretical computer science, as well as mathematics pedagogy. Outside of academics, I also enjoy music and cooking.

Email: ashe [at] cs [dot] toronto [dot] edu

My CV (Updated Dec 2024)

My PhD Thesis: Algebraic Methods in Query and Proof Complexity

Research Publications

1. Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs
   Kunal Marwaha, Adrian She, James Sud
   [arXiv]

2. On the algebraic proof complexity of Tensor Isomorphism
   Nicola Galesi, Joshua Grochow, Toni Pitassi, and Adrian She
   [arXiv] [Conference Version (CCC 2023)] [Video Presentation by Me at CCC 2023]

3. Unitary property lower testing lower bounds by polynomials
   Adrian She and Henry Yuen
   [arXiv] [Conference Version (ITCS 2023)] [video submission for ITCS 2023][video presentation by John Bostanci at QIP 2023]

4. Schur polynomials do not have small formulas if the Determinant doesn't
   Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan
   Published in computational complexity (2023).
   [arXiv] [Conference Version (CCC 2020) [Journal Version]

5. A Quadratic Lower Bound for Algebraic Branching Programs
   Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
   Published in computational complexity (2022).
   [arXiv] [Conference Version (CCC 2020)] [Journal Version]

6. Chromatic Posets
   Samantha Dahlberg, Adrian She, and Stephanie van Willigenburg
   Published in Journal of Combinatorial Theory Series A (2021).
   [arXiv] [Journal Version]

7. Schur and e-positivity of trees and cut vertices
   Samantha Dahlberg, Adrian She, and Stephanie van Willigenburg
   Published in Electronic Journal of Combinatorics Volume 27 (2020).
   [arXiv] [Journal Version]

Additional Writing and Projects

• Quantum Non-Local Games and Representation Theory (with Deepanshu Kush)
  We describe linear system games and describe how (approximate) representation theory is used to analyze the maximum winning probability of these games when their players are allowed to use quantum strategies.


• Limitations of Quantum Fourier Sampling (with Adrian Chiu)
  We describe the quantum Fourier sampling algorithm and prove that quantum Fourier sampling cannot be used to solve the graph isomorphism problem in quantum polynomial time.


• Quantum Complexity Theory - Myths and Facts
  I gave a talk for the University of Toronto quantum computing club outlining the basics of quantum complexity theory, with a focus on why there is believed to be a quantum advantage for factoring, what kind of problems we expect to have quantum speedups for, and why research in quantum computing is important despite fault-tolerant quantum computing being impractical with current technology. Slides and a Zoom recording are available on the club's website.


• Toda's Theorem
  These notes sketch the proof of Toda's theorem and outlines one of its applications to the study of quantum supremacy conjectures, and are based on a presentation to the University of Toronto Theory Student Seminar.


• Introduction to proof complexity
  These notes introduce the resolution proof system and proves the well-known lower bound that the pigeonhole principle requires exponentially long resolution proofs, and are based on a presentation to the University of Toronto Theory Student Seminar.


• Notes on Boolean Function Analysis
  Two lectures on Boolean function analysis delivered at the University of Toronto Theory Student Seminar.

Teaching

In Fall 2024, I was course instructor for CSC 265: Enriched Data Structures and Analysis, and MAT 186: Calculus I. Course websites were kept on Quercus (the University of Toronto LMS).

In Winter 2020, I was course instructor for CSC 463: Computational Complexity and Computability.

I promise that I will make more visually appealling website someday.