Doctoral seminar

Kombinatorický seminář pro pokročilé (NDMI041) se v roce 2015/2016 koná ve čtvrtek od 9:50 do 12:10 v S6.

Seminář vedou Robert Šámal a Hans Raj Tiwary, o program se stará Jan Musílek, o změnách mu pište emailem na adresu stinovlas@kam....

Účastníci semináře referují všeobecně zajímavé matematické a informatické články (zpravidla náročnější než se probírají na studentském kombinatorickém semináři). Články vybírají školitelé zúčastněných doktorandů a další zájemci po dohodě s vedoucími semináře. Úkolem řečníka je přečíst a pochopit celý článek. V samotném referátu je možné, a někdy i nutné, vybrat jen některé části. Vždy má však být vysvětlen hlavní výsledek i s celým důkazem nebo, pokud je celý důkaz příliš rozsáhlý, aspon jeho část a hlavní myšlenky ostatních částí.

Referující má také za úkol připravit jedno- až dvoustránkové shrnutí, na začátku semináře ho rozdat ostatním účastníkům a také poslat elektronickou verzi (handout) Janu Musílkovi emailem na stinovlas@kam..., nejlépe jako PDF nebo PostScript.

Přehled navržených článků je k dispozici na zvláštní stránce. Články z jiných zdrojů jsou v zásadě vítány, ale konzultujte je prosím s vedoucími semináře.

Announcements are sent out via mailing list dokt-seminar-l@kam. If you wish to subscribe, visit the archive or change your options, see the mailing list webpage.

Winter semester 2015/2016
Preliminary program:
Oct 8 Presentation of papers, program preparation. Starts 10:40.
Oct 15 Martin Böhm Thomas Rothvoß: Constructive discrepancy minimization for convex sets [arXiv]
Oct 22 Dušan Knop Balázs Szegedy: An information theoretic approach to Sidorenko's conjecture [arXiv] [handout]
Oct 29 Peter Korcsok Ken-ichi Kawarabayashi, Mikkel Thorup: Combinatorial coloring of 3-colorable graphs [arXiv]
Nov 5 Debarati Das Mika Göös: Lower Bound for Clique vs. Independent Set [web]
Nov 12 Jana Syrovátková Siddharth Barman: Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem [arXiv] [handout]
Nov 19 Pavel Dvořák Mika Göös, Toniann Pitassi, Thomas Whatson: Deterministic Communication vs. Partition Number [web] [handout]
Nov 26 Jaroslav Hančl Noga Alon, Shagnik Das, Roman Glebov, Benny Sudakov: Comparable pairs in families of sets [arXiv] [handout]
Dec 3 Pavel Veselý Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein: Welfare Maximization with Limited Interaction [arXiv] [handout]
Dec 10 (?) Homonolo
Dec 17 Martin Balko Wojciech Samotij, Benny Sudakov: On the number of monotone sequences [arXiv] [handout]
Dec 24 Vánoce
Jan 31 Silvestr
Jan 7 Radek Hušek Noga Alon, Elchanan Mossel, Robin Pemantle: Corruption Detection on Networks [arXiv] [handout]
Jan 14 Jan Musílek Artur Czumaj: Random Permutations using Switching Networks [web] [handout]
Summer semester 2015/2016
Feb 25 Video of L. Babai lecture on Graph Isomorphism in Quasipolynomial Time. Starts at 10:15.
Mar 3 Dušan Knop Julia Chuzhoy: Improved Bounds for the Excluded Grid Theorem [arXiv] [handout]
Mar 10 Tomáš Masařík Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin: Tight Bounds for Subgraph Isomorphism and Graph Homomorphism [arXiv] [handout]
Mar 17 Pavel Dvořák Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh: Exact Algorithms via Monotone Local Search [arXiv] [handout]
Mar 24 Pavel Veselý Massimo Lauria, Pavel Pudlák, Vojtěch Rödl, Neil Thapen: The complexity of proving that a graph is Ramsey [arXiv] [handout]
Mar 31 Jan Musílek Jon Kleinberg, Sigal Oren: Mechanisms for (Mis)allocating Scientific Credit [web]
Apr 7 Spring school
Apr 14 Jaroslav Hančl Brendan Murphy, Oliver Roche-Newton, Ilya Shkredov: Variations on the sum-product problem [arXiv] [handout]
Apr 21 Martin Böhm Subhash Khot, Dana Moshkovitz: NP-hardness of approximately solving linear equations over reals [web]
Apr 28 Jana Syrovátková Ayush Choure, Sundar Vishwanathan: Random walks, electric networks and the transience class problem of sandpiles [arXiv]
May 5 Martin Balko Tomáš Kaiser, Matěj Stehlík: Colouring quadrangulations of projective spaces [arXiv] [handout]
May 12 Vojtěch Kaluža Florent Foucaud, Michael Krivelevich, Guillem Perarnau: Large subgraphs without short cycles [arXiv] [handout]
May 19 Radek Hušek Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup: Changing base without losing space [web]
May 26 Peter Korcsok Charalampos Mavroforakis, Michael Mathioudakis, Aristides Gionis: Absorbing random-walk centrality: Theory and algorithms [arXiv]

Archived seminar pages: 2001/2002, 2002/2003, 2003/2004, 2004/2005, 2005/2006, 2006/2007, 2007/2008, 2008/2009, 2009/2010, 2010/2011, 2011/2012, 2012/2013, 2013/2014. 2014/2015.

Webmaster: kamweb@kam.mff.cuni.cz         Modified: 07. 03. 2018