Computer Science/Discrete Mathematics Seminar I

The computational complexity of finding Nash Equilibria in games has received much attention over the past two decades due to its theoretical and philosophical significance. This talk will be centered around the connection between this problem and cryptography. Mostly, I will discuss a result proving that finding Nash equilibrium is hard, assuming the existence of a cryptographic notion called indistinguishability obfuscation. This is done by demonstrating that this cryptographic notion gives rise to a hard computational problem in the complexity class PPAD, for which finding Nash equilibrium is known to be complete.Indeed, in recent years indistinguishability obfuscation has turned out to have surprisingly strong implications in cryptography and beyond. I will give the high-level picture as to where we stand in our efforts of constructing such obfuscators and basing them on solid hardness assumptions. In a companion talk on Tuesday, I will discuss one specific line of work that reduces indistinguishability obfuscation to simple assumptions on 5-linear maps, coming closer to well-studied cryptographic objects such as bilinear-map groups.The talk is based on joint work with Paneth and Rosen. No prior knowledge in cryptography is required.