default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJoshua A. Grochow
Person information
- affiliation: University of Colorado at Boulder, Department of Computer Science, CO, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2024
[j13]Joshua A. Grochow
, Youming Qiao:
On p-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors. ACM Trans. Comput. Theory 16(1): 2:1-2:39 (2024)- 2023
- [j12]Joshua A. Grochow:
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality. Theory Comput. Syst. 67(3): 627-669 (2023) - [j11]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): 568-617 (2023) - 2020
- [j10]Joshua A. Grochow:
Complexity in Ideals of Polynomials: Questions on Algebraic Complexity of Circuits and Proofs. Bull. EATCS 130 (2020) - [j9]Joshua A. Grochow:
Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs. Bull. EATCS 131 (2020) - 2018
- [j8]Joshua A. Grochow, Toniann Pitassi:
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System. J. ACM 65(6): 37:1-37:59 (2018) - [j7]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): 1339-1372 (2018) - [j6]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): 33-56 (2018) - 2017
- [j5]Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay:
Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines. Entropy 19(7): 310 (2017) - [j4]Joshua A. Grochow, Youming Qiao:
Algorithms for Group Isomorphism via Group Extensions and Cohomology. SIAM J. Comput. 46(4): 1153-1216 (2017) - [j3]Joshua A. Grochow:
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds. Theory Comput. 13(1): 1-15 (2017) - 2015
- [j2]Joshua A. Grochow:
Unifying Known Lower Bounds via Geometric Complexity Theory. Comput. Complex. 24(2): 393-475 (2015) - 2011
- [j1]Lance Fortnow, Joshua A. Grochow:
Complexity classes of equivalence problems revisited. Inf. Comput. 209(4): 748-763 (2011)
Conference and Workshop Papers
- 2024
- [c20]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: 31:1-31:23 - [c19]Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß:
Constant Depth Circuit Complexity for Generating Quasigroups. ISSAC 2024: 198-207 - 2023
- [c18]Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She:
On the Algebraic Proof Complexity of Tensor Isomorphism. CCC 2023: 4:1-4:40 - [c17]Joshua A. Grochow, Michael Levet:
On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman. FCT 2023: 234-247 - [c16]Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Matrix Multiplication via Matrix Groups. ITCS 2023: 19:1-19:16 - [c15]Joshua A. Grochow, Michael Levet:
On the Descriptive Complexity of Groups without Abelian Normal Subgroups (Extended Abstract). GandALF 2023: 185-202 - 2022
- [c14]Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet:
Experience Report: Standards-Based Grading at Scale in Algorithms. ITiCSE (1) 2022: 221-227 - 2021
- [c13]Joshua A. Grochow, Youming Qiao:
On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. CCC 2021: 16:1-16:38 - [c12]Joshua A. Grochow, Youming Qiao:
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. ITCS 2021: 31:1-31:19 - [c11]Joshua A. Grochow, Youming Qiao, Gang Tang:
Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms. STACS 2021: 38:1-38:17 - 2018
- [c10]Joshua A. Grochow, Jamie Tucker-Foltz:
Computational Topology and the Unique Games Conjecture. SoCG 2018: 43:1-43:16 - [c9]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. ITCS 2018: 20:1-20:20 - 2016
- [c8]Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao:
Boundaries of VP and VNP. ICALP 2016: 34:1-34:14 - 2015
- [c7]Joshua A. Grochow, Youming Qiao:
Polynomial-Time Isomorphism Test of Groups that are Tame Extensions - (Extended Abstract). ISAAC 2015: 578-589 - 2014
- [c6]Joshua A. Grochow, Youming Qiao:
Algorithms for Group Isomorphism via Group Extensions and Cohomology. CCC 2014: 110-119 - [c5]Joshua A. Grochow:
Unifying Known Lower Bounds via Geometric Complexity Theory. CCC 2014: 274-285 - [c4]Joshua A. Grochow, Toniann Pitassi:
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. FOCS 2014: 110-119 - 2012
- [c3]Joshua A. Grochow:
Matrix Isomorphism of Matrix Lie Algebras. CCC 2012: 203-213 - 2011
- [c2]László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao:
Code Equivalence and Group Isomorphism. SODA 2011: 1395-1408 - 2007
- [c1]Joshua A. Grochow, Manolis Kellis:
Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking. RECOMB 2007: 92-106
Informal and Other Publications
- 2024
- [i46]Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß:
On the Constant-Depth Circuit Complexity of Generating Quasigroups. CoRR abs/2402.00133 (2024) - 2023
- [i45]Joshua A. Grochow:
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality. CoRR abs/2301.07123 (2023) - [i44]Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She:
On the algebraic proof complexity of Tensor Isomorphism. CoRR abs/2305.19320 (2023) - [i43]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 abs/2306.02184 (2023) - [i42]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 abs/2306.03135 (2023) - [i41]Joshua A. Grochow, Youming Qiao:
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications. CoRR abs/2306.16317 (2023) - [i40]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 abs/2311.17166 (2023) - 2022
- [i39]Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Matrix multiplication via matrix groups. CoRR abs/2204.03826 (2022) - [i38]Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet:
Experience Report: Standards-Based Grading at Scale in Algorithms. CoRR abs/2204.12046 (2022) - [i37]Joshua A. Grochow, Michael Levet:
On the Descriptive Complexity of Groups without Abelian Normal Subgroups. CoRR abs/2209.13725 (2022) - 2021
- [i36]Joshua A. Grochow, Michael Levet:
Weisfeiler-Leman for Group Isomorphism: Action Compatibility. CoRR abs/2112.11487 (2021) - 2020
- [i35]Joshua A. Grochow, Youming Qiao, Gang Tang:
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms. CoRR abs/2012.01085 (2020) - [i34]Yerim Song, Joshua A. Grochow:
An Improved Algorithm for Coarse-Graining Cellular Automata. CoRR abs/2012.12153 (2020) - 2019
- [i33]Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, James B. Wilson:
Incorporating Weisfeiler-Leman into algorithms for group isomorphism. CoRR abs/1905.02518 (2019) - [i32]Joshua A. Grochow, Youming Qiao:
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. CoRR abs/1907.00309 (2019) - 2018
- [i31]Joshua A. Grochow, Jamie Tucker-Foltz:
Computational topology and the Unique Games Conjecture. CoRR abs/1803.06800 (2018) - 2017
- [i30]Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf:
Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR abs/1701.01717 (2017) - [i29]Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay:
Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines. CoRR abs/1706.09667 (2017) - [i28]Joshua A. Grochow, Cristopher Moore:
Designing Strassen's algorithm. CoRR abs/1708.09398 (2017) - [i27]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. CoRR abs/1710.09806 (2017) - [i26]Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans:
Which groups are amenable to proving exponent two for matrix multiplication? CoRR abs/1712.02302 (2017) - [i25]Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i24]Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf:
Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. TR17 (2017) - [i23]Joshua A. Grochow, Cristopher Moore:
Designing Strassen's algorithm. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i22]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 abs/1604.02096 (2016) - [i21]Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao:
Boundaries of VP and VNP. CoRR abs/1605.02815 (2016) - [i20]Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans:
On cap sets and the group-theoretic approach to matrix multiplication. CoRR abs/1605.06702 (2016) - [i19]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 abs/1610.05825 (2016) - [i18]Joshua A. Grochow, Cristopher Moore:
Matrix multiplication algorithms from group orbits. CoRR abs/1612.01527 (2016) - [i17]Joshua A. Grochow:
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. TR16 (2016) - 2015
- [i16]Joshua A. Grochow, Youming Qiao:
Polynomial-time isomorphism test of groups that are tame extensions. CoRR abs/1507.01917 (2015) - [i15]Joshua A. Grochow:
Monotone projection lower bounds from extended formulation lower bounds. CoRR abs/1510.08417 (2015) - [i14]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 abs/1510.08542 (2015) - [i13]Eric Allender, Joshua A. Grochow, Cristopher Moore:
Graph Isomorphism and Circuit Size. CoRR abs/1511.08189 (2015) - [i12]Eric Allender, Joshua A. Grochow, Cristopher Moore:
Graph Isomorphism and Circuit Size. Electron. Colloquium Comput. Complex. TR15 (2015) - [i11]Joshua A. Grochow:
Monotone projection lower bounds from extended formulation lower bounds. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i10]Joshua A. Grochow, Toniann Pitassi:
Circuit complexity, proof complexity, and polynomial identity testing. CoRR abs/1404.3820 (2014) - [i9]David H. Wolpert, Joshua A. Grochow, Eric Libby, Simon DeDeo:
A framework for optimal high-level descriptions in science and engineering - preliminary report. CoRR abs/1409.7403 (2014) - [i8]Joshua A. Grochow, Toniann Pitassi:
Circuit complexity, proof complexity, and polynomial identity testing. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i7]Joshua A. Grochow:
Unifying and generalizing known lower bounds via geometric complexity theory. CoRR abs/1304.6333 (2013) - [i6]Joshua A. Grochow, Youming Qiao:
Algorithms for group isomorphism via group extensions and cohomology. CoRR abs/1309.1776 (2013) - [i5]Joshua A. Grochow, Youming Qiao:
Algorithms for group isomorphism via group extensions and cohomology. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i4]Joshua A. Grochow, Korben Rusek:
Report on "Mathematical Aspects of P vs. NP and its Variants.". CoRR abs/1203.2888 (2012) - 2011
- [i3]Joshua A. Grochow:
Lie algebra conjugacy. CoRR abs/1112.2012 (2011) - [i2]Joshua A. Grochow:
Lie algebra conjugacy. Electron. Colloquium Comput. Complex. TR11 (2011) - 2009
- [i1]Lance Fortnow, Joshua A. Grochow:
Complexity Classes of Equivalence Problems Revisited. CoRR abs/0907.4775 (2009)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:07 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
