Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

Pushkar S. Joglekar; V. Arvind

REVIEW

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

V. Arvind, Pushkar S. Joglekar

Computational Complexity · Submitted 29 Sep 2026

Pith's verdict: The internal proofs are careful and the entry oracle is a genuine new step; the whole result stands on one unvetted black box, the CGGRT26 uniformity claim, and the referee's real job is checking that box, not the paper's own math.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 30, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.37319 (version 2)

Pith ID63X6H77K, Pith's permanent record of this paper and its review

CitationPushkar S. Joglekar, V. Arvind. "Rational Identity Testing for Noncommutative Circuits is in Polynomial Space." arXiv:2609.37319 (2026). https://pith.science/paper/63X6H77K

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper's own mathematics is the strong part, and I want that said first. The genuinely new piece is the entry oracle in Lemma 4.9: the Hrubes–Wigderson pencil of a rational circuit — not just a formula — is succinctly presentable, each entry computable in O(s^2) space. The clause analysis is detailed and I could not find a hole in it. The other two legs are also handled honestly: the folklore simulation in Theorem 2.5 is stated with exact hypotheses and proved rather than gestured at, and Remark 4.7 is a point in the authors' favor — they explicitly flag that the unconditional biconditional about inversion gadgets is false. That is the behavior of people who understand their own reduction. Lemma 5.1 homogenization is terse but it is a standard rank-preservation fact, not where this result can break. The soft spot is precisely where the reader and stress-test put it: the entire PSPACE bound is a direct lift of CGGRT26, an ECCC report from July 2026 that has not been through peer review. The paper states twice that the ncFull algorithm is logspace-uniform NC — but asserting it is not establishing it, and the make-or-break property really is the uniformity space, not the depth. Corollary 2.6 needs u(M) = O(log M); if the true uniformity is only P-uniform, the u(M) term blows the workspace to 2^(Ω(s)) and the PSPACE conclusion fails outright. I also agree the composed reduction from the paper's formal pencils (variables occurring once, in distinct positions) to the CGGRT26 instance, and the logspace-uniformity of that composition, is asserted rather than shown. That is the one place a referee must dig. It is not the authors' fault that their black box is recent and unvetted, but they have a verification obligation they have not discharged. If the CGGRT26 uniformity claim checks out, this is a clean resolution of an open gap — RIT for circuits dropping from EXPSPACE to PSPACE, with the entry oracle as a reusable technique. My recommendation: send it to peer review, seriously. The referee's primary job is to read CGGRT26 TR26-100 and confirm (a) the uniformity is genuinely logspace, and (b) the formal-pencil instances lie inside ncFull with a logspace reduction. The paper's own proofs deserve to be refereed with that question settled first.

Referee report

Significance

If Theorem 5.3 is sound with the asserted uniformity, this is a genuine advance: it replaces the EXPSPACE bound the paper attributes to previous methods for rational circuits and transfers to degree-unrestricted noncommutative PIT (Corollary 6.3). The manuscript's own contributions are concrete and mostly checkable: the entry-oracle construction (Lemma 4.9) is a real succinct-presentation result with O(s^2) workspace; the simulation theorem (Theorem 2.5) supplies exactly the hypotheses a space-bounded reduction needs; Proposition 6.1's induction correctly maintains the promise of the zero-tester on subcircuits; and Remark 4.7 honestly records a false unconditional biconditional that a less careful paper would have used. The conditional framing ('Assume Theorem 5.3') is also to the authors' credit. The significance is, however, hostage to the external black box: the workspace exponent and indeed the PSPACE conclusion itself inherit the uniformity space and depth of an unvetted technical report, and the load-bearing uniformity clause is asserted rather than demonstrated.

Major objections (3)

[5 (Theorem 5.3) and 6 (Theorem 6.2)] The PSPACE conclusion of Theorem 6.2 is a direct lift of the two parameters attributed to [CGGRT26]: Corollary 2.6 turns depth O(log^2 M) into the O(s^2) workspace term, and the same corollary needs the uniformity space u(M) = O(log M). The manuscript asserts the uniformity clause twice — abstract bullet 2 ('their algorithm is logspace-uniform NC') and Theorem 5.3 ('uniformity space O(log M)') — but neither proves it nor quotes the part of the cited report that contains it, and the cited report is a July 2026 ECCC technical report whose title concerns bipartite matching, with the chain to ncFull not reproduced in the present paper. This is load-bearing: if the direct-connection procedure of that algorithm were only P-uniform, u(M) would be up to poly(M) = 2^{Ω(s)} and the workspace bound of Theorem 2.5 would blow up, destroying the PSPACE claim; if the depth were O(log^3 M) rather than O(log^2 M), PSPACE would survive but the O(s^2) headline would become O(s^3). I ask the authors to state precisely which statement in [CGGRT26] supplies each clause of Theorem 5.3 (size M^{O(1)}, depth O(log^2 M), uniformity space O(log M)), to verify that the reduction from the present paper's pencil format to the setting of that report preserves those parameters, or to prove the uniformity claim themselves; I also suggest separating the robust statement (uniform NC^i with polylogarithmic uniformity for any constant i suffices for PSPACE) from the O(s^2) headline so that the bound degrades gracefully if the depth exponent differs.
[6 (proof of Theorem 6.2), 4.3 (Lemma 4.9)] Corollary 2.6 requires a bit oracle that returns individual bits of the length-M input, whereas Lemma 4.9 returns whole entries (Q_k)_{i,j}, each an integer of bit-size at most s. The proof of Theorem 6.2 skips the conversion between the two: it should fix the ncFull encoding of Definition 5.2 (self-delimiting header; (n+1)N^2 entries of width w = O(s) bits), give the decoding of a query position t in [M] into (k, i, j, bit offset), and account for the workspace of that decoding, which should be σ = O(s^2) plus O(log s). As printed, the O(s^2) workspace claim depends on an unstated composition, so the bound is not checkable exactly where it matters.
[5 (Lemma 5.1)] The proof of the homogenization lemma is compressed into one sentence and omits the two standard facts on which the reverse inequality rests: for a generic tuple of d×d matrices (X_0,...,X_n) the rank of Q_0⊗X_0 + Σ_k Q_k⊗X_k equals d·nc-rank(L^h), and for every tuple Y_k the rank of the blow-up Q_0⊗I_d + Σ_k Q_k⊗Y_k is at most d·nc-rank(L). The printed implication '... is equal to r·d implying nc-rank(L) ≥ nc-rank(L^h)' needs the second fact as an upper bound on the blow-up of the affine pencil and also needs X_0 to be generically invertible. Please expand the proof, state the 'suitably large dimension' quantifier, and address the finite-field case explicitly, since Remark 6.4 claims the finite-field extension holds 'without any changes in the proofs'.

Minor objections (6)

[4.2 (Lemma 4.4(d))] The stated bound p(F) ≤ 3·2^{depth(F)−1} contradicts the proof in the same sentence, which derives 3·2^d − 1, and also contradicts the following line's p(F_v) ≤ 3·2^{s−1}−1; the −1 belongs outside the exponent.
[4.3 (Lemma 4.9)] The output clause for an atom labelled by a variable x_ℓ says it answers 1 if k=ℓ and 0 otherwise, which covers k=0 only implicitly; the scalar-output and variable-output cases should be restated so the k=0 (scalar part) behaviour is explicit.
[6 (proof of Theorem 6.2)] The homogenization step is implicit in the sentence 'simulate the NC algorithm of Theorem 5.3 on the succinct input L', since ncFull is defined for homogeneous pencils; the instance should be stated as the homogenized tuple (Q_0, Q_1, ..., Q_n) via Lemma 5.1.
[5 (Lemma 5.1)] Lemma 5.1 assumes n ≥ 1; the edge case of a circuit with no variables (n = 0) is not discussed anywhere, though it is trivially handled by treating the constant matrix directly or by adding a dummy variable with zero coefficients.
[References] The bibliography contains entries that are never cited in the text — [HS80], [BCP83], [Mul87], [Nis93], [KI04], [ACGMR23], [DM17], [FR04] — and [DM17] and [FR04] would be natural citations for the blow-up facts used in Lemma 5.1; the authors should cite or delete them.
[Abstract] The abstract contains the typo 'inputrational circuit' (missing space).

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Rational identity testing for noncommutative circuits is decidable in deterministic space $O(s^2)$, and hence lies in PSPACE.

The reading

The paper claims that rational identity testing (RIT) for noncommutative arithmetic circuits with inversion gates — deciding whether a circuit computes the zero element of the free skew field, and, if not, whether some inversion gate divides by zero — is decidable in deterministic workspace $O(s^2)$, and hence lies in PSPACE. The previous upper bound for circuits was exponential time and space, because a circuit of size $s$ unrolls into a formula whose Hrubes–Wigderson pencil has dimension $2^{O(s)}$. The proof never writes that pencil down: it provides an entry oracle returning any requested entry in space $O(s^2)$, then runs a folklore polylogarithmic-space simulation of a uniform $\mathrm{NC}^2$ algorithm for full noncommutative rank against this succinct input. If the argument holds, degree-unrestricted noncommutative polynomial identity testing is also in PSPACE, over $\mathbb{Q}$ and over finite fields.

What carries the argument

The central object is the Hrubes–Wigderson syntactic pencil $A_F$ and its wrapper $L(F) = A_{F^{-1}}$, a matrix over the free associative algebra whose dimension satisfies $p(F) \le 2|F|$ and whose entries are single symbols — scalars in $\{0,\pm 1\}$, variables, or constants of bit-size at most $s$ (Lemma 4.4). The load-bearing identity is Lemma 4.5: for a correct formula $F$, $(A_F^{-1})_{1,p(F)} = \widehat F$, so the value of the formula is a single entry of the pencil's inverse, and Theorem 4.8 makes $\widehat F = 0$ equivalent to non-fullness of $L(F)$. The carrying mechanism is the entry oracle (Lemma 4.9), which answers any query $(k,i,j)$ for $(Q_k)_{i,j}$ in workspace $O(s^2)$ and time $\mathrm{poly}(s)$ by descending through the circuit once, never duplicating the exponential matrix; coupled with Corollary 2.6 this converts a uniform $\mathrm{NC}^i$ rank decision on a $2^{\Theta(s)}$-bit input presented by a polynomial-space oracle into a deterministic $O(s^i)$-space procedure.

Extended reading notes

Core claim

On the paper's own terms: RIT for rational circuits, with no correctness promise on the input, lies in PSPACE. The mechanism is a three-part assembly. First, the Hrubes–Wigderson linearization of a rational formula is extended to circuits by unrolling, so that each gate's subcircuit becomes a formula of at most $2^s$ nodes and hence a pencil of dimension $2^{O(s)}$; the entry oracle (Lemma 4.9) computes any single entry of this pencil in workspace $O(s^2)$ without materializing the matrix. Second, a recent theorem — that deciding whether a homogeneous symbolic matrix has full noncommutative rank is in logspace-uniform $\mathrm{NC}^2$ — is used as a black box for the rank test. Third, the succinct-simulation theorem (Theorem 2.5 and Corollary 2.6) shows that a uniform $\mathrm{NC}^i$ procedure run against an input of length $2^{\Theta(s)}$ presented by a polylogspace bit oracle takes workspace $O(s^i)$. The zero criterion (Theorem 4.8) ties the value question on a correct formula $F$ to fullness of the wrapper pencil $L(F) = A_{F^{-1}}$: $\widehat F = 0$ if and only if $L(F)$ is not full, so identity testing becomes a rank test on a succinctly presented pencil. The main theorem (Theorem 6.2) states the decision procedure for correctness, returning an offending inversion gate when one exists, and for identity, and Remark 6.4 extends the statement to finite fields.

Load-bearing premise

The PSPACE bound hinges on the externally cited result that deciding full noncommutative rank of a homogeneous symbolic matrix lies in logspace-uniform $NC^{2}$, including its asserted uniformity, which the paper does not re-derive and whose depth sets the space exponent.

Editorial extensions

If this is right

Degree-unrestricted noncommutative polynomial identity testing for circuits without inversion gates is in PSPACE (Corollary 6.3).
The decision procedure is constructive about failure: if the circuit is incorrect, it outputs the label of an inversion gate whose argument evaluates to zero, with no promise on the input needed (Theorem 6.2(a)).
The same PSPACE bound and proof hold over any finite field, with no modification (Remark 6.4).
The exponential unrolling of a circuit to a formula is absorbed by the succinct presentation, so the exponential cost appears only as a polynomial factor in the space exponent rather than as an exponential blow-up in workspace.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The PSPACE containment is only as clean as the external rank theorem: if the asserted logspace-uniform $\mathrm{NC}^2$ membership for full noncommutative rank (the paper's only black box) fails, the whole bound falls, since Corollary 2.6 sets the space exponent $O(s^i)$ from the NC depth.
The succinct-pencil-plus-uniform-NC template suggests a route to PSPACE for other algebraic problems whose natural instances are exponentially large but locally computable — the entry-oracle idea is not specific to identity testing.
Pushing the space bound below $O(s^2)$ would require a fully uniform $\mathrm{NC}^1$ rank test, which the cited tools do not provide; the paper leaves that as an open direction.
A practical check of the construction: run the entry oracle against the explicit wrapper pencil of Example 4.3, where $F = x_1 x_2$, and confirm the fullness classification matches $\widehat F \neq 0$; any mismatch would trace to Lemmas 4.5–4.9 rather than to the black box.

Original abstract

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space. We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE. As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE. The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction. By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC. We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$. Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{\Theta(s)}$ yields a polynomial space algorithm.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-30: 1 request, 9,179 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.21 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.93 · compares with prior results 0.96 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space. We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE. As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE. The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction. By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC. We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$. Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{\Theta(s)}$ yields a polynomial space algorithm.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field.	background 1.00	0.06	0.02	asserted 0.98
s1	For rational \emph{formulas} the problem is known to be in deterministic polynomial time.	background 1.00	0.03	0.01	asserted 1.00
s2	For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space.	background 0.81	0.07	0.02	asserted 1.00
s3	We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE.	result 0.88	0.95	0.92	asserted 1.00
s4	As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE.	interpretation 0.51	0.82	0.20	asserted 1.00
s5	The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$.	method 0.80	0.78	0.04	asserted 0.99
s6	More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$.	method 0.78	0.84	0.02	asserted 1.00
s7	This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction.	interpretation 0.48	0.82	0.03	asserted 0.96
s8	By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC.	background 0.67	0.03	0.03	asserted 1.00
s9	We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$.	method 0.95	0.54	0.03	asserted 0.99
s10	Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space.	method 0.53	0.16	0.02	asserted 1.00
s11	Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{\Theta(s)}$ yields a polynomial space algorithm.	interpretation 0.40	0.45	0.12	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 0.98.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.