Picture of Joshua A. Grochow
Joshua A. Grochow
Assistant Professor
Departments of Computer Science and Mathematics
University of Colorado at Boulder
[first initial][last name]@colorado.edu
ECES 118E   (303) 735-7438   Fax: (303) 492-2844 (ATTN: me)
CS Theory @ CU Boulder
Complex Systems @ CU Boulder

We're hiring in quantum! Deadline Nov 15.

Me @ Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC DBLP MathSciNet Google Scholar SciRate

About Me

I am an Assistant Professor in the Departments of Computer Science and Mathematics at the University of Colorado at Boulder, where I am a member of the CS Theory Group and the Complex Systems Group. My research has two main thrusts (with deep underlying relations beneath):

For a taste of the deep underlying relations, check out this brief video.

I was previously an Omidyar Fellow at the interdisciplinary Santa Fe Institute for complex systems. Prior to SFI, I was a postdoc in the University of Toronto CS Theory Group, and prior to that I got my Ph.D. at the University of Chicago.

What's new

(Dec 27, 2018) Wildness for tensors accepted to Linear Algebra and its Applications! Joint with Vyacheslav Futorny and Vladimir V. Sergeichuk.

(Oct 22, 2018) New paper posted online: Wildness for tensors! Joint with Vyacheslav Futorny and Vladimir V. Sergeichuk.

(Oct 1, 2018) New expository paper published in the Bulletin of the AMS: New applications of the polynomial method: the cap set conjecture and beyond!

(July 23-26, 2018) Invited speaker at the Clay Math Institute/Oxford Workshop on Complexity Theory! I spoke on "Complexity in Ideals of Polynomials." Student support available.

(July 23, 2018) Report from the January Dagstuhl Workshop on Proof Complexity now available, including lots of great open questions!

(June 18, 2018) New paper published with David H. Wolpert: Beyond number of bit erasures: New complexity questions raised by recently discovered thermodynamic costs of computation in SIGACT News! Feedback more than welcome.

(June 14, 2018) My co-author Jamie Tucker-Foltz presented @ SoCG 2018 on our joint paper "Computational topology and the Unique Games Conjecture."

(June 1, 2018) The Ideal Proof System accepted to J. ACM! (To appear.)

(June 1, 2018) I'm happy to announce that Alex Kolla and I have hired Eric Reckwerdt and Nathan Lindzey as our postdocs! They'll be starting Fall '18 and Jan '19, respectively.

(May 1, 2018) Gave a talk in the Topology Seminar in the CU Math Department on Computational topology and the Unique Games Conjecture.

(Mar 20, 2018) New paper posted: "Computational topology and the Unique Games Conjecture", to appear at SoCG 2018. Joint with Jamie Tucker-Foltz.

(Mar 19, 2018) Minimum circuit size, graph isomorphism, and related problems accepted to SIAM J. Comput.! Joint with Eric Allender, Dieter van Melkebeek, Cris Moore, and Andrew Morgan.

(Mar 16, 2018) Gave a talk in the CU Boulder Applied Math Colloquium: "Computational Complexity, Dynamical Systems, and Non-Convex Optimization."

(Mar 2, 2018) Gave a talk at the Rocky Mountain Algebraic Combinatorics Seminar: "Combinatorial Polytopes in Algebraic and Geometric Complexity Theory," based partially on these two papers.

(Feb 28, 2018) Presented "Computational Complexity and Mathematics" at the CU Boulder Math Club. With computer science, math, pizza, and drinks, how can you go wrong?

(Feb 16, 2018) "Computational topology and the Unique Games Conjecture" accepted to SoCG 2018. Joint with Jamie Tucker-Foltz. Preprint coming soon UPDATE 3/20/2018: now available!

(Due Jan 31, 2018) We solicited applications for a Postdoctoral Fellowship beginning 2018! Algebraic/geometric complexity, spectral algorithms, unique games, and more with me and Alex Kolla. Check out our theory group.

(Jan 31, 2018) Gave a talk on Ideal Proof Systems at this Dagstuhl Workshop on Proof Complexity. Update 7/23/2018: report now available.

(Jan 12, 2018) Gave an invited talk at the AMS Current Events Bulletin, "The Cap Set Conjecture, the polynomial method, and applications (after Croot-Lev-Pach, Ellenberg-Gijswijt, and others)." You can find a write-up associated with the talk in the 2018 Current Events Bulletin booklet.

See all past updates