3rd Annual Scientific Meeting of Computer Science Institute of Charles University and Institute for Theoretical Computer Science (CE-ITI)

The meeting takes place on Friday December 19, 2014. All lectures are in the building of MFF UK in Malá Strana, Malostranské nám. 25.

Program

Morning lectures are in the room S1, 4th floor
9:30 Jaroslaw Byrka: Recent progress on approximation algorithms for the k-median problem
10:30 Coffee break
10:45 Pavel Surynek: Solving cooperative path-finding optimally by reducing it to propositional satisfiability
11:15 Martin Tancer: Van Kampen - Flores type non-embeddability result for 2k-dimensional manifolds
11:45 Dmitry Gavinsky: Equality, revisited
12:30 Lunch at the faculty building
Afternoon lectures are in the room S5, 2nd floor
14:00 Harald Helfgott: 93rd Mathematical Colloquium – The ternary Goldbach conjecture
15:30 Zuzana Haniková, Petr Savický: Term satisfiability in FLew-algebras
16:00 Zdeněk Dvořák: Tree-width and separators

Abstracts

Jaroslaw Byrka: Recent progress on approximation algorithms for the k-median problem

The k-median problem is: given a set of clients and a set of facilities all being points in a metric space, select a subset of k facilities so as to minimize the total distance from clients to selected facilities. I will first survey some recent results including our recent improvement of the Li and Svensson algorithm. Then, I will talk in more detail about a factor-revealing LP technique used in the improvement of one of the ingredients of the algorithm. Finally, I will briefly talk about the capacitated version of the problem and go through recent algorithms that violate either the number of facilities or the capacities of facilities.

Pavel Surynek: Solving Cooperative Path-Finding Optimally by Reducing it to Propositional Satisfiability

The talk will address makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task in CPF is to relocate a set of agents to given goal locations so that they do not collide with each other. A novel SAT encoding of CPF will be described. The novel encoding uses the concept of matching in bipartite graphs to separate spatial constraints of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evaluation shown that novel encoding can be solved faster than existing encodings for CPF and that the SAT based methods dominates over A* based methods in environments densely occupied by agents.

Martin Tancer: Van Kampen - Flores type non-embeddability result for 2k-dimensional manifolds

(Joint work with X. Goaoc, I. Mabillard, P. Patak, Z. Patakova, and U. Wagner)

The van Kampen - Flores theorem says that the k-dimensional skeleton of the (2k+2)-simplex does not embed into R^2k. We prove an analogous result for 2k-dimensional manifolds. We show that for every 2k-dimensional compact manifold M there is a value n such that the k-dimensional skeleton of the n-simplex does not embed into M. This result is also related to a conjecture of Kuhnel, who conjectured that if M is in addition (k-1)-connected, then n can be taken as the smallest integer satisfying \binom{n-k-1}{k+1} > b\binom{2k+1}{k+1} where b is the kth reduced Betti number of M (over Z_2). Our bound, n = 2b\binom{2k+2}{k}+2k+6 is weaker, but on the other hand, it holds for an arbitrary compact 2k-manifold.

Dmitry Gavinsky: Equality, Revisited

(Joint work with Hartmut Klauck)

The Equality function is, probably, one of the most fundamental problems studied in the field of Communication Complexity (the problem is as old as the field itself, both having been introduced in 1979 by A. Yao).

We propose a new method for analysing the communication complexity of Equality in the Simultaneous Message Passing model, which

  1. gives a number of new tight lower bounds, and
  2. offers a unified way of treating Equality in virtually all imaginable variations of the original model, both previously-studied and newly-defined: quantum, classical, mixed (quantum-classical), with Merlin added, etc.

Harald Helfgott (CNRS - Paris VI/VII): The ternary Goldbach conjecture

The ternary Goldbach conjecture (1742) asserts that every odd number greater than 5 can be written as the sum of three prime numbers. Following the pioneering work of Hardy and Littlewood, Vinogradov proved (1937) that every odd number larger than a constant C satisfies the conjecture. In the years since then, there has been a succession of results reducing C, but only to levels much too high for a verification by computer up to C to be possible (C>10^1300). (Works by Ramare and Tao solved the corresponding problems for six and five prime numbers instead of three.) My recent work proves the conjecture. We will go over the main ideas of the proof.

Z. Hanikova, P. Savicky: Term satisfiability in FLew-algebras

We investigate satisfiability of terms in a class of algebras interpreting the full Lambek calculus with exchange and weakening (FLew). The language of this logic, as well as of its algebraic semantics, is nearly classical (with two conjunctions, a disjunction, an implication, and constants 0 and 1), and the class of FLew-algebras subsumes, e.g., Heyting algebras or MV-algebras (rendered in an appropriate language). As each of the algebras contains the two-element Boolean algebra as a subalgebra, the set of satisfiable terms extends the classically satisfiable ones. We offer some characterizations of algebras where the two sets of terms coincide. We also try to reconstruct parts of the duality between satisfiability and validity of terms, familiar from classical logic, within this wider algebraic setting.

Zdenek Dvorak: Tree-width and separators

(joint work with Sergei Norin)

It is well-known that a graph of tree-width at most k has a separator of order at most k+1 which splits the graph into parts of approximately the same size. Using a result on confluent flows, we show a rough converse to this claim: If every subgraph of G has such a balanced separator of order at most s, then G has tree-width at most 105s.