Property Testing of Linear Threshold Functions

Inferring underlying properties of a dataset is a fundamental task in the fields of learning, statistics, and data analysis. In recent years, the amount of data which we have access to and would like to analyze continues to grow at an astronomical rate. Algorithms that were previously considered efficient for learning properties of the data are no longer feasible in this domain, and in many cases it is even prohibitively expensive to look through the entire data-set. This motivates the study of property testers, highly-efficient algorithms for determining whether a set of data satisfies a desired property, or is far from any data-set satisfying that property, while observing only a small portion of the data.
This work continues the study of property-testing of linear threshold functions (LTFs), a fundamental class of functions for learning theory, optimization, and computational complexity. TO BE CONT’D

Faculty Supervisor:

Toniann Pitassi

Student:

Partner:

National Institute of Informatics

Discipline:

Computer science

Sector:

Education

University:

University of Toronto

Program: