PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hadar Strauss

arXiv:2609.35746v2cs.DS

TL;DR

The paper addresses the query complexity of testing Residual-String Equality and the resulting bounds for Dyck languages. It proves stronger lower bounds, presents nearly matching non-adaptive testers, and improves the testers’ dependence on the proximity parameter.

  • Problem

    The paper studies how many queries are needed to test ResStringEq, a property-testing problem where testers aim to distinguish property members from inputs ϵ-far from the property.

    Source: §1 · p. 3, §1.1 · p. 3

  • Method

    The paper analyzes tester views under input distributions and develops non-adaptive testers for ResStringEq.

    Source: §1.1 · p. 4, The two distributions · p. 6, §4.2 · p. 16

  • Results

    Testing ResStringEq requires Ω(n^2/5) queries; non-adaptive testers require Ω(√n) and can use O(n^1/2+δ) queries.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    The Ω(√n) lower bound and O(n^1/2+δ) tester give nearly matching query bounds for non-adaptive ResStringEq testing.

    Source: §1.1 · p. 4

    One-sided error testers for ResStringEq require Ω(n) queries, a bound that also holds for Dyck languages even for Dyck_1.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

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$ for any $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 gap, by showing that testing $\texttt{ResStringEq}$, and hence $\texttt{Dyck}_m$ (for any $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))}$.

1 Introduction

This work sharpens the query-complexity bounds for testing Residual-String Equality, where two strings are equal after deleting all ‘*’ symbols, and for the Dyck languages. It also gives nearly matching non-adaptive bounds and improves the dependence on the proximity parameter.

1 Introduction

  • ResStringEq tests whether two strings over {0,1,*} are equal after deleting all ‘*’ symbols; property testing permits distinguishing members from inputs ϵ-far from the property.The paper frames query complexity as minimizing how much of the input a tester must access.Source: §1 · p. 3
  • Earlier work established an Ω(n^1/5) lower bound for ResStringEq and an O(n^2/5+δ) upper bound for testing Dyck_m, leaving a gap addressed here.[FMS18] also gave a reduction from ResStringEq testing to Dyck_2 testing.Source: §1 · p. 3

1.1 Our results

  • Testing ResStringEq requires Ω(n^2/5) queries, and testing Dyck_m requires Ω(n^2/5) queries for every m ≥2.Both lower bounds are nearly tight against the O(n^2/5+δ)-query Dyck tester of [FMS18].Source: §1.1 · pp. 3–4
  • Non-adaptive testers for ResStringEq require Ω(√n) queries, while non-adaptive testers using O(n^1/2+δ) queries exist for ResStringEq and Dyck_m.Here δ > 0 can be arbitrarily small, and the testers apply for every constant ϵ > 0.Source: §1.1 · p. 4
  • The adaptive tester's dependence on ϵ improves from O((1/ϵ)^poly(1/δ)) to O((1/ϵ)^O(log(1/δ))): the improved dependence applies to ResStringEq and Dyck testers.The same improved ϵ dependence is obtained for the non-adaptive testers; their query complexity is O((1/ϵ)^O(log(1/δ))·n^1/2+δ).Source: §1.1 · p. 4

1.2 Organization

  • The introduction previews the lower-bound proofs, the non-adaptive tester and its extension to Dyck languages, and the improved ϵ dependence for adaptive testers.The paper places the lower-bound proof in Section 4, the ResStringEq tester in Section 5, and the Dyck extension in Section 6.Source: §1.2 · p. 5

2 Technical overview

This technical overview develops the lower-bound analysis for ResStringEq, using indistinguishability between YES and NO input distributions and a modified construction aimed at an Ω(n²ᐟ⁵) bound. It also outlines block-based and rank-segment constructions for testers, including recursive non-adaptive and adaptive approaches.

2.1 The lower bound

  • The proof compares YES inputs in ResStringEq with NO inputs far from the property, showing that testers using o(n2/5) queries cannot distinguish the distributions.The approach builds on [FMS18] and, with a tighter analysis of essentially the same construction first yielding Ω(n1/4).Source: §2.1 · p. 5

The two distributions.

  • YES and NO pairs use independently chosen star locations and shared bits at matching ranks, except that NO pairs use independent bits on the middle third of ranks.The overview describes exactly n/2 star positions in each string.Source: The two distributions · pp. 5–6

The non-adaptive case.

  • The non-adaptive analysis establishes an Ω(n1/4) lower bound by bounding the chance that queries hit interior matching positions.It uses a union bound over pairs of queried positions.Source: The non-adaptive case · pp. 6–7

The adaptive case.

  • Adaptive queries can exploit previously found matches because nearby positions are more likely to match, with that probability decreasing as distance grows.For positions on the same side of a known matching pair, matching depends on equal counts of non-star positions between them.Source: The adaptive case · p. 7
  • The adaptive analysis partitions progress intervals using τ to separate queried positions with unqueried positions, controls total progress, and establishes an Ω(n1/4) lower bound.The general analysis also handles queries to either half of the first string, non-monotone query depths, and interspersed queries to both strings.Source: The adaptive case · pp. 9–10

2.1.2 Improving the lower bound to Ω(n2/5)

  • The construction is modified to obtain an Ω(n2/5) lower bound, beyond the Ω(n1/4) bound from the initial analysis.The overview says the modification is necessary because the initial distributions can be distinguished with eO(n1/4) queries.Source: §2.1 · p. 5, §2.1.2 · p. 10
  • Uniformly choosing each block’s non-star count spreads star counts and reduces interior-rank concentration, supporting the desired Ω(n^2/5) adaptive lower bound.The construction makes the block count uniform over {0, 1, ..., b}, making interior matching positions harder to find.Source: §2.1.2 · pp. 10–11

2.2 A non-adaptive tester

  • Rank estimates partition inputs into rank-segments; sampling fixed overlapping blocks makes the basic tester non-adaptive, with eO(n^4/5) queries versus eO(n^2/3) adaptively.The adaptive warm-up queries selected segments directly, while the non-adaptive version samples covering blocks in advance.Source: §2.2 · pp. 12–13
  • Replacing full rank-segment reads with recursion yields an adaptive ResStringEq tester using O(n^2/5+δ) queries for constant ε.Balancing rank-estimation cost with recursive checks on sampled segment pairs uses L = n^4/5.Source: §2.2 · p. 14

3 Preliminaries

Property testing relaxes exact membership into a randomized distinction between members and inputs far from the property. The preliminaries define statistical distance and describe a boundary-slack choice in the tester’s implementation.

3 Preliminaries

  • A tester must accept property members with probability at least 2/3 and reject inputs that are epsilon-far with probability at least 2/3, while query complexity bounds its queries.Epsilon-farness means differing from every property member on more than an epsilon fraction of positions.Source: §3 · p. 14
  • Statistical distance is the maximum distinguishing-probability gap over Boolean tests, expressed as the sum of absolute probability differences.The displayed definition begins with a sum over outcomes and equates it to the maximum over Boolean functions.Source: §3 · p. 14
  • The implementation uses the all-offset procedure from the first round, so it accepts residual strings that match up to boundary slack 0.1·epsilon·n.This differs from treating the first recursive round separately.Source: §3 · p. 14

4 Lower bound

The section proves Ω(n^{2/5}) and non-adaptive Ω(√n) query lower bounds for ResStringEq using indistinguishability arguments over YES and NO input distributions. It bounds testers’ chances of observing matching ranks, controlling new-query matches under a no-match condition.

4.1 The two distributions

  • The NO pair is ε-far from ResStringEq with probability at least 1 − o(1), while its middle-third rank bits are independent across strings.The YES pair instead shares bits at each rank; the far-pair claim is implicit in [FMS18, Lem. 5.4] and also appears in [PRR03, Lem. 14].Source: §4.1 · pp. 15–16

4.2 The non-adaptive case

  • Unless a non-adaptive tester makes Ω(√n) queries, its views on the YES and NO distributions are indistinguishable, establishing the lower bound.Conditioned on querying no interior matching positions, the two views are identically distributed; the proof bounds the probability of querying such a match.Source: §4.2 · p. 16

4.3 The adaptive case

  • For an arbitrary possibly adaptive tester, unless its query complexity q is Ω(n^(2/5)), its views A and ˜A are indistinguishable, establishing Theorem 1.2.Source: §4.3 · p. 17

4.3.1 Proof of Lemma 4.7

  • The adaptive proof measures progress by the deepest matching queried positions and uses good-depth cuts to bound accumulated progress when b ≥ C·q^3/2.The depth-progress analysis supports the bound on the probability of querying interior matching positions.Source: §4.3 · p. 17, §4.3.1 · pp. 18–19
  • Under E2, changing the remaining block variables preserves the joint distribution of observed non-star bits because queries in I have no matching second-string query.Rank changes inside I can affect whether positions share a rank, but E2 makes the corresponding bits uniform and independent of the second-string answers and other first-string answers.Source: §4.3.1 · p. 21
  • A good depth provides Ω(p) unqueried depths for bounding new-query matches and earlier-query matches; the proof obtains the desired bound when b ≥ C·q^(3/2).The proof uses a union bound over possible matches and Fact 4.12 for the new-query event; the condition on b is used in bounding the complement of E2.Source: §4.3.1 · pp. 22–23
  • For a second-string query, the proof repeats the argument with the roles of the new query and a matching prior first-string query exchanged, adding a union bound over prior queries.When the event P′_k ≥ p holds, some previous first-string query matches the new second-string query.Source: §4.3.1 · p. 23

5 A non-adaptive tester for ResStringEq

The section presents a recursive non-adaptive tester for ResStringEq. For every constant delta greater than zero, its query complexity is O((1/epsilon)^(O(log(1/delta))) · n^(1/2+delta)).

5 A non-adaptive tester for ResStringEq

  • O((1/epsilon)^(O(log(1/delta))) · n^(1/2+delta)) queries suffice for a non-adaptive ResStringEq tester for every constant delta > 0.This is the stated query complexity of Theorem 5.1.Source: §5 · p. 23
  • The final tester is recursive and achieves the stated O(n^(1/2+delta)) query bound, with the theorem giving its epsilon dependence.The section overview distinguishes this tester from the earlier warm-up procedures.Source: §5 · p. 23
  • The warm-up gives an adaptive eO(n^(2/3))-query tester and a non-adaptive eO(n^(4/5))-query variant for constant epsilon.Making the warm-up tester non-adaptive increases its query complexity.Source: §5 · p. 23

5.1 A warm-up

The warm-up develops an adaptive rank-segment tester and then a block-sampling modification that makes the basic approach non-adaptive. Its correctness relies on accurate rank estimates and detecting bad pairs of corresponding segments.

5.1.1 A basic adaptive tester

  • The basic adaptive tester uses rank estimates to select corresponding short segments, checks their residual strings up to boundary slack, and uses eO(n2/3) queries.It repeats random segment-pair checks O(1/ϵ) times.Source: §5.1.1 · pp. 23–24

5.1.2 Correctness

  • For ϵ-far inputs, at least Ω(ϵn/L) segment pairs are bad, giving each iteration Ω(ϵ) rejection probability; all rank estimates succeed with probability at least 0.99.For equal residual strings, successful estimates keep corresponding segment ranks within 2∆, so all checks pass.Source: §5.1.2 · pp. 24–25

5.1.3 Making the basic tester non-adaptive

  • The non-adaptive modification presamples fixed blocks so short rank-segments can be checked without queries depending on rank estimates, but its basic tester uses eO(n4/5/ϵ6/5) queries.Blocks are chosen so every short rank-segment is contained in a block.Source: §5.1.3 · pp. 26–27

Correctness.

  • For ϵ-far inputs with successful estimates and no earlier rejection, with probability at least 0.99 some bad pair has both segments contained in sampled blocks.The sampled blocks let the tester check that pair non-adaptively.Source: Correctness · p. 27

5.2 The actual non-adaptive tester

This section presents a recursive non-adaptive tester for ResStringEq with near-square-root query complexity, accepting strings that match up to boundary slack and rejecting pairs that are ϵ-far from equality. Its correctness analysis shows that the Decision procedure’s recursive soundness ensures rejection when the estimates succeed and the tester reaches the procedure.

5.2 The actual non-adaptive tester

  • The tester separates non-adaptive query collection from recursive decisions, comparing corresponding rank-segments across offsets and accepting when all recursive checks pass.It accepts when residual strings match up to boundary slack 0.1 · ϵ · n, and rejects when more than ϵ · n modifications are required.Source: §5.2 · pp. 27–30

5.2.1 Query complexity

  • O((1/ϵ)^O(log(1/δ)) · n^(1/2+δ)) queries suffice for every constant δ > 0.The bound follows by choosing the recursion depth r = O(log(1/δ)).Source: §5.2.1 · p. 30

5.2.2 Correctness

  • With successful estimates, the tester accepts boundary-slack matches with probability at least 2/3, while all estimates succeed simultaneously with probability at least 1−η/2.The Decision procedure’s stated guarantees are acceptance with probability at least 1−η for boundary-slack matches and rejection with probability at least 1−η for pairs requiring more than ϵ · n modifications.Source: §5.2 · p. 29, §5.2.2 · pp. 30–31
  • For every ordering and offset, successful estimates imply Ω(ϵ · n/L) bad rank-segment pairs, and a bad pair is contained in sampled blocks with probability at least 1−η/(2N).This provides the sampled-block witness used in the soundness analysis.Source: §5.2.2 · pp. 31–32
  • The Decision procedure falsely accepts with probability at most η/2, by bounding each iteration’s error by η/N and applying a union bound.Successful estimates make recursive-call promises hold; the estimates themselves are unsuccessful with probability at most η/2.Source: §5.2.2 · p. 33

5.3 On the adaptive tester for ResStringEq

Composing the basic adaptive tester with the recursive non-adaptive tester gives an adaptive tester for ResStringEq. It achieves O(n2/5+δ) query complexity while improving the dependence on ϵ over the earlier approach.

5.3 On the adaptive tester for ResStringEq

  • O((1/ϵ)^O(log(1/δ)) · n2/5+δ) queries suffice for an adaptive ResStringEq tester, improving the earlier dependence on ϵ from (1/ϵ)^O(poly(1/δ)).The construction composes the basic adaptive tester with the recursive non-adaptive tester.Source: §5.3 · p. 33

6 Extending the non-adaptive tester to the Dyck languages

This section extends the testing approach to Dyck languages, presenting a recursive tester with query-complexity and correctness guarantees and an adaptive tester using an improved excess-parentheses matching procedure to improve dependence on ε.

6 Extending the non-adaptive tester to the Dyck languages

  • O((1/ϵ)^O(log(1/δ)) · n^1/2+δ) queries suffice to non-adaptively test Dyck_m for every m and arbitrarily small constant δ > 0.Source: §6 · p. 34

6.1 Preliminaries

  • Testing Dyck_m reduces to testing Dyck_m-consistency with O(q + ϵ^-2 · log(1/ϵ)) queries, preserving non-adaptivity; its matching graph is planar with at most 3n/b edges.Approximate excess numbers yield matching-graph edge-weight estimates within 2∆.Source: §6.1 · pp. 34–35

6.2 The excess parentheses matching procedure

  • When |e0(s) − e1(s′)| ≤ 0.2·ϵ·n and n = Ω(ϵ·N), the matching procedure accepts matches with slack 0.1·ϵ·n with probability at least 1−η.If it accepts with probability greater than η, a non-crossing matching exists with matching types, an even number of intervening parentheses per pair, and at most ϵ·n unmatched excess parentheses.Source: §6.2 · pp. 38–39

6.3 The tester

  • The Dyck_m-consistency tester uses recursive non-adaptive queries, initialized with three rounds and failure parameter 1/3, alongside sampling, blocks, excess estimates, and approximate matching intervals.The algorithm invokes the Query procedure with O(log(1/δ)) rounds on selected blocks.Source: §6.3 · p. 39
  • The tester runs excess parentheses matching on sampled block pairs and recursively tests O(ε^-1 · log(1/η)) uniformly sampled blocks, accepting only if all checks accept.For a selected pair, it invokes the matching procedure when both blocks were selected and the approximate matching intervals meet the stated size threshold.Source: §6.3 · p. 40

6.3.1 Query complexity

  • After three recursive rounds, Algorithm 6.10 has expected query complexity O((1/ε)^O(log(1/δ)) · n^(1/2+δ)).Each round makes O(ε^-1 · log(1/η)) recursive calls on blocks of length n^(3/4), while the proximity parameter stays Ω(ε) and the failure parameter stays 1/poly(n).Source: §6.3.1 · p. 40

6.3.2 Correctness

  • If Algorithm 6.10 accepts x with probability greater than η, Claim 6.11 guarantees a non-crossing matching of locally excess parentheses with at most 0.1 · ε · n unmatched.The matched parentheses have the same type and an even number of parentheses between them; the proof bounds bad pairs by ε′ · n/b and the total unmatched locally excess parentheses by O(ε′ · n).Source: §6.3.2 · pp. 40–42

6.4 On the adaptive tester for the Dyck languages

  • For every m ∈ N and any arbitrarily small constant δ > 0, there exists an adaptive tester for Dyck_m with query complexity O((1/ε)^O(log(1/δ)) · n^(2/5+δ)).Source: §6.4 · p. 42

A A reduction to the equal-length case in ResStringEq

Unequal-length inputs to ResStringEq can be reduced to the equal-length case by padding the shorter string with star symbols. This preserves membership and converts an ε-far pair into an ε/2-far pair.

A reduction to the equal-length case in ResStringEq

B Proof of Fact 4.6

The section proves Fact 4.6, which generalizes Fact 4.2. If two event-restricted distributions agree pointwise, their event probabilities agree and their total variation distance is bounded by that probability.

Proof of Fact 4.6

  • Fact 4.6 generalizes Fact 4.2 and assumes pointwise equality of the event-restricted probabilities for two discrete random variables.Source: B Proof of Fact 4.6 · p. 44
  • Equal event-restricted probabilities at every domain value imply that the two events have equal probabilities.Source: B Proof of Fact 4.6 · p. 44
  • The total variation distance between the random variables is at most the probability of either event, using the triangle inequality.The two event probabilities are equal.Source: B Proof of Fact 4.6 · p. 44
Loading 2609.35746v2…