Department of
Applied
Mathematics

On Average-Case Hardness of Search Problems with Guaranteed Existence of Solution

Pavel Hubáček

IUUK

Abstract

In this talk, I will discuss a recent line of research at the intersection of computational complexity and cryptography which aims at explaining the somewhat surprising lack of efficient algorithms for many natural search problems for which solution (syntactically) always exists, the so-called total search problems. A prime example of a total search problem is finding a Nash equilibrium of a bimatrix game.

I will present our most recent result in this direction which connects average-case hardness of total search problems to worst-case hardness of counting problems in the complexity class #P assuming the security of a standard cryptographic transformation due to Fiat and Shamir. Our results imply that, under these assumptions, there exists a distribution of bimatrix games for which no polynomial-time algorithm can find a Nash equilibrium.

Our main technical contribution is a stateful incrementally verifiable procedure which, given a Boolean formula over n variables, counts the number of its satisfying assignments. This is accomplished via an exponential sequence of efficient steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes proof of its correctness which can be updated and verified in time poly(n).

Based on joint work with Arka Rai Choudhuri, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen and Guy N. Rothblum which appeared in STOC 2019.