Seminar: March 12
Sourav Chakraborty, Chennai Mathematical Institute
Testing of Boolean Function Isomorphism
Testing isomorphism among various objects is a very important problem is Computer Science. We consider the problem of testing whether two given functions are isomorphic under permutation of the inputs. It is one of the most well studied problem in Property Testing and in the past couple of year we have made significant progress in understanding the problem. We know various classes of functions for which testing isomorphism can be done by looking at only a constant number of bits of the truth table. We try to characterize all functions such that isomorphism to it can be tested using constant number of queries to the truth table. These new understanding on this problem also helps in testing of other function properties.
This is based of several papers which are joint works with Eldar Fischer, Arie Matsliah, David G Soriano, Raghav Kulkarni, Eric Blais and Noga Alon.