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.

Session 11B Chair: Kunal TalwarTuesday 10/21, 10:30am-12:15pm (Crystal Ballroom)
10:30-10:50 On Learning and Testing Dynamic Environments
Oded Goldreich (Weizmann Institute) , Dana Ron (Tel-Aviv University)
10:55-11:15 Preventing False Discovery in Interactive Data Analysis is Hard
Moritz Hardt (IBM Research Almaden) , Jonathan Ullman (Harvard University SEAS)
11:20-11:40 Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
Raef Bassily (Pennsylvania State University) , Adam Smith (Pennsylvania State University) , Abhradeep Thakurta (Yahoo! Labs)
11:45-12:05New algorithms and lower bounds for monotonicity testing
Xi Chen (Columbia University) , Rocco A. Servedio (Columbia University) , Li-Yang Tan (Columbia University)
Speaker(s): 

Rocco Anthony Servedio

Computer Science
Associate Professor
ras2105@columbia.edu

Rocco Servedio is an associate professor of computer science at Columbia Engineering. His research focuses on computational learning theory and computational complexity. He is particularly interested in foundational questions of understanding what types of learning problems have—and do not have—computationally efficient algorithms. A major goal of his research is the design and analysis of computationally efficient algorithms for challenging learning problems involving noisy data and complex target functions.

Back to Top