•  
    • Jan Pich
    • (Oxford University)
    • Hardness magnification near state-of-the-art lower bounds
    • Abstract:
    • We continue the development of hardness magnification, a strategy for deriving strong circuit lower bounds by reducing them to a refined analysis of weaker models proposed by Oliveira and Santhanam (2018). Specifically, we consider a gap version of the meta-computational problem MCSP which asks to distinguish truth-tables of Boolean functions of small circuit complexity from truth-tables of a slightly larger complexity and establish that a small improvement over the state-of-the-art lower bounds in a variety of computational models for the gap version of MCSP would imply explicit super-polynomial lower bounds. This talk is based on a joint work with Igor C.Oliveira and Rahul Santhanam.
    • 14.12.18   13:30
    • Navid Talebanfard
    • (IM)
    • An exposition of R. Williams' "Strong ETH Breaks with Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation".
    • Abstract:
    • Variants are the Strong Exponential Time Hypothesis have been proposed. In this talk I sketch Williams' result which asserts that Strong ETH fails when we have both non-determinism and randomization. The proof uses arithmetization and polynomial arguments.
    • 07.12.18   13:30
    • Debarati Das
    • (Charles University)
    • Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
    • Abstract:
    • Edit distance is a measure of similarity of two strings based onthe minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor $\text{poly}(\log n)$. In this talk, I will describe an algorithm with running time $\tildeO(n^{2-2/7})$ that approximates the edit distance within a constant factor. This is a joint work with Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky, Michael Saks
    • 23.11.18   13:30
    • Pavel Hubáček
    • (MFF UK)
    • The Journey from NP to TFNP Hardness
    • Abstract:
    • The complexity class TFNP is the search analogue of the class NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. In my talk, I will show that hard-on-average TFNP problems exist under the weak assumption that there exists a hard-on-average language in NP. In terms of techniques, our results demonstrate an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs. Based on joint work with Moni Naor and Eylon Yogev.
    • 08.06.18   13:30
    • Diptarka Chakraborty
    • (Charles University)
    • Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
    • Abstract:
    • The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems, see Henzinger et al. [STOC'15]. In recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure (that is, we only charge for memory accesses, while computation is free). Their cell probe data structure answers queries in $\tilde{O}(n^{7/4})$ time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional $\tilde{O}(n^{7/4})$ bits on the side. In this talk, we present a new cell probe data structure with query time $\tilde{O}(n^{3/2})$ storing just $\tilde{O}(n^{3/2})$ bits on the side. We then complement our data structure with a matching lower bound showing that any data structure storing $r$ bits on the side, with $n < r < n^2$ must have query time $t$ satisfying $t r = \tilde{\Omega}(n^3)$. For $r \leq n$, any data structure must have $t = \tilde{\Omega}(n^2)$. Since lower bounds in the cell probe model also apply to classic word-RAM data structures, the lower bounds naturally carry over. This talk will be based on a joint work with Lior Kamma and Kasper Green Larsen (to appear in STOC'18).
    • 25.05.18   13:30
    • Pavel Pudlák
    • (IM, CAS)
    • Matroids, 3-regular graphs and random restrictions
    • Abstract:
    • I will show some connections between matroids and random restrictions of Tseitin tautologies on 3-regular graphs. In particular I will show that the domains of the restrictions are flats in a matroid that is dual to a bicircular matroid. I will pose several problems concerning how these facts can be generalized to other kinds of restrictions and other graphs. This talk will be a sort of a continuation of Navid's, but I will recall everything that is needed.
    • 11.05.18   13:30
    • Alexander V. Smal
    • (Steklov Math. Inst., St. Petersburg)
    • Half-duplex communication complexity
    • Abstract:
    • Suppose Alice and Bob are communicating bits to each other in order to compute some function f but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is in fact more powerful than the classical one as it allows to compute some functions in smaller number of rounds. We also introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions. Join work with  Kenneth Hoover, Russell Impagliazzo and Ivan Mihajlin
    • 04.05.18   13:30
    • Eric Allender
    • (Rutgers University)
    • Complexity meets Computability: Connections between Computational Complexity Theory and the Kolmogorov Random Strings
    • Abstract:
    • In this talk, I will survey some results (some dating back more than a decade) indicating that certain computational complexity classes can be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings.  There have been a few new developments, and there are a lot of open questions. Some of the main results in this line of research: Let U be a universal Turing machine, and let R_U be {x : K_U(x) is at least |x|}.  That is, R_U is the set of Kolmogorov-random strings, when K-complexity is defined using universal machine U. When we write "R" instead of "R_U" in statement, it will mean that the statement holds for EVERY universal machine U.  Let P_tt(A) denote the class of sets that are polynomial-time non-adaptively reducible to A (also known as the class of sets that are polynomial-time truth-table reducible to A).  Let P(A) denote the class of sets that are poly-time Turing-reducible to A. Theorem: BPP is contained in P_tt(R), which is contained in PSPACE, which is contained in P(R). NEXP is contained in NP(R), which is contained in EXPSPACE(R).
    • 27.04.18   13:30
    • Navid Talebanfard
    • (IM CAS)
    • Random 3-regular graphs from random 3-regular graphs
    • Abstract:
    • Given a 3-regular graph we define a natural process which gives a random topological minor of this graph. We show that if the original graph is uniformly distributed, so is the resulting topological minor over the space of 3-regular graphs of the same size. Based on ongoing work with Pavel Pudlák and Neil Thapen.
    • 23.03.18   13:30
    • Jan Hladký
    • (IM CAS)
    • Graphons as weak* limits
    • Abstract:
    • Around 2004, Lovasz and Szegedy came up with a certain compactification of the space of finite graphs. More precisely, they proved that there exists a metric - now called the cut-distance - which yields a compact topology. Their proof of compactnes relies on the Szemeredi regularity lemma. An entire theory, with applications in extremal graph theory and random graphs, developed from this statement. I will talk about approaching the cut-norm topology via the weak* topology. This approach gives a new view of many properties, and in particular yields a quick and elementary proof of the Lovasz-Szegedy theorem. The talk will be self-contained. Various bits of this are joint work with Martin Dolezal, Jan Grebik, Jon Noel, Diana Piguet, Israel Rocha, Vaclav Rozhon, Maria Saumell.
    • 19.01.18   13:30
    • Navid Talebanfard
    • (IM CAS)
    • Prediction, partial information and hindsight
    • Abstract:
    • Let X be a random variable distributed over n bit strings with entropy at least n - k. Subaddativity implies that the average coordinate has entropy close to 1 if k is small. Meir and Wigderson recently showed that the same remains true even if we are allowed to non-deterministically query around n/k other coordinates. I will present an alternative proof of this fact which quantitatively tightens this result. Furthermore I will show how Meir and Wigderson used to this to develop a top-down argument for depth-3 circuit lower bounds.  Based on join work with Alexander Smal.
    • 12.01.18   13:30

    Michal Koucky, Pavel Pudlak
    organizers

  •