Joshua A. Grochow

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 61

Top Topics

Boltzmann Machine

Matrix Multiplication

Related Problems

Extended Abstract

Top Venues

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

Publications

Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. ITCS (2024)
Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß
Constant Depth Circuit Complexity for Generating Quasigroups. ISSAC (2024)
Joshua A. Grochow, Youming Qiao
-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors. ACM Trans. Comput. Theory 16 (1) (2024)
Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß
On the Constant-Depth Circuit Complexity of Generating Quasigroups. CoRR (2024)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
On the Algebraic Proof Complexity of Tensor Isomorphism. CCC (2023)
Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans
Matrix Multiplication via Matrix Groups. ITCS (2023)
Joshua A. Grochow, Michael Levet
On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman. FCT (2023)
Joshua A. Grochow, Youming Qiao
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications. CoRR (2023)
Joshua A. Grochow, Michael Levet
On the Descriptive Complexity of Groups without Abelian Normal Subgroups (Extended Abstract). GandALF (2023)
David H. Wolpert, Jan Korbel, Christopher Lynn, Farita Tasnim, Joshua A. Grochow, Gülce Kardes, James B. Aimone, Vijay Balasubramanian, Eric De Giuli, David Doty, Nahuel Freitas, Matteo Marsili, Thomas E. Ouldridge, Andréa W. Richa, Paul M. Riechers, Édgar Roldán, Brenda M. Rubenstein, Zoltán Toroczkai, Joseph A. Paradiso
Is stochastic thermodynamics the key to understanding the energy costs of computation? CoRR (2023)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
On the algebraic proof complexity of Tensor Isomorphism. CoRR (2023)
Joshua A. Grochow
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality. Theory Comput. Syst. 67 (3) (2023)
Joshua A. Grochow
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality. CoRR (2023)
Joshua A. Grochow, Youming Qiao
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. SIAM J. Comput. 52 (2) (2023)
Joshua A. Grochow
Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system. CoRR (2023)
Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups. CoRR (2023)
Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet
Experience Report: Standards-Based Grading at Scale in Algorithms. ITiCSE (1) (2022)
Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet
Experience Report: Standards-Based Grading at Scale in Algorithms. CoRR (2022)
Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans
Matrix multiplication via matrix groups. CoRR (2022)
Joshua A. Grochow, Michael Levet
On the Descriptive Complexity of Groups without Abelian Normal Subgroups. CoRR (2022)
Joshua A. Grochow, Michael Levet
Weisfeiler-Leman for Group Isomorphism: Action Compatibility. CoRR (2021)
Joshua A. Grochow, Youming Qiao
On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. Computational Complexity Conference (2021)
Joshua A. Grochow, Youming Qiao
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. ITCS (2021)
Joshua A. Grochow, Youming Qiao, Gang Tang
Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms. STACS (2021)
Joshua A. Grochow, Youming Qiao, Gang Tang
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms. CoRR (2020)
Joshua A. Grochow
Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs. Bull. EATCS 131 (2020)
Joshua A. Grochow
Complexity in Ideals of Polynomials: Questions on Algebraic Complexity of Circuits and Proofs. Bull. EATCS 130 (2020)
Yerim Song, Joshua A. Grochow
An Improved Algorithm for Coarse-Graining Cellular Automata. CoRR (2020)
Joshua A. Grochow, Youming Qiao
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. CoRR (2019)
Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, James B. Wilson
Incorporating Weisfeiler-Leman into algorithms for group isomorphism. CoRR (2019)
Joshua A. Grochow, David H. Wolpert
Beyond Number of Bit Erasures: New Complexity Questions Raised by Recently Discovered Thermodynamic Costs of Computation. SIGACT News 49 (2) (2018)
Joshua A. Grochow, Jamie Tucker-Foltz
Computational Topology and the Unique Games Conjecture. SoCG (2018)
Joshua A. Grochow, Toniann Pitassi
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System. J. ACM 65 (6) (2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. SIAM J. Comput. 47 (4) (2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. ITCS (2018)
Joshua A. Grochow, Jamie Tucker-Foltz
Computational topology and the Unique Games Conjecture. CoRR (2018)
Joshua A. Grochow, Cristopher Moore
Designing Strassen's algorithm. Electron. Colloquium Comput. Complex. 24 (2017)
Joshua A. Grochow, Youming Qiao
Algorithms for Group Isomorphism via Group Extensions and Cohomology. SIAM J. Comput. 46 (4) (2017)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. Electron. Colloquium Comput. Complex. 24 (2017)
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. 24 (2017)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Minimum Circuit Size, Graph Isomorphism, and Related Problems. CoRR (2017)
Joshua A. Grochow
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds. Theory Comput. 13 (1) (2017)
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR (2017)
Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay
Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines. Entropy 19 (7) (2017)
Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans
Which groups are amenable to proving exponent two for matrix multiplication? CoRR (2017)
Joshua A. Grochow, Cristopher Moore
Designing Strassen's algorithm. CoRR (2017)
Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay
Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines. CoRR (2017)
Andrew Berdahl, Christa Brelsford, Caterina De Bacco, Marion Dumas, Vanessa Ferdinand, Joshua A. Grochow, Laurent Hébert-Dufresne, Yoav Kallus, Christopher P. Kempes, Artemy Kolchinsky, Daniel B. Larremore, Eric Libby, Eleanor A. Power, Caitlin A. Stern, Brendan D. Tracey
Dynamics of beneficial epidemics. CoRR (2016)
Joshua A. Grochow
NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications. CoRR (2016)
Joshua A. Grochow, Cristopher Moore
Matrix multiplication algorithms from group orbits. CoRR (2016)
Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
Boundaries of VP and VNP. ICALP (2016)
Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans
On cap sets and the group-theoretic approach to matrix multiplication. CoRR (2016)
Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
Boundaries of VP and VNP. CoRR (2016)
Laurent Hébert-Dufresne, Joshua A. Grochow, Antoine Allard
Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition. CoRR (2015)
Joshua A. Grochow, Youming Qiao
Polynomial-time isomorphism test of groups that are tame extensions. CoRR (2015)
Joshua A. Grochow
Unifying Known Lower Bounds via Geometric Complexity Theory. Comput. Complex. 24 (2) (2015)
Joshua A. Grochow
Monotone projection lower bounds from extended formulation lower bounds. CoRR (2015)
Joshua A. Grochow
Monotone projection lower bounds from extended formulation lower bounds. Electron. Colloquium Comput. Complex. 22 (2015)
Eric Allender, Joshua A. Grochow, Cristopher Moore
Graph Isomorphism and Circuit Size. Electron. Colloquium Comput. Complex. 22 (2015)
Joshua A. Grochow, Youming Qiao
Polynomial-Time Isomorphism Test of Groups that are Tame Extensions - (Extended Abstract). ISAAC (2015)
Eric Allender, Joshua A. Grochow, Cristopher Moore
Graph Isomorphism and Circuit Size. CoRR (2015)
Joshua A. Grochow, Youming Qiao
Algorithms for Group Isomorphism via Group Extensions and Cohomology. Computational Complexity Conference (2014)
Joshua A. Grochow
Unifying Known Lower Bounds via Geometric Complexity Theory. Computational Complexity Conference (2014)
Joshua A. Grochow, Toniann Pitassi
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. FOCS (2014)
David H. Wolpert, Joshua A. Grochow, Eric Libby, Simon DeDeo
A framework for optimal high-level descriptions in science and engineering - preliminary report. CoRR (2014)
Joshua A. Grochow, Toniann Pitassi
Circuit complexity, proof complexity, and polynomial identity testing. Electron. Colloquium Comput. Complex. 21 (2014)
Joshua A. Grochow, Toniann Pitassi
Circuit complexity, proof complexity, and polynomial identity testing. CoRR (2014)
Joshua A. Grochow, Youming Qiao
Algorithms for group isomorphism via group extensions and cohomology. Electron. Colloquium Comput. Complex. 20 (2013)
Joshua A. Grochow, Youming Qiao
Algorithms for group isomorphism via group extensions and cohomology. CoRR (2013)
Joshua A. Grochow
Unifying and generalizing known lower bounds via geometric complexity theory CoRR (2013)
Joshua A. Grochow
Matrix Isomorphism of Matrix Lie Algebras. Computational Complexity Conference (2012)
Joshua A. Grochow, Korben Rusek
Report on "Mathematical Aspects of P vs. NP and its Variants." CoRR (2012)
László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao
Code Equivalence and Group Isomorphism. SODA (2011)
Lance Fortnow, Joshua A. Grochow
Complexity classes of equivalence problems revisited. Inf. Comput. 209 (4) (2011)
Joshua A. Grochow
Lie algebra conjugacy CoRR (2011)
Joshua A. Grochow
Lie algebra conjugacy. Electron. Colloquium Comput. Complex. 18 (2011)
Lance Fortnow, Joshua A. Grochow
Complexity Classes of Equivalence Problems Revisited CoRR (2009)
Joshua A. Grochow, Manolis Kellis
Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking. RECOMB (2007)