Testing Function Isomorphism
Oct 6, 2010
Consider the following problem: I give you query access to some (unknown) function f, and you must determine whether f is identical, up to relabeling of the input variables, to some (known) function g or whether f is "far" from identical to g. How many queries do you need to accomplish this task?
The problem can be made precise in the property testing framework, where it is called the function isomorphism testing problem. The number of queries required to test isomorphism to g depends on the choice of the function g, and until recently this query complexity was known only for a small number of functions.
In this talk, we will discuss a recent result that gives tight bounds on the query complexity for testing isomorphism to g for almost all boolean functions g. We will also survey some other recent results that establish strong lower bounds on the query complexity of the problem for explicit classes of functions.
This talk is based on joint work with Ryan O'Donnell (CCC '10) and Noga Alon (RANDOM '10).
The problem can be made precise in the property testing framework, where it is called the function isomorphism testing problem. The number of queries required to test isomorphism to g depends on the choice of the function g, and until recently this query complexity was known only for a small number of functions.
In this talk, we will discuss a recent result that gives tight bounds on the query complexity for testing isomorphism to g for almost all boolean functions g. We will also survey some other recent results that establish strong lower bounds on the query complexity of the problem for explicit classes of functions.
This talk is based on joint work with Ryan O'Donnell (CCC '10) and Noga Alon (RANDOM '10).