Total Search Problems

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!

About

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 [42], Cryptography [33, 35, 36, 38], Probabilistically Checkable Proofs [13, 14], Linear Programming and Sum-of-Squares hierarchies [49].

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.

Organizers

Aviad Rubinstein

Email: aviad [at) cs(dot] stanford(dot] edu

Manolis Zampetakis

Email: mzampet [at) mit(dot]edu

Program

Time
Presenter
Title
03:20 p.m.
Introduction to the Complexity of Total Search Problems
04:00 p.m.
Break
04:10 p.m.
Total Search Problems and Cryptography
04:40 p.m.
TFNP in Query & Communication Complexity
05:10 p.m.
Break
PPA-Completeness
End of The Potential Line
Communication Complexity of Local Search
Sum of Squares and TFNP
Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games

Venue

Tha workshop will take place on October 6th 2018 in Paris at Institut Henri Poincaré (Directions).

References on the Complexity of Total Search Problems

    Definition of Classes
  1. How Easy is Local Search?  
    Journal of Computer and System Sciences, 1988
  2. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence  
    Journal of Computer and System Sciences, 1994
  3. Continous Local Search  
    22nd SIAM Symposium on Discrete Algorithms SODA 2011
  4. Towards a Unified Complexity Theory of Total Functions  
    9th Innovations in Theoretical Computer Science ITCS 2018
  5. Black Box Separations of TFNP Subclasses
  6. The Relative Complexity of NP Search Problems  
    Journal of Computer and System Sciences, 1998
  7. Finding Collisions on a One-Way Street: Can Secure Hash Fhnctions Be Based on General Assumptions?  
    27th Annual International Conference on the Theory and Applications of Cryptographic Techniques EUROCRYPT 1998
  8. Classification of Search Problems and Their Definability in Bounded Arithmetic  
    Electronic Colloquium on Computational Complexity, 2001
  9. Relativized NP Search Problems and Propositional Proof Systems  
    19th IEEE Conference on Computational Complexity CCC 2004
  10. Closure Under Cook-Reductions
  11. Propositional Proofs and Reductions between NP Search Problems  
    Annals of Pure and Applied Logic, 2012
  12. Hardness of Finding a Nash Equilibrium
  13. The Complexity of Computing a Nash Equilibrium  
    SIAM Journal of Computing, 2009
  14. Settling the Complexity of Computing Two-Player Nash Equilibria  
    47th Annual IEEE Symposium on Foundations of Computer Science FOCS 2006
  15. Approximate Nash Equilibrium and PCP for PPAD
  16. Inapproximability of Nash Equilibrium  
    47th Annual ACM Symposium on the Theory of Computing STOC 2015
  17. Can almost everybody be almost happy?  
    9th Annual Innovations in Theoretical Computer Science ITCS 2016
  18. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria  
    57th Annual IEEE Symposium on Foundations of Computer Science FOCS 2016
  19. More on PPAD-completeness
  20. Market Equilibria in Polynomial time for fixed number of goods or agents  
    49th Annual IEEE Symposium on Foundations of Computer Science FOCS 2008
  21. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities  
    50th Annual IEEE Symposium on Foundations of Computer Science FOCS 2009
  22. Reducibility Among Fractional Stability Problems  
    50th Annual IEEE Symposium on Foundations of Computer Science FOCS 2009
  23. Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities  
    Journal of ACM, 2011
  24. PLS-completeness
  25. Simple Local Search Problems that are Hard to Solve  
    SIAM Journal of Computing, 1991
  26. The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem  
    SIAM Journal of Computing, 1992
  27. The Complexity of Pure Nash Equilibria  
    36th Annual ACM Symposium on the Theory of Computing STOC 2004
  28. PPA-completeness
  29. A Sperner Lemma Complete for PPA  
    Information Processing Letters, 2001
  30. 2-D Tucker is PPA-complete  
    Electronic Colloquium on Computational Complexity, 2015
  31. Understanding PPA-completeness  
    31th IEEE Conference on Computational Complexity CCC 2016
  32. Octahedral Tucker is PPA-complete  
    Electronic Colloquium on Computational Complexity, 2017
  33. On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz  
    31th IEEE Conference on Computational Complexity CCC 2017
  34. Consensus Halving is PPA-Complete  
    50th Annual ACM Symposium on the Theory of Computing STOC 2018
  35. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches  
    Manuscript ArXiv 2018
  36. PPP-completeness
  37. PPP-completeness with Connections to Cryptography
    59th Annual IEEE Symposium on Foundations of Computer Science FOCS 2018
  38. CLS-completeness
  39. A Converse to Banach's Fixed Point Theorem and its CLS Completeness
    50th Annual ACM Symposium on the Theory of Computing STOC 2018
  40. End of potential line  
    Manuscript ArXiv 2018
  41. Cryptography and Total Search Problems
  42. On Algorithms for Nash Equilibria  
    Manuscript, 2004
  43. On the Cryptographic Hardness of Finding a Nash Equilibrium  
    56th Annual IEEE Symposium on Foundations of Computer Science FOCS 2015
  44. Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium  
    36th International Cryptology Conference CRYPTO 2016
  45. Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds  
    28th ACM-SIAM Symposium on Discrete Algorithms SODA 2017
  46. White-box vs. Black-box Complexity of Search Problems: Ramsey and Graph Property Testing  
    58th Annual IEEE Symposium on Foundations of Computer Science FOCS 2017
  47. The Journey from NP to TFNP Hardness  
    8th Innovations in Theoretical Computer Science ITCS 2017
  48. Can PPAD Hardness be Based on Standard Cryptographic Assumptions?  
    15th IACR Theory of Cryptography Conference TCC 2017
  49. Factoring in PPA and PPP
  50. On the TFNP complexity of factoring  
    Manuscript, 2006
  51. Integer factoring and modular square roots  
    Journal of Computer and System Sciences, 2016
  52. Query & Communication Complexity and TFNP
  53. Communication complexity of approximate Nash equilibria  
    49th Annual ACM Symposium on the Theory of Computing STOC 2017
  54. Monotone circuit lower bounds from resolution  
    50th Annual ACM Symposium on the Theory of Computing STOC 2018
  55. Lifting Nullstellensatz to Monotone Span Programs over Any Field  
    50th Annual ACM Symposium on the Theory of Computing STOC 2018
  56. Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria  
    59th Annual IEEE Symposium on Foundations of Computer Science FOCS 2018
  57. The Communication Complexity of Local Search  
    Manuscript ArXiv 2018
  58. Adventures in Monotone Complexity and TFNP  
    Electronic Colloquium on Computational Complexity, 2018
  59. Communication Complexity of Cake Cutting  
    Manuscript, 2018
  60. Sum of Squares and TFNP
  61. Tight SoS-Degree Bounds for Approximate Nash Equilibria  
    31th IEEE Conference on Computational Complexity CCC 2016
  62. Sum-of-Squares meets Nash: Lower Bounds for Finding any Equilibrium  
    50th Annual ACM Symposium on the Theory of Computing STOC 2018
  63. Smoothed Complexity of Total Search Problems
  64. Smoothed Analysis of Local Search for the Maximum-Cut Problem  
    25nd SIAM Symposium on Discrete Algorithms SODA 2014
  65. Local max-cut in smoothed polynomial time  
    49th Annual ACM Symposium on the Theory of Computing STOC 2017
  66. Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games  
    Manuscript, 2018