arXiv preprint ·
Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $Ω(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+δ})$ queries for every constant proximity parameter, where $δ>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 $Ω(n^{2/5})$ queries. We also show a stronger lower bound of $Ω(\sqrt{n})$ for testers that make non-adaptive queries. We establish that the $Ω(\sqrt{n})$ bound is nearly tight, by presenting a non-adaptive tester for $\texttt{ResStringEq}$ that uses $O(n^{1/2+δ})$ queries for an arbitrarily small constant $δ>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 $ε$ in the tester of Fischer, Magniez, and Starikovskaya, reducing it from $O(1/ε)^{\mathrm{poly}(1/δ)}$ to $O(1/ε)^{O(\log(1/δ))}$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Online Stochastic Allocation with Increasing Returns
On Extensions of the Unanimous Vote Problem
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.