My name is Gregory Rosenthal. I am a fifth-year MSc/PhD student at the University of Toronto, where I am fortunate to be co-advised by Benjamin Rossman and Henry Yuen. Previously I was a math major and computer science minor at Cornell. My research interests are in computational complexity theory and related areas, including quantum circuit complexity and boolean function analysis.


photo of me

Research Papers

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Gregory Rosenthal
TQC 2022 (slides) - workshop track

Interactive Proofs for Synthesizing Quantum States and Unitaries
Gregory Rosenthal and Henry Yuen
ITCS 2022 (video, slides)
QIP 2022

Bounds on the QAC0 Complexity of Approximating Parity
Gregory Rosenthal
ITCS 2021 (Best Student Paper Award) (video, slides)
TQC 2021 - workshop track

Beating Treewidth for Average-Case Subgraph Isomorphism
Gregory Rosenthal
IPEC 2019 (Best Student Paper Award) (slides)
Algorithmica Special Issue for IPEC 2019

Other Writings

Teaching Assistantships

University of Toronto

Fall 2022 CSC 2332 Introduction to Quantum Algorithms
Fall 2021 CSC 2429 Algebraic Gems in Theoretical Computer Science and Discrete Mathematics
Fall 2020 CSC 2426 Fundamentals of Cryptography
Fall 2020 CSC 2429 Advanced Topics in Quantum Information Theory
Summer 2020 CSC 336 Numerical Methods
Winter 2020 CSC 463 Computational Complexity and Computability
Fall 2019 CSC 373 Algorithm Design, Analysis and Complexity
Summer 2019 CSC 263 Data Structures and Analysis
Winter 2019 CSC 2556 Algorithms for Collective Decision Making
Fall 2018 CSC 2451 Quantum Computing: Foundations to Frontier
Summer 2018 CSC 165 Mathematical Expression and Reasoning for Computer Science
Winter 2018 CSC 473 Advanced Algorithm Design
Fall 2017 CSC 373 Algorithm Design, Analysis and Complexity

Cornell University

Spring 2016 CS 4820 Introduction to Analysis of Algorithms


In Fall 2018 I attended the beginning of the Lower Bounds in Computational Complexity program at the Simons Institute for the Theory of Computing. I visited Tom Gur at University of Warwick for the first half of Summer 2022, and I am visiting Henry Yuen at Columbia University for most of the Fall 2022 semester.

Other Activities

From Jan. 2018 to July 2019 I coordinated the weekly Cookiebreak for grad students in the department. I play cello in an orchestra on campus, and as an undergrad I played in the Cornell Orchestras and also conducted the Cornell Eastern Music Ensemble.