Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium "Algorytmika"

Research seminar (FRIDAYS, usually biweekly at 14.15 in room 5060 or online)

For schedule or link to online meetings, see

Rules for PhD studens:

Google calendar:

YouTube cannel:

Lista referatów

  • 2018-04-05, godz. 12:15, 5870

    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, where k-th level contains those vertices, which have exactly k one...

  • 2018-03-15, godz. 12:15, 5870

    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, planar graphs can be colored with at most 4 colors, and the p...

  • 2018-03-08, godz. 12:15, 5870

    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 examples exist, both of problems SAT(\Gamma) with improved algorithms and problems hypothesised...

  • 2018-03-01, godz. 12:15, 5870

    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. We consider a variation of the First-Fit algorithm in which the algorithm is...

  • 2018-02-08, godz. 12:15, 5870

    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 stable set, and every clique of C intersects every stable set of S. De Simone and Körner conjectured in 1999 that a graph G is norma...

  • 2017-12-07, godz. 12:15, 5870

    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. Recently, there has been a growing interest in the symmetrized variant of th...

  • 2017-11-23, godz. 12:15, 5870

    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 any L >= 1. We show that when the integrality condition i...

  • 2017-11-09, godz. 12:15, 5870

    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 a graph G and integer k, is it possible to delete k vertices from G ...

  • 2017-07-06, godz. 12:15, 5870

    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 their inputs have many applications in circuit complexity and learning t...

  • 2017-06-08, godz. 12:15, 5870

    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 we need to find a set phi(u) from C such that u belongs to phi(u). Once we construct and fix the m...