[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~

THEORY SEMINAR
 
 
Tuesday, March 13, 2013
3:00 p.m.
Ryerson 251
 
Sourav Chakraborty
Chennai Mathmatical Institute (CMI)
www.cmi.ac.in
 
Title:  Testing of Boolean Function Isomorphism
 
Abstract: 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.

 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130312/9d4792f0/attachment.htm