Symmetric MOD_m circuits require subexponential size to compute n-ary AND, with the bound matched by known depth-2 constructions.
Efficiently Testing Simon’s Congruence
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
verdicts
UNVERDICTED 5representative citing papers
New constructions intersect k NFAs in O(m n^{k-1}) transitions for fixed alphabet, enabling faster emptiness algorithms that are optimal unless (k+1)-clique detection admits a combinatorial breakthrough.
Decidability of the Orbit Problem for logarithmic-dimensional target subspaces and Skolem-hardness for linear-dimensional targets.
The paper proves feasibility of quantum domain decomposition preconditioning for FEM Poisson problems with the two-level Additive Schwarz method, supplies block-encoding bounds, derives quantum solver complexity, and details a BPX local solver choice.
The paper introduces minimal and shortest absent subsequences, gives combinatorial characterizations with compact representations, and provides efficient algorithms to test membership and compute the lexicographically smallest ones along with a query data structure.
citing papers explorer
-
Optimal Lower Bounds for Symmetric Modular Circuits
Symmetric MOD_m circuits require subexponential size to compute n-ary AND, with the bound matched by known depth-2 constructions.
-
Intersecting Dense Automata
New constructions intersect k NFAs in O(m n^{k-1}) transitions for fixed alphabet, enabling faster emptiness algorithms that are optimal unless (k+1)-clique detection admits a combinatorial breakthrough.
-
On the Subspace Orbit Problem and the Simultaneous Skolem Problem
Decidability of the Orbit Problem for logarithmic-dimensional target subspaces and Skolem-hardness for linear-dimensional targets.
-
Quantum Domain Decomposition for Preconditioning the Finite Element Method
The paper proves feasibility of quantum domain decomposition preconditioning for FEM Poisson problems with the two-level Additive Schwarz method, supplies block-encoding bounds, derives quantum solver complexity, and details a BPX local solver choice.