Distance-Sensitive Property Testing Lower Bounds

In this paper, we consider several property testing problems and ask how the query complexity depends on the distance parameter $\eps$. We achieve new lower bounds in this setting for the problems of testing whether a function is monotone and testing whether the function has low Fourier degree. For monotonicity testing, our lower bound matches the recent upper bound of Chakrabarty and Seshadhri.

• Publication year

  2013

• Venue

  arXiv: Computational Complexity

• Publication date

  2013-04-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1304.6685
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A o(n) monotonicity tester for boolean functions over the hypercube

  2013cited by this paper
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

  2012influential reference
• A Brief Introduction to Property Testing

  2011cited by this paper
• Nearly tight bounds for testing function isomorphism

  2011cited by this paper
• Property Testing Lower Bounds via Communication Complexity

  2011influential reference
• Efficient Sample Extractors for Juntas with Applications

  2011cited by this paper
• Algorithmic and Analysis Techniques in Property Testing

  2010cited by this paper
• On Testing Computability by Small Width OBDDs

  2010cited by this paper
• Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown

  2010cited by this paper
• Testing Boolean Function Isomorphism

  2010cited by this paper
• Lower Bounds for Testing Function Isomorphism

  2010cited by this paper
• Monotonicity testing and shortest-path routing on the cube

  2010cited by this paper
• Introduction to Testing Graph Properties

  2010cited by this paper
• Transitive-Closure Spanners of the Hypercube and the Hypergrid

  2009cited by this paper
• Testing Computability by Width-Two OBDDs

  2009cited by this paper
• Improved Bounds for Testing Juntas

  2008cited by this paper
• The Randomized Communication Complexity of Set Disjointness

  2007cited by this paper
• Testing for Concise Representations

  2007cited by this paper
• Testing Juntas

  2002cited by this paper
• An information statistics approach to data stream and communication complexity

  2002cited by this paper
• Monotonicity testing over general poset domains

  2002cited by this paper
• Fast approximate PCPs for multidimensional bin-packing problems

  1999cited by this paper
• Improved Testing Algorithms for Monotonicity

  1999cited by this paper
• Testing Monotonicity

  1998cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• The Probabilistic Communication Complexity of Set Intersection

  1992cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• On the Distributional Complexity of Disjointness

  1990cited by this paper
• Some complexity questions related to distributive computing(Preliminary Report)

  1979cited by this paper

• Reconstruction and testing via decision trees

  2021cites this paper
• Testing and reconstruction via decision trees

  2020cites this paper
• Reconstructing Decision Trees

  2020cites this paper
• Lp-testing

  2014cites this paper