New algorithms and lower bounds for monotonicity testing

Tuesday, October 21, 2014 - 10:30am to 12:15pm
Foundations of Computer Science (FOCS 2014)
Radisson Blu Warwick Hotel (Crystal Ballroom)
Philadelphia, PA 19103
United States

Abstract: We consider the problem of testing whether an unknown Boolean function f:\{-1,1\}^n -> \{-1,1} is monotone versus ϵ-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem.

Back to Top