
Makrand Sinha
 (CWI Amsterdam)

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Abstract:

Chattopadhyay, Mande and Sherif (to appear in STOC 2019) recently
exhibited a total Boolean function, the sink function, that has polynomial
approximate rank and polynomial randomized communication complexity. This gives
an exponential separation between randomized communication complexity and
logarithm of the approximate rank, refuting the logapproximaterank conjecture.
We show that even the quantum communication complexity of the sink function is
polynomial, thus also refuting the quantum logapproximaterank conjecture.
Our lower bound is based on the fooling distribution method introduced by Rao
and Sinha (Theory of Computing 2018) for the classical case and extended by
Anshu, Touchette, Yao and Yu (STOC 2017) for the quantum case. We also give a
new proof of the classical lower bound using the fooling distribution method.
Joint work with Ronald de Wolf.

Pavel Hubacek
 (MFF UK)

Finding a Nash Equilibrium Is No Easier Than Breaking FiatShamir

Abstract:

The FiatShamir heuristic transforms a publiccoin interactive proof into a noninteractive argument,
by replacing the verifier’s random coins with a cryptographic hash function that is applied to the
protocol's transcript. Constructing hash functions for which this transformation is sound is a
central and longstanding open question in cryptography. We show that solving the EndOfMeteredLine
problem is no easier than breaking the soundness of the FiatShamir transformation when applied to
the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in
#P gives rise to a hard distribution in the class CLS. Since CLS is contained in PPAD for which the
problem of finding a Nash equilibrium is complete, our results show existence of a distribution of
strategic games for which it is not possible to find a Nash equilibrium in polynomial time.
Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT
instance over n variables, counts the number of satisfying assignments. This is accomplished via an
exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means
that each intermediate state includes a sumcheckbased proof of its correctness, and the proof can be
updated and verified in time poly(n).
Joint work with Arka Rai Choudhuri, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen and Guy N.
Rothblum.
Michal Koucky, Pavel Pudlak
organizers