Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. UW

Information

Home page

List of talks

• April 19, 2018, 12:15 p.m.
  Laszlo Kozma (TU Eindhoven)
  Trees and heaps: the many faces of basic data structures
  Binary search trees (BSTs) and heaps are the canonical comparison-based implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about …

  ---

• April 5, 2018, 12:15 p.m.
  Wiktor Zuba (MIMUW)
  Hamilitonian cycles of middle-levels subgraphs of hypercubes
  The n-dimension hypercube graph is the graph with vertices represented by sequences of n bits, with edges connecting those vertices, which representations differ at exactly one position. We can divide the graph into (n+1) levels, …

  ---

• March 15, 2018, 12:15 p.m.
  Marthe Bonamy (LaBRI, CNRS, Universite de Bordeaux)
  Distributed coloring in sparse graphs with fewer colors
  Distributed coloring in sparse graphs with fewer colors Abstract : We are concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, …

  ---

• March 8, 2018, 12:15 p.m.
  Magnus Wahlström (University of London)
  Fine-grained structure of NP-hard SAT problems
  Say that a problem SAT(\Gamma), for a constraint language \Gamma, admits an improved algorithm if it can be solved in O(c^n) time on n variables for some c<2, and that it is hard otherwise. Many …

  ---

• March 1, 2018, 12:15 p.m.
  Marc Heinrich (LIRIS )
  Online graph coloring with bichromatic exchanges
  Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires $\Omega(\log n)$ colors in the worst case. …

  ---

• Feb. 8, 2018, 12:15 p.m.
  Lucas Pastor
  Disproving the normal graph conjecture
  A graph G is said to be normal if there exists two coverings, C and S of its vertex set such that, every member of C induces a clique, every member of S induces a …

  ---

• Dec. 7, 2017, 12:15 p.m.
  Marcin Pilipczuk (Uniwrsytet Warszawski)
  The Erdős-Hajnal conjecture for caterpillars and their complements
  The celebrated Erdos-Hajnal conjecture states that for every proper hereditary graph class GG there exists a constant eps>0 such that every graph G in GG contains a clique or an independent set of size |V(G)|^eps. …

  ---

• Nov. 23, 2017, 12:15 p.m.
  Irene Muz
  Half-integral linkages in highly connected directed graphs
  We study the half-integral k-Directed Disjoint Paths Problem (1/2 kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where k=2, and the input graph is L-strongly connected, for …

  ---

• Nov. 9, 2017, 12:15 p.m.
  Bart M. P. Jansen (Eindhoven University of Technology)
  Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
  We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-Deletion problem is the following: given …

  ---

• July 6, 2017, 12:15 p.m.
  Brynmor Chapman (Massachusetts Institute of Technology)
  A Refutation of the Gotsman-Linial Conjecture
  A degree-$d$ polynomial threshold function is a function that can be written as the sign of a degree-$d$ polynomial on the Boolean hypercube.  Bounds on the sensitivity of polynomial threshold functions to small changes in …

  ---

• June 8, 2017, 12:15 p.m.
  Marek Adamczyk (University of Warsaw)
  When the Optimum is also Blind: a New Perspective on Universal Optimization
  Consider the following variant of the set cover problem. We are given a universe $U={1,2,...,n}$ and a collection of subsets C={S_1,...,S_m} where each S_i is a subset of U. For every element u of U …

  ---

• May 11, 2017, 12:15 p.m.
  Till Miltzow (Universit ́e libre de Bruxelles)
  The Art Gallery Problem is $\exists \mathbb{R}$-complete
  The \emph{art gallery problem} is a classical problem in computational geometry, introduced in 1973 by Viktor Klee. Given a simple polygon \poly and an integer $k$, the goal is to decide if there exists a …

  ---

• April 20, 2017, 12:15 p.m.
  Marcin Wrochna (University of Warsaw)
  A topological approach related to Hedetniemi's conjecture
  Hedetniemi's 50 years old conjecture states that the chromatic number of the tensor product of graphs G,H is the minimum of the chromatic numbers of G and H. The conjecture has many interesting connections with …

  ---

• March 23, 2017, 12:15 p.m.
  Paweł Rzążewski (Politechnika Warszawska)
  Fine-grained complexity of coloring disks, balls, and segments.
  On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian …

  ---

• March 16, 2017, 12:15 p.m.
  Andreas Emil Feldmann (Charles University)
  The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
  Given a directed graph G and a list (s1 , t1 ), . . . , (sk , tk ) of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of G …

  ---