Tolerant Testing of Regular Languages in Sublinear Time

A classic problem in property testing is to test whether a binary input word 𝑤 is in regular language 𝐿. Such testers distinguish the case that 𝑤 is in 𝐿 from the case where 𝑤 is 𝜖-far from 𝐿 (𝜖-far means that at least 𝜖 fraction of the bits in 𝑤 must be modified to change 𝑤 into a word in 𝐿. Otherwise, 𝑤 is 𝜖-close). When it is known that 𝑤 is noisy, it can be useful to provide tolerant testers: algorithms that accept when 𝑤 is 𝛿-close and reject when 𝑤 is 𝜖-far, for 𝛿 < 𝜖. We build on the work of Alon, Krivelevich, Newman and Szegedy [1] to provide a tolerant, constant time property tester for regular languages. Our main result is that given a regular language 𝐿 ∈ {0, 1} * and an integer 𝑛, there exists a randomized algorithm which accepts a word 𝑤 of length 𝑛 if it is 𝛿-close (𝛿 < 𝜖) to a word in 𝐿 and rejects with high probability if 𝑤 is 𝜖-far from a word in 𝐿. The algorithm queries polynomial in 1 𝜖 bits in 𝑤.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Gong, Linda

Advisor dc:contributor.advisor

• Rubinfeld, Ronitt

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139249

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139249