Chennai Mathematical Institute

Seminars




12:00 noon
Monotonicity testing and directed isoperimetries of the hypercube

Seshadri C
Sandia National Labs, San Francisco.
23-09-13


Abstract

A function f:{0,1}^n -> R (where R is some ordered set) is called "monotone" if for all x < y, f(x) \leq f(y). The problem of monotonicity testing is to determine if a given function is monotone or "far" from monotone, using as few queries as possible. This is a classic property testing problem that has seen much work since the seminal paper of Goldreich et al (1999) that introduced this problem. There have been recent advances in this problem for the general case (when R is the reals) and the boolean case (when R is {0,1}). These were obtained by connections to the isoperimetry problem: given a set S of {0,1}^n, what can be said of the edge/vertex boundary of S in the directed hypercube?

This talk will focus on this connection, but will be structured as a sort of survey of monotonicity testing.

Based on joint work with Deeparnab Chakrabarty