Robert Andrews

Photo by Dan Komoda / Institute for Advanced Study

Email: robert_andrews at sfu dot ca
Office: TASC1 9405

I am an assistant professor in the School of Computing Science at Simon Fraser University.

I spent my postdoctoral years at the Institute for Advanced Study, the University of Waterloo, and the Simons Institute for the Theory of Computing. I received my Ph.D. in computer science from the University of Illinois Urbana-Champaign, where I was fortunate to be advised by Michael A. Forbes.

Teaching

Fall 2026

CMPT 409 & 981: Algebra and Computation

Research

I am broadly interested in computational complexity and particularly enjoy problems related to algebra. Here is a short talk, intended for a general mathematical audience, that describes some of my interests.

• Hilbert's Nullstellensatz is in the Counting Hierarchy
  with Abhibhav Garg and Éric Schost
  FOCS 2026
  [arXiv | ECCC | talk @ WACT 2026]
  
• An Improved Construction of Variety-Evasive Subspace Families
  with Abhibhav Garg
  RANDOM 2026
  [arXiv | ECCC | RANDOM]
  
• On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
  with Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas
  ITCS 2026
  [ITCS]
  
• Algebraic Pseudorandomness in VNC⁰
  CCC 2025
  [arXiv | ECCC | CCC]
  
• Polynomial-Time PIT from (Almost) Necessary Assumptions
  with Deepanshu Kush and Roei Tell
  STOC 2025
  [arXiv | ECCC | STOC]
  
• Constant-Depth Arithmetic Circuits for Linear Algebra Problems
  with Avi Wigderson
  FOCS 2024; SIAM Journal on Computing 2026
  Invited to SICOMP special issue on FOCS 2024
  [arXiv | ECCC | FOCS | SICOMP | talk @ IAS]
  
• On Matrix Multiplication and Polynomial Identity Testing
  FOCS 2022; SIAM Journal on Computing 2024
  Best Student Paper Award
  Invited to SICOMP special issue on FOCS 2022
  [arXiv | ECCC | FOCS | SICOMP | talk @ IAS]
  
• Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals
  with Michael A. Forbes
  STOC 2022
  Invited to Theory of Computing
  [arXiv | ECCC | STOC]
  
• Algebraic Hardness Versus Randomness in Low Characteristic
  CCC 2020
  [arXiv | ECCC | CCC]
  

Miscellaneous

• Polynomial Ideals in Algebraic Complexity
  Ph.D. dissertation
  [UIUC library]
• Need more RAM? Just invent time travel!
  with Mitchell Jones and Patrick Lin
  SIGBOVIK 2019
  "Most Frighteningly like Real Research!" award
  [SIGBOVIK proceedings]