in Computation, Communication and Cryptography
Welcome to the workshop on the complexity of total search problems, that will be held at FOCS 2018 in Paris!
Total search problems are ones where every instance has a solution. Yet, a growing body of evidence suggests that finding this solution is sometimes intractable. This phenomenon has fascinated complexity theorists since the 1980’s [1, 2]. Over the last few decades, it has also been tied to an increasingly diverse list of applications from areas such as Combinatorial Optimization, Graph Theory, Economics and Social Choice.
In the last few years we saw both exciting breakthroughs on some of the core problems on the study of complexity of total functions, as well as new connections discovered to other areas of Theoretical Computer Science: Communication Complexity [41, 42, 43, 44], Circuit Complexity , Cryptography [33, 35, 36, 38], Probabilistically Checkable Proofs [13, 14], Linear Programming and Sum-of-Squares hierarchies .
The main goal of this workshop is to introduce the broad Theoretical Computer Science community to total functions and the aforementioned connections to various subfields, as well as promote new connections. A secondary goal of the workshop is to advertise some of the recent breakthroughs (including natural complete problems for PPA and PPP [27, 29]), and shine the spotlight on some of the core open problems.
Email: aviad [at) cs(dot] stanford(dot] edu
Email: mzampet [at) mit(dot]edu