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
-
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.
-
Absent Subsequences in Words
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.