Robert Andrews

Photo by Dan Komoda / Institute for Advanced Study

Email: randrews at uwaterloo dot ca
Office: DC 2306L

I am a William T. Tutte Postdoctoral Fellow in the Cheriton School of Computer Science at the University of Waterloo, where I am hosted by Rafael Oliveira.

Previously, I was a postdoctoral member at the Institute for Advanced Study. I spent the Fall 2025 term at the Simons Institute as part of the Complexity and Linear Algebra program. 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.

Research

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

• An Improved Construction of Variety-Evasive Subspace Families
  with Abhibhav Garg
  Manuscript
  [arXiv | ECCC]
  
• Hilbert's Nullstellensatz is in the Counting Hierarchy
  with Abhibhav Garg and Éric Schost
  Manuscript
  [arXiv | ECCC]
  
• 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]