Zobrazeno 1 - 10
of 141
pro vyhledávání: '"Grochow, Joshua A."'
We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for groups and quasigroups (=Latin squares), given as input in terms of their m
Externí odkaz:
http://arxiv.org/abs/2402.00133
Autor:
Wolpert, David, Korbel, Jan, Lynn, Christopher, Tasnim, Farita, Grochow, Joshua, Kardeş, Gülce, Aimone, James, Balasubramanian, Vijay, de Giuli, Eric, Doty, David, Freitas, Nahuel, Marsili, Matteo, Ouldridge, Thomas E., Richa, Andrea, Riechers, Paul, Roldán, Édgar, Rubenstein, Brenda, Toroczkai, Zoltan, Paradiso, Joseph
The relationship between the thermodynamic and computational characteristics of dynamical physical systems has been a major theoretical interest since at least the 19th century, and has been of increasing practical importance as the energetic cost of
Externí odkaz:
http://arxiv.org/abs/2311.17166
Autor:
Grochow, Joshua A., Levet, Michael
Publikováno v:
EPTCS 390, 2023, pp. 185-202
In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fraisse bijective pebble game in Hella's (Ann. Pure Appl. Log., 1989) hierarchy. This is a Spoiler-Duplicator game in which
Externí odkaz:
http://arxiv.org/abs/2310.01007
Autor:
Grochow, Joshua A., Qiao, Youming
Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introduction of the complexity class TI (Grochow & Qiao, ITCS '21; SIAM J. Co
Externí odkaz:
http://arxiv.org/abs/2306.16317
We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. Such problems arise naturally in statistical data analysis and quantum informa
Externí odkaz:
http://arxiv.org/abs/2306.03135
Autor:
Grochow, Joshua A.
The Ideal Proof System (IPS) of Grochow & Pitassi (FOCS 2014, J. ACM, 2018) is an algebraic proof system that uses algebraic circuits to refute the solvability of unsatisfiable systems of polynomial equations. One potential drawback of IPS is that ve
Externí odkaz:
http://arxiv.org/abs/2306.02184
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or r
Externí odkaz:
http://arxiv.org/abs/2305.19320
Autor:
Grochow, Joshua A.
There is no single canonical polynomial-time version of the Axiom of Choice (AC); several statements of AC that are equivalent in Zermelo-Fraenkel (ZF) set theory are already inequivalent from a constructive point of view, and are similarly inequival
Externí odkaz:
http://arxiv.org/abs/2301.07123
Autor:
Grochow, Joshua A., Levet, Michael
In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fra\"iss\'e bijective pebble game in Hella's (Ann. Pure Appl. Log., 1989) heirarchy. This is a Spoiler-Duplicator game in wh
Externí odkaz:
http://arxiv.org/abs/2209.13725
We report our experiences implementing standards-based grading at scale in an Algorithms course, which serves as the terminal required CS Theory course in our department's undergraduate curriculum. The course had 200-400 students, taught by two instr
Externí odkaz:
http://arxiv.org/abs/2204.12046