•  
    • Navid Talebanfard
    • (Institute of Mathematics, CAS)
    • Interlude: how many error correcting codes are there?
    • Abstract:
    • We continue our journey through the landscape of extremal combinatorics. This time we will acquaint ourselves briefly with the powerful technique of (hyper)graph containers which is used to bound the number of independent sets in various graphs and hypergraphs. Specifically, possibly of interest of complexity theorists, we will see a result of Balogh, Treglown and Wagner which gives a close to tight bound on the number of possible error correcting codes of a given relative distance.
    • 11.12.20   14:30
    • Pavel Hrubeš
    • (Institute of Mathematics, CAS)
    • Tau conjectures
    • Abstract:
    • Tau conjectures of Koiran and Poitier are an approach towards proving arithmetic circuit lower bounds. Besides that, they are related to some interesting mathematics. I will explain the background and whatever I feel like at the moment. 
    • 27.11.20   14:30
    • Susanna F. de Rezende
    • (Institute of Mathematics, CAS)
    • KRW Composition Theorems via Lifting
    • Abstract:
    • Proving super-logarithmic lower bounds on the depth of circuits (i.e., P \neq NC^1) is one of the main frontiers of circuit complexity.  In 1991, Karchmer, Raz and Wigderson observed that we could resolve this question by proving the following conjecture: Given two non-constant boolean functions f, g, the depth complexity of their composition is approximately equal to the sum of their individual depth complexities.    Several works have made progress towards resolving this conjecture by proving it for every outer function f, but only when composed with two specific inner functions g. In this talk, I will present a recent result that extends the range of inner functions that can be handled to include any function g whose depth complexity can be lower bounded via a certain lifting theorem. Based on a joint work with Or Meir, Jakob Nordstrom, Toniann Pitassi, and Robert Robere. 
    • 20.11.20   14:30
    • Navid Talebanfard
    • (Institute of Mathematics, CAS)
    • Combinatorial miniatures from low depth complexity, chapter two
    • Abstract:
    • Motivated by proving lower bounds for affine dispersers, in this chapter we will see a graph theoretic characterization of affine spaces accepted by 2-CNFs.
    • 13.11.20   14:30
    • Navid Talebanfard
    • (Institute of Mathematics, CAS)
    • Combinatorial miniatures from low depth complexity, chapter one
    • Abstract:
    • In what is hopefully going to be a series of talks, I will survey very natural extremal combinatorial questions arising from complexity theory. I will point out several questions and report some progress. In the first chapter we will look at a relaxation of VC dimension and prove a Sauer-Shelah type theorem.
    • 23.10.20   14:30
    • Pavel Pudlak
    • (IM)
    • Tree codes - recent progress
    • Abstract:
    • The problem of finding an explicit construction of good tree codes over a constant size alphabet is still open. In this talk I will explain the problem and mention some recent results and proposed approaches to this problem.
    • 16.10.20   14:30
    • Dmitry Gavinsky
    • (IM, CAS)
    • Bare quantum simultaneity versus classical interactivity in communication complexity
    • Abstract:
    • We shall see a relational problem that is easy for the weakest quantum model of communication – simultaneous message passing (without shared resources); at the same time, the problem is difficult for the strongest classical model – interactive (two-way) communication.
    • 02.10.20   14:30
    • Navid Talebanfard
    • (IM, CAS)
    • Super Strong ETH is true for strong PPSZ
    • Abstract:
    • Super Strong ETH states that there is no k-SAT algorithm with running time 2^(1 - f_k)m where f_k >> 1/k. We prove that this hypothesis is true for the strong version of the PPSZ algorithm. Previously such a bound was known only for the weak version of PPSZ. Our construction is based on a modification of satisfiable Tseitin formulas over a certain class of high girth graphs. This is joint work with Dominik Scheder.
    • 24.04.20   13:30
    • Navid Talebanfard
    • (IM, CAS)
    • A tutorial on character sums and Paley graphs
    • Abstract:
    • We recall the famous of problem explicit constructions of Ramsey graphs. One of the early non-trivial constructions is Paley graphs defined using quadratic residues in finite fields. We will see nice tools from analytic number theory to study properties of this graph.  
    • 27.03.20   13:30
    • Stanislav Žák
    • (Institute of Computer Science, CAS)
    • A Logical Characteristic of Read-Once Branching Programs
    • Abstract:
    • We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties: i) The "knowledge" arising at a stage of computation in question is derivable from the "knowledge" arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p. ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a "mystery" information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.) We prove that with respect to our model no such information exists in read-once b.p.`s but on the other hand in b. p.`s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see the instances of our models as a systems $S=(U,D)$ where $U$ is a universe of knowledge and $D$ arederivation rules. We say that a b.p. $P$ is compatible with a system $S$ iff along each computation in $P$ $S$ derives $F$ ($false$) or $T$ ($true$) at the end correctly according to the label of the reached sink. This key notion modifies the classic paradigm according to which the computational complexity is defined with respect to different classes of restricted b.p.`s (e.g. read-once b.p.`s, k-b.p.`s, b.p.`s computing in limited time etc.). Now, the restriction is defined by a subset of systems and only these programs are taken into account which are compatible with at least one of the chosen systems. Further  we may understand the sets $U$ of knowledge(s) as a sets of admissible logical formulae.  More rich  sets $U$`s imply the larger (= more free) restrictions on b.p.`s and consequently the smaller complexities of Boolean functions are detected. More rich logical equipment implies stronger computational effectiveness.
    • 31.01.20   13:30

    Michal Koucky, Pavel Pudlak
    organizers

  •