slideshow 3

Complexity seminar

usually takes place each Friday at 14:00 - 16:00 temporarily on Zoom, normally in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list...

Quantum Adversary Bound
Alexander Belov
University of Latvia
Friday, 15. December 2017 - 13:30 to 15:00

in IM, rear building, ground floor

In this talk, I will briefly describe the quantum adversary bound, which is an
intriguing way of characterising quantum query complexity, and sketch some of its applications.
No prior knowledge of quantum computation is required.

Nested Convex Bodies are Chaseable
Martin Böhm
IUUK
Friday, 24. November 2017 - 13:30 to 15:00

in IM, rear building, ground floor

In the Convex Body Chasing problem, we are given an initial point v in R^d and an online
sequence of n convex bodies F_1,...,F_n. When we receive F_i, we are required to move inside
F_i. Our goal is to minimize the total distance travelled. This fundamental online problem was
first studied by Friedman and Linial (DCG 1993). They proved an Omega(sqrt(d)) lower bound on
the competitive ratio, and conjectured that a competitive ratio depending only on d is possible.
However, despite much interest in the problem, the conjecture remains wide open.

In this work, we give a simple f(d)-competitive algorithm for chasing *nested* convex bodies in
R^d, i.e. when F_2 lies inside F_1, F_3 lies inside F_2 and so on. Among other consequences,
this indicates that the problem is considerably more difficult when the optimal path visits
several points, as opposed to just moving to a single globally feasible position.

Joint work with Nikhil... more

Adaptively-secure secret sharing
Chethan Kamath
IST Austria
Friday, 20. October 2017 - 13:30 to 15:00

in IM, rear building, ground floor

A secret-sharing scheme is used to distribute a secret between a
set of participants so that a subset of the participants that satisfy
certain conditions can reconstruct the secret. In the computational setting,
it is relatively easy to achieve selective security (where the adversary
commits a-priori to the set of corrupt participants), but appears difficult
to achieve the more natural notion of adaptive security (where the adversary
can corrupt participants as the attack progresses). It is well known that
selective security, where the adversary has to commit to n-bits of
information about his future choices, automatically implies adaptive
security at the cost of amplifying the adversary’s advantage by a factor of
up to 2^n. In this talk we will see how one can, in certain cases, achieve
better bounds than 2^n by using techniques from graph pebbling. 

(Based on joint work with Zahra Jafargholi, Karen Klein,... more

Quantum versus classical simultaneity in communication complexity
Dmitri Gavinsky
IM CAS
Friday, 2. June 2017 - 13:30 to 15:00

in IM, rear building, ground floor

We will see a bipartite partial function, which has no efficient solution in the model of randomised simultaneous
message passing (with shared randomness), but has an efficient protocol in the model of quantum simultaneous message
passing – even without shared randomness.

This can be interpreted as the strongest known − as of today − example of "super-classical" capabilities of the
weakest studied model of quantum communication.

Pages