Answers are grounded in this paper and cite their sources.
Theoretical analysis demonstrates exponential complexity for determinant-symmetric arithmetic circuits, indicating that polynomial-size circuits require logarithmic unanchored variables.
Symmetric arithmetic circuits require specified symmetries of the input variables to extend to automorphisms of the computation. For the determinant, polynomial-size symmetric circuits are known under simultaneous row and column permutations, whereas exponential lower bounds are known when even row and column permutations act independently. This preprint studies the natural determinant-preserving variable-permutation group generated by independent row and column permutations of equal parity together with transposition. Over fields of characteristic zero, we construct a homogeneous skew symmetric arithmetic circuit based on oriented minors. Its size is O(n^2 binom(2n,n)) = O(n^(3/2) 4^n). Combined with the known 2Omega(n) lower bound for the alternating row-column subgroup, this determines the size of fully determinant-symmetric arithmetic circuits as 2Theta(n) on the exponential scale. We then introduce the independent alternating residual rank of a partially anchored symmetry group and derive a lower bound exponential in this residual rank. For the balanced point-anchor model with q unanchored rows and q unanchored columns in an N x N matrix, we prove 2Omega(q) <= s_F(N,q)<= NO(1) q^2 binom(2q,q)<= NO(1) 4^q. Consequently, polynomial-size residual-symmetric circuits exist exactly when q = O(log N). The results apply to symmetry-constrained arithmetic circuits over fields of characteristic zero in the circuit model stated in the manuscript. They do not imply lower bounds for unrestricted arithmetic circuits and do not resolve VP versus VNP or P versus NP.
No takes yet. Share an insight, caveat, or question.
Oliver Tuma (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: