Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages

Residual-String Equality, denoted $\mathtt{\text{ResStringEq}}$, is the property consisting of all pairs of strings over $\{0,1,\ast \}$ that are equal after deleting all `$\ast$’ symbols from them. This property was first introduced by Fischer, Magniez, and Starikovskaya (SODA 2018), who used it to show a lower bound on testing the $\mathtt{\text{Dyck}}$ languages, where ${\mathtt{\text{Dyck}}}_m$ is the language consisting of balanced sequences of parentheses over $m$ parenthesis types. They showed that testing $\mathtt{\text{ResStringEq}}$ on inputs of length $n$ requires $\mathrm{\Omega }(n^{1\mathrm{/}5})$ queries, and presented a reduction from testing $\mathtt{\text{ResStringEq}}$ to testing ${\mathtt{\text{Dyck}}}_m$ where $m\ge 2$. Furthermore, they showed that ${\mathtt{\text{Dyck}}}_m$ can be tested with $O(n^{2\mathrm{/}5+\delta })$ queries for every constant proximity parameter, where $\delta >0$ is an arbitrarily small constant. In this work, we nearly close the remaining gap, by showing that testing $\mathtt{\text{ResStringEq}}$, and hence ${\mathtt{\text{Dyck}}}_m$ where $m\ge 2$, requires $\mathrm{\Omega }(n^{2\mathrm{/}5})$ queries. We also show a stronger lower bound of $\mathrm{\Omega }(\sqrt{n})$ for testers that make non-adaptive queries. We establish that the $\mathrm{\Omega }(\sqrt{n})$ bound is nearly tight, by presenting a non-adaptive tester for $\mathtt{\text{ResStringEq}}$ that uses $O(n^{1\mathrm{/}2+\delta })$ queries for an arbitrarily small constant $\delta >0$. Furthermore, we extend this non-adaptive tester to the $\mathtt{\text{Dyck}}$ languages, with the same query complexity. Finally, we improve the dependence on the proximity parameter $\epsilon$ in the tester of Fischer, Magniez, and Starikovskaya, reducing it from $O(1\mathrm{/}\epsilon {)}^{\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(1\mathrm{/}\delta )}$ to $O(1\mathrm{/}\epsilon {)}^{O(\log (1\mathrm{/}\delta ))}$.