slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Makrand Sinha
CWI Amsterdam
Friday, 7. June 2019 - 13:30 to 15:00

in IM, rear building, ground floor

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.

Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Pavel Hubacek
MFF UK
Friday, 24. May 2019 - 13:30 to 15:00

in IM, rear building, ground floor

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... more

Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucky
MFF UK
Friday, 17. May 2019 - 13:30 to 15:00

in IM, rear building, ground floor

We will present an algorithm that runs in time n^{1+eps} and computes a
constant factor approximation to edit distance of two input strings, given that
their edit distance is at least n^{1-delta} for some delta>0 dependening on eps>0.
Joint work with Mike Saks.

Lower bounds on balancing families
Pavel Hrubes
IM CAS
Friday, 3. May 2019 - 13:30 to 15:00

in IM, rear building, ground floor

A family of proper non-empty subsets S1, . . . , Sk ⊂ [n] is called
balancing if for every subset X ⊂ [n] of size n/2, there is i ∈ [k] so that
                |Si ∩ X| = |Si|/2.
I will show that, for n even, the size of a balancing family must be at least
n(1-o(1))/2. A similar reasoning can be applied to prove lower bounds on certain
types of depth-two circuits computing the majority function. 

Joint work with S.Ramamoorthy, A. Rao, and A. Yehudayoff.

Pages