•  
    • Alexander Belov
    • (University of Latvia)
    • Quantum Adversary Bound
    • Abstract:
    • 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.
    • 15.12.17   13:30
    • Martin Böhm
    • (IUUK)
    • Nested Convex Bodies are Chaseable
    • Abstract:
    • 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 Bansal, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh.
    • 24.11.17   13:30
    • Chethan Kamath
    • (IST Austria)
    • Adaptively-secure secret sharing
    • Abstract:
    • 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, Ilan Komargodski, Krzysztof Pietrzak, and Daniel Wichs.)
    • 20.10.17   13:30
    • Dmitri Gavinsky
    • (IM CAS)
    • Quantum versus classical simultaneity in communication complexity
    • Abstract:
    • 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.
    • 02.06.17   13:30
    • Klim Efremenko
    • (Tel-Aviv University)
    • Testing Equality in Communication Graphs
    • Abstract:
    • Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose that on each vertex of the graph there is a player having an $n$-bit string. Each player is allowed to communicate with its neighbors according to a (static) agreed communication protocol and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem? We determine this minimum up to a lower order additive term in many cases (but not for all graphs).   In particular, we show that it is $kn/2+o(n)$ for any Hamiltonian $k$-vertex graph, and that for any $2$-edge connected  graph with $m$ edges containing no two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$. The proofs combine graph theoretic ideas with tools from additive number theory.
    • 19.05.17   13:30
    • Filip Šedivý
    • (Faculty of Mathematics and Physics, Charles Univ.)
    • Cluster Planarity
    • Abstract:
    • This thesis studies the problem of clustered planarity and follows two directions. First direction deals with computational complexity, where we show how clustered planarity can be solved in linear nondeterministic time in terms of the number of vertices of the input graph. Second directions is characterization of restricted versions of clustered planarity using minimal non-clustered-planar instances. For this purpose we introduce a notion of clustered minor using several operations reducing clustered graphs. We show that these operations preserve clustered planarity. We show that in the case of clustered graphs where clusters have size 2 and the graph is a cycle or a path, there are only finitely many minimal non-clustered-planar minors. We also mention known results about the computational complexity of clustered planarity.
    • 07.04.17   13:30
    • Igor Carboni Oliveira
    • (MFF, UK)
    • Complexity theory beyond deterministic exponential time and applications Parts II
    • Abstract:
    • Part I. (this will be on the Seminar on limits of efficient computation on Marh 15) I'll survey a variety of connections between non-uniform circuit lower bounds, non-trivial proof systems, non-trivial learning algorithms, and variants of natural properties. In particular, I plan to discuss how one can prove new unconditional lower bounds for standard complexity classes such as REXP, ZPEXP, BPEXP, and NEXP by designing algorithms with a non-trivial running time, and to present some open problems.  Part II. I'll focus on a recent application of some of the complexity-theoretic techniques behind these results. I'll describe in more detail recent progress on the problem of efficiently generating large canonical prime numbers, via pseudodeterministic pseudorandomness. If there is enough time and interest, we will also discuss some non-constructive aspects of the result, and connections to derandomization. Based on joint work with Rahul Santhanam.
    • 17.03.17   13:30
    • Anup Rao
    • (Univ. of Washington, Seattle, USA)
    • Lower bounds on Non-adaptive Data Structures for Median and Predecessor search
    • Abstract:
    • What is the best way to maintain a subset of {1,2,...,m} so that the median of the set can be easily recovered? We are interested in the algorithms that access the fewest memory locations when adding an element to the set and computing the median of the set. We prove the first lower bounds for such algorithms. We say that the algorithm handles insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of the memory. If the algorithm handles insertions non-adaptively, then our lower bounds imply that Binary Search Trees are essentially optimal (our results give a more general tradeoff between the parameters of the algorithm). In addition, we investigate the predecessor search problem, where the algorithm is required to compute the predecessor of any element in the set. Here we prove that if computing the predecessors can be done non-adaptively, then again Binary Search Trees are essentially optimal. Our results follow from a novel application of the Sunflower Lemma to these questions. This is joint work with Siva Ramamoorthy
    • 10.03.17   13:30

    Michal Koucky, Pavel Pudlak
    organizers

  •