• 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 log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank 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.
    • 07.06.19   13:30
    • Pavel Hubacek
    • (MFF UK)
    • Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
    • Abstract:
    • The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive 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 long-standing open question in cryptography. We show that solving the End-Of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir 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 sumcheck-based 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.  
    • 24.05.19   13:30

    Michal Koucky, Pavel Pudlak