The Space Complexity of Property TestingResearch Paper
Property testing asks for randomized algorithms that query a Boolean function at a few points and decide, with probability at least , whether has a property or is -far from it, meaning that at least an fraction of its values must change to land in . The classical resource is the number…