Sourav Chakraborty (Theory Seminar S14)

chakraborty.jpg"Testing of Boolean Function Isomorphism"
Sourav Chakraborty
(Chennai Mathematical Institute)
Monday, May 19th, 2014, 2:00 pm
EBU3B, Room 4140
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. These new understanding on this problem also helps in testing of other function properties.