Picture of Joshua A. Grochow Joshua A. Grochow
Omidyar Fellow
Santa Fe Institute

Office: C-4
Office phone: (505)-946-2789
Email: [first initial][lastname]@santafe.edu

About Me

I am an Omidyar Fellow at the interdisciplinary Santa Fe Institute; my "home discipline" is (theoretical) computer science. My research lies primarily at the intersection of theoretical computer science and mathematics—particularly algebraic geometry, representation theory, and group theory—but I am starting to branch out into more general complex systems and, thereby, more worldly pursuits such as biology, energy, and the environment (which I've been interested in for most of my career).

Prior to coming to the Santa Fe Institute, 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

(November 3, 2015) Updated Monotone projection lower bounds from extended formulation lower bounds with new lower bound against reductions from perfect matchings in general graphs to perfect matchings in bipartite graphs.

(October 29, 2015) New paper posted: Network structure at multiple scales via a new network statistic: the onion decomposition, joint with Laurent Hébert-Dufresne and Antoine Allard.

(October 28, 2015) New paper posted: Monotone projection lower bounds from extended formulation lower bounds.

(October 12-16, 2015) Organized the SFI Workshop on Wildness in Computer Science, Physics, and Mathematics.

(October 8, 2015) New paper posted: Graph isomorphism and circuit size, joint with Eric Allender and Cris Moore.

(October 1, 2015) Eric Allender gave a great 15-minute talk at the Simons Institute for the Theory of Computing on our most recent joint work with Cris Moore, "Graph Isomorphism and Circuit Size."

(August 31, 2015) Polynomial-time isomorphism test of groups that are tame extensions accepted to ISAAC 2015 (the leading conference on algorithms in (East) Asia). Join my co-author Youming Qiao at the conference in Nagoya, Japan this December!

(July 14, 2015) You can listen to my interview by @Samuel_Hansen for the Strongly Connected Components podcast. My segment starts at 40:45, but you should also listen to the preceding interviews with my colleagues Yoav Kallus and Sid Redner!

(July 7, 2015) New paper posted: Polynomial-time isomorphism test of groups that are tame extensions (joint w/ Youming Qiao).

(May 9, 2015) The final, significantly expanded and edited version of Unifying known lower bounds via geometric complexity theory has now appeared in Computational Complexity, and is freely available forever (thanks to funding from SFI).

(Apr 21, 2015) Gave a CS colloquium at UNM: The role of symmetry (or the lack thereof) in algorithms and computational complexity.

(Jan 5, 2015) Video of Toni Pitassi's FOCS 2014 talk on our joint paper, "Circuit complexity, proof complexity, and polynomial identity testing," is now available!

(Dec 30, 2014) Li, Tzameret, and Wang built off our previous work to show that the Non-Commutative Formula Ideal Proof System (an algebraic proof system) is quasi-polynomially equivalent to the standard Frege Boolean proof system!