Joshua A. Grochow

95 papers A* 6A 11B 5C 1Journal 70Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	On the parallel complexity of group isomorphism via Weisfeiler-Leman. J. Comput. Syst. Sci. Joshua A. Grochow, Michael Levet
2025	B	`conf`	Complexity of Identifying Fitting-Free Groups. FCT Joshua A. Grochow, Dan Johnson, Michael Levet
2025	A	`conf`	Finite Matrix Multiplication Algorithms from Infinite Groups. ITCS Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans
2025	J	`jnl`	Gröbner Bases Native to Term-ordered Commutative Algebras, with Application to the Hodge Algebra of Minors. CoRR Joshua A. Grochow, Abhiram Natarajan
2025	J	`jnl`	Multivariate Hensel Lifting Without Assuming as Many Variables as Equations. Am. Math. Mon. Joshua A. Grochow
2025	J	`jnl`	On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness. CoRR Joshua A. Grochow, Dan Johnson, Michael Levet
2025	A*	`conf`	On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications. STOC Joshua A. Grochow, Youming Qiao
2025	A*	`conf`	On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings. STOC Joshua A. Grochow, Youming Qiao, Katherine E. Stange, Xiaorui Sun
2025	J	`jnl`	On the Constant-Depth Circuit Complexity of Generating Quasigroups. TheoretiCS Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß
2025	J	`jnl`	On the Descriptive Complexity of Groups without Abelian Normal Subgroups. Log. Methods Comput. Sci. Joshua A. Grochow, Michael Levet
2025	J	`jnl`	Physical Complexity of a Cognitive Artifact. CoRR Gülce Kardes, David Krakauer, Joshua A. Grochow
2025	C	`conf`	Reconstructing Sets of Strings from Their k-Way Projections: Algorithms & Complexity - (Extended Abstract). IWOCA Elise Tate, Joshua A. Grochow
2025	J	`jnl`	Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity. CoRR Elise Tate, Joshua A. Grochow
2025	J	`jnl`	Universality in Collective Intelligence on the Rubik's Cube. CoRR David Krakauer, Gülce Kardes, Joshua A. Grochow
2024	B	`conf`	Constant Depth Circuit Complexity for Generating Quasigroups. ISSAC Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß
2024	J	`jnl`	Finite matrix multiplication algorithms from infinite groups. CoRR Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans
2024	J	`jnl`	On ACM Trans. Comput. Theory Joshua A. Grochow, Youming Qiao
2024	A	`conf`	On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. ITCS Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
2024	J	`jnl`	On the Constant-Depth Circuit Complexity of Generating Quasigroups. CoRR Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß
2023	J	`jnl`	Is stochastic thermodynamics the key to understanding the energy costs of computation? CoRR 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
2023	A	`conf`	Matrix Multiplication via Matrix Groups. ITCS Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans
2023	A	`conf`	On the Algebraic Proof Complexity of Tensor Isomorphism. CCC Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
2023	J	`jnl`	On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. SIAM J. Comput. Joshua A. Grochow, Youming Qiao
2023	—	`conf`	On the Descriptive Complexity of Groups without Abelian Normal Subgroups (Extended Abstract). GandALF Joshua A. Grochow, Michael Levet
2023	B	`conf`	On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman. FCT Joshua A. Grochow, Michael Levet
2023	J	`jnl`	On the algebraic proof complexity of Tensor Isomorphism. CoRR Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
2023	J	`jnl`	On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups. CoRR Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
2023	J	`jnl`	On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications. CoRR Joshua A. Grochow, Youming Qiao
2023	J	`jnl`	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 Joshua A. Grochow
2023	J	`jnl`	Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality. CoRR Joshua A. Grochow
2023	J	`jnl`	Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality. Theory Comput. Syst. Joshua A. Grochow
2022	J	`jnl`	Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms. Groups Complex. Cryptol. Joshua A. Grochow, Youming Qiao, Gang Tang
2022	—	`conf`	Experience Report: Standards-Based Grading at Scale in Algorithms. ITiCSE (1) Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet
2022	J	`jnl`	Experience Report: Standards-Based Grading at Scale in Algorithms. CoRR Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet
2022	J	`jnl`	Matrix multiplication via matrix groups. CoRR Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans
2022	J	`jnl`	On the Descriptive Complexity of Groups without Abelian Normal Subgroups. CoRR Joshua A. Grochow, Michael Levet
2021	A	`conf`	Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms. STACS Joshua A. Grochow, Youming Qiao, Gang Tang
2021	A	`conf`	On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. CCC Joshua A. Grochow, Youming Qiao
2021	A	`conf`	On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. ITCS Joshua A. Grochow, Youming Qiao
2021	J	`jnl`	Weisfeiler-Leman for Group Isomorphism: Action Compatibility. CoRR Joshua A. Grochow, Michael Levet
2020	J	`jnl`	An Improved Algorithm for Coarse-Graining Cellular Automata. CoRR Yerim Song, Joshua A. Grochow
2020	J	`jnl`	Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms. CoRR Joshua A. Grochow, Youming Qiao, Gang Tang
2020	J	`jnl`	Complexity in Ideals of Polynomials: Questions on Algebraic Complexity of Circuits and Proofs. Bull. EATCS Joshua A. Grochow
2020	J	`jnl`	Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs. Bull. EATCS Joshua A. Grochow
2019	J	`jnl`	Incorporating Weisfeiler-Leman into algorithms for group isomorphism. CoRR Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, James B. Wilson
2019	J	`jnl`	Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. CoRR Joshua A. Grochow, Youming Qiao
2018	J	`jnl`	Beyond Number of Bit Erasures: New Complexity Questions Raised by Recently Discovered Thermodynamic Costs of Computation. SIGACT News Joshua A. Grochow, David H. Wolpert
2018	J	`jnl`	Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System. J. ACM Joshua A. Grochow, Toniann Pitassi
2018	A*	`conf`	Computational Topology and the Unique Games Conjecture. SoCG Joshua A. Grochow, Jamie Tucker-Foltz
2018	J	`jnl`	Computational topology and the Unique Games Conjecture. CoRR Joshua A. Grochow, Jamie Tucker-Foltz
2018	A	`conf`	Minimum Circuit Size, Graph Isomorphism, and Related Problems. ITCS Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2018	J	`jnl`	Minimum Circuit Size, Graph Isomorphism, and Related Problems. SIAM J. Comput. Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2017	J	`jnl`	Algorithms for Group Isomorphism via Group Extensions and Cohomology. SIAM J. Comput. Joshua A. Grochow, Youming Qiao
2017	J	`jnl`	Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines. CoRR Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay
2017	J	`jnl`	Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines. Entropy Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay
2017	J	`jnl`	Designing Strassen's algorithm. CoRR Joshua A. Grochow, Cristopher Moore
2017	J	`jnl`	Designing Strassen's algorithm. Electron. Colloquium Comput. Complex. Joshua A. Grochow, Cristopher Moore
2017	J	`jnl`	Minimum Circuit Size, Graph Isomorphism, and Related Problems. CoRR Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2017	J	`jnl`	Minimum Circuit Size, Graph Isomorphism, and Related Problems. Electron. Colloquium Comput. Complex. Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
2017	J	`jnl`	Monotone Projection Lower Bounds from Extended Formulation Lower Bounds. Theory Comput. Joshua A. Grochow
2017	J	`jnl`	Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
2017	J	`jnl`	Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
2017	J	`jnl`	Which groups are amenable to proving exponent two for matrix multiplication? CoRR Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans
2016	A*	`conf`	Boundaries of VP and VNP. ICALP Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
2016	J	`jnl`	Boundaries of VP and VNP. CoRR Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
2016	J	`jnl`	Dynamics of beneficial epidemics. CoRR 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
2016	J	`jnl`	Matrix multiplication algorithms from group orbits. CoRR Joshua A. Grochow, Cristopher Moore
2016	J	`jnl`	NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications. CoRR Joshua A. Grochow
2016	J	`jnl`	NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications. Electron. Colloquium Comput. Complex. Joshua A. Grochow
2016	J	`jnl`	On cap sets and the group-theoretic approach to matrix multiplication. CoRR Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans
2015	J	`jnl`	Graph Isomorphism and Circuit Size. CoRR Eric Allender, Joshua A. Grochow, Cristopher Moore
2015	J	`jnl`	Graph Isomorphism and Circuit Size. Electron. Colloquium Comput. Complex. Eric Allender, Joshua A. Grochow, Cristopher Moore
2015	J	`jnl`	Monotone projection lower bounds from extended formulation lower bounds. CoRR Joshua A. Grochow
2015	J	`jnl`	Monotone projection lower bounds from extended formulation lower bounds. Electron. Colloquium Comput. Complex. Joshua A. Grochow
2015	J	`jnl`	Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition. CoRR Laurent Hébert-Dufresne, Joshua A. Grochow, Antoine Allard
2015	B	`conf`	Polynomial-Time Isomorphism Test of Groups that are Tame Extensions - (Extended Abstract). ISAAC Joshua A. Grochow, Youming Qiao
2015	J	`jnl`	Polynomial-time isomorphism test of groups that are tame extensions. CoRR Joshua A. Grochow, Youming Qiao
2015	J	`jnl`	Unifying Known Lower Bounds via Geometric Complexity Theory. Comput. Complex. Joshua A. Grochow
2014	J	`jnl`	A framework for optimal high-level descriptions in science and engineering - preliminary report. CoRR David H. Wolpert, Joshua A. Grochow, Eric Libby, Simon DeDeo
2014	A	`conf`	Algorithms for Group Isomorphism via Group Extensions and Cohomology. CCC Joshua A. Grochow, Youming Qiao
2014	A*	`conf`	Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. FOCS Joshua A. Grochow, Toniann Pitassi
2014	J	`jnl`	Circuit complexity, proof complexity, and polynomial identity testing. CoRR Joshua A. Grochow, Toniann Pitassi
2014	J	`jnl`	Circuit complexity, proof complexity, and polynomial identity testing. Electron. Colloquium Comput. Complex. Joshua A. Grochow, Toniann Pitassi
2014	A	`conf`	Unifying Known Lower Bounds via Geometric Complexity Theory. CCC Joshua A. Grochow
2013	J	`jnl`	Algorithms for group isomorphism via group extensions and cohomology. CoRR Joshua A. Grochow, Youming Qiao
2013	J	`jnl`	Algorithms for group isomorphism via group extensions and cohomology. Electron. Colloquium Comput. Complex. Joshua A. Grochow, Youming Qiao
2013	J	`jnl`	Unifying and generalizing known lower bounds via geometric complexity theory CoRR Joshua A. Grochow
2012	A	`conf`	Matrix Isomorphism of Matrix Lie Algebras. CCC Joshua A. Grochow
2012	J	`jnl`	Report on "Mathematical Aspects of P vs. NP and its Variants." CoRR Joshua A. Grochow, Korben Rusek
2011	A*	`conf`	Code Equivalence and Group Isomorphism. SODA László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao
2011	J	`jnl`	Complexity classes of equivalence problems revisited. Inf. Comput. Lance Fortnow, Joshua A. Grochow
2011	J	`jnl`	Lie algebra conjugacy CoRR Joshua A. Grochow
2011	J	`jnl`	Lie algebra conjugacy. Electron. Colloquium Comput. Complex. Joshua A. Grochow
2009	J	`jnl`	Complexity Classes of Equivalence Problems Revisited CoRR Lance Fortnow, Joshua A. Grochow
2007	B	`conf`	Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking. RECOMB Joshua A. Grochow, Manolis Kellis