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

Abstract

Residual-String Equality, denoted $\texttt{ResStringEq}$, is the property consisting of all pairs of strings over $\{0,1,*\}$ that are equal after deleting all `$*$'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 $\texttt{Dyck}$ languages, where $\texttt{Dyck}_m$ is the language consisting of balanced sequences of parentheses over $m$ parenthesis types. They showed that testing $\texttt{ResStringEq}$ on inputs of length $n$ requires $\Omega(n^{1/5})$ queries, and presented a reduction from testing $\texttt{ResStringEq}$ to testing $\texttt{Dyck}_m$ where $m \geq 2$. Furthermore, they showed that $\texttt{Dyck}_m$ can be tested with $O(n^{2/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 $\texttt{ResStringEq}$, and hence $\texttt{Dyck}_m$ where $m\geq 2$, requires $\Omega(n^{2/5})$ queries. We also show a stronger lower bound of $\Omega(\sqrt{n})$ for testers that make non-adaptive queries. We establish that the $\Omega(\sqrt{n})$ bound is nearly tight, by presenting a non-adaptive tester for $\texttt{ResStringEq}$ that uses $O(n^{1/2+\delta})$ queries for an arbitrarily small constant $\delta>0$. Furthermore, we extend this non-adaptive tester to the $\texttt{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/\epsilon)^{\mathrm{poly}(1/\delta)}$ to $O(1/\epsilon)^{O(\log(1/\delta))}$.