Overview
My research interests lie in computational complexity and logic, specifically the areas of circuit complexity (the quest for lower bounds in combinatorial models of computation) and finite model theory (the study of logical definability on finite structures). My work is supported by NSERC Discovery and Accelerator Grants, the Ontario Early Researcher Award, and a Sloan Research Fellowship.
Current Appointments & Affiliations
Associate Professor of Computer Science
·
2020 - Present
Computer Science,
Trinity College of Arts & Sciences
Associate Professor of Mathematics
·
2020 - Present
Mathematics,
Trinity College of Arts & Sciences
Recent Publications
Equi-Rank Homomorphism Preservation Theorem on Finite Structures
Conference Leibniz International Proceedings in Informatics, LIPIcs · February 3, 2025 The Homomorphism Preservation Theorem (HPT) of classical model theory states that a first-order sentence is preserved under homomorphisms if, and only if, it is equivalent to an existential-positive sentence. This theorem remains valid when restricted to f ... Full text CiteFormula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication
Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 10, 2024 Iterated Sub-Permutation Matrix Multiplication is the problem of computing the product of k n-by-n Boolean matrices with at most a single 1 in each row and column. For all d ≤ logk, this problem is solvable by size nO(dk1/d) monotone AC0 formulas of depth ... Full text CiteSymmetric Formulas for Products of Permutations
Conference Leibniz International Proceedings in Informatics, LIPIcs · January 1, 2023 We study the formula complexity of the word problem WordSn,k : (0, 1)kn2 → (0, 1): given n-by-n permutation matrices M1,..., Mk, compute the (1, 1)-entry of the matrix product M1 · · · Mk. An important feature of this function is that it is invariant under ... Full text CiteRecent Grants
NSF Student Travel Grant for 2023 Conference on Computational Complexity
ConferencePrincipal Investigator · Awarded by National Science Foundation · 2023 - 2025Rossman Alfred P. Sloan Foundation Fellowship (transfer)
FellowshipPrincipal Investigator · Awarded by Alfred P. Sloan Foundation · 2020 - 2021View All Grants
Education, Training & Certifications
Massachusetts Institute of Technology ·
2010
Ph.D.