Randomized and Approximation Algorithms Seminar

Dr Grzegorz Gutowski
Dr Jakub Kozik
Dr Tomasz Krawczyk

Tuesday 16:15 - 17:45, room 0174

Previous seminars

04.06.2019 16:15
Jarosław Grytczuk
Politechnika Warszawska
Graph polynomials and choosability
A result of Thomassen asserts that every planar graph is 5-choosable (colorable from arbitrary lists of size 5 preassigned to the vertices of a graph). We prove that every planar graph has a matching whose deletion gives a 4-choosable graph. The proof is based on Combinatorial Nullstellensatz - a famous algebraic result of Alon involving multivariable polynomials. We also discuss possible applications of this method to other graph coloring problems, like the four color problem or the empire coloring problem, for instance.
 
Joint work with Xuding Zhu.
26.02.2019 16:15
Marcin Briański
Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz)
15.01.2019 16:15
Marcin Briański
Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz)
08.01.2019 16:15
Bartosz Wodziński
Algorithmic barriers from phase transitions (Dimitris Achlioptas, Amin Coja-Oghlan)
18.12.2018 16:15
Maciej Czerwiński
Lovasz meets Weisfeiler and Leman (by Dell, Grohe and Rattan)
"In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k -dimensional generalization known as the Weisfeiler-Leman algorithm."
27.11.2018 16:15
04.12.2018 16:15
Dominika Salawa, Kamil Kropiewnicki
Representative sets in matroids (based on chapter of 'Parameterized algorithms')
20.11.2018 16:15
Dawid Tracz
Finding Cliques in Social Networks: A New Distribution-Free Model (Fox, Roughgarden, Seshadhri, Wei, Wein)
13.11.2018 16:15
Mateusz Pabian
New approximation algorithm for (1,2)-TSP (Adamaszek, Mnich, Paluch)
06.11.2018 16:15
Szymon Łukasz
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors (A. Bhangale)

We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices,

1) It is NP-hard to color it with log^delta n colors for some delta>0.

2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.

30.10.2018 16:15
Wiktor Daniec
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
14.04.2015
Maciej Solon
Graphs defined by forbidden patterns.
 
13.01.2015
Andrzej Dorobisz.
Treewidth. Courcelle's theorem.
 
16.12.2014
Grzegorz Gutowski.
s-t orientations of planar graphs.
 
02.12.2014
Andrzej Dorobisz
Treewidth.
 
25.11.2014
18.11.2014,Patryk Mikos
Kernelization and Linear Programming Techniques
 
03.06.2014
M. Solon, P. Wójcik
Polynomial coloring of 3-colorable graphs.
 
27.05.2014
20.05.2014
13.05.2014
Adam Gągol
Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma (by Harris and Srinivasan)

 
References:
David G. Harris, Aravind Srinivasan, Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma, STOC '13

15.04.2014
Grzegorz Gutowski, Jakub Kozik
Lower bounds for on-line graph colorings (cont.)
(join work with P. Micek and X. Zhu)  
08.04.2014
01.04.2014,
Cancelled (all participants are invited to the lecture of prof. A. Ruciński.)
 
18.03.2014
Grzegorz Gutowski, Jakub Kozik
Lower bounds for on-line graph colorings
(join work with P. Micek and X. Zhu)  
04.03.2014
Igor Adamski
Outer-string graphs are chi-bounded
 
References:
Alexandre Rok, Bartosz Walczak, Outer-string graphs are chi-bounded, preprint
21.01.2014
Maciej Solon
On the number of edges in families of pseudo-discs
 
References:
Piotr Micek, Rom Pinchasi, On the number of edges in families of pseudo-discs, preprint
14.01.2014
Maciej Bendkowski
List Colouring When The Chromatic Number Is Close To the Order Of The Graph
 
References:
B. Reed, B. Sudakov, List Colouring When The Chromatic Number Is Close To the Order Of The Graph, Combinatorica December 2004, Volume 25, Issue 1, pp 117-123
07.01.2014
Aneta Pawłowska
Three Topics in Online List Coloring
 
References:
J. Carraher, S. Loeb, T. Mahoney, G. Puleo, M. Tsai, D.B. West,Three Topics in Online List Coloring, preprint
17.12.2013
10.12.2013,Damian Królik
Sum-paintability of generalized theta-graphs
 
References:
J. Carraher, T. Mahoney, G.J. Puleo, D.B. West , Sum-paintability of generalized theta-graphs, preprint
26.11.2013
Wojciech Łopata
Conflict-Free Colourings of Uniform Hypergraphs With Few Edges
 
References:
A.V. Kostochka, M. Kumbhat, T. Łuczak, Conflict-Free Colourings of Uniform Hypergraphs With Few Edges, Combinatorics, Probability and Computing Volume 21 Issue 4, July 2012
12.11.2013
Tomasz Krawczyk, Bartosz Walczak
Coloring subtree overlap graphs with O(log lgo n) colors.
 
05.11.2013
Grzegorz Guśpiel
On the construction of 3-chromatic hypergraphs with few edges.
 
References:
Heidi Gebauer, On the construction of 3-chromatic hypergraphs with few edges, JCTA 120 (2013)