Manolis Zampetakis and I are organizing a workshop at FOCS on the complexity of total search problems.

Looking for a needle that you know is in the haystack

Search problem means that we’re looking for something. Total means that what we’re looking for is guaranteed to exist. A famous example is Nash equilibrium: every game has at least one equilibrium, but [Daskalakis, Goldberg, Papadimitriou 2009] proved that it is PPAD-hard to find any of them.

Communication Complexity, Cryptography, PCPs, Sum-of-Squares, Quantum

A specific focus of this workshop is on connections to different sub-fields of Theory of Computer Science. We’ve seen exciting progress on those recently, and we hope the workshop can further bridge together all of the above (actually, all of TCS). Which brings me to my next point…

Who will be there?

You!

We already have some fantastic speakers confirmed (schedule and workshop website coming soon), including an opening overview talk by Costis Daskalakis, who recently received the Nevalinna Prize (in part) for his work on total search problems.
By the way, if you have something interesting to tell the community about total search problems, and we haven’t contacted you yet about giving a talk, please let us know. We can probably still accommodate you in the schedule, even if you don’t have a Nevalinna Prize.

Looking forward to seeing y’all there – it will be totally awesome!
(Sorry- I couldn’t resist the bad pun…)