Say Alice has a string x of length n (EXAMPLE: x=0111 and n=4). Say Bob has a string y of length n They want to know if x=y. Alice could just say HEY BOB, MY STRING is x, and Bob could shout back either YES x=y or NO x is NOT y. This would require communication n bits. This could be A LOT of bits (say if x is the collected works of Shakespeare). Can they determine if x=y while communication FAR less bits. Come to the talk to find out!
Please RSVP Here!
Dr. Gasarch got his BS in Math and Applied Math at SUNY Stonybrook in the Spring of 1980.
He then got a PhD from Harvard in Computer science in the Spring of 1985. He got a Job at Univ of MD as a professor in Fall of 1985 and has been there ever since. His main intersts have shifted from logic to combinatorics, but always with an eye towards applying these to computer science theory. He currently advised MANY High School Students, some of which have won awards.