Doktorandský seminář

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

Seminář vedou Robert Šámal, Jiří Matoušek a Hans Raj Tiwary, o program se stará Tomáš Gavenčiak, o změnách mu pište emailem na adresu gavento@kam....

Účastníci semináře referují pokud možno 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) Tomáši Gavenčiakovi emailem na gavento@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.

Zimní semestr 2014/2015
2. října Prezentace článků, příprava programu. Začátek 10:40.
9. října Jaroslav Hančl David Conlon, Jacob Fox, Benny Sudakov: Short proofs of some extremal results [arXiv] [handout]
16. října Tomáš Masařík Noga Alon: Bipartite decomposition of random graphs [arXiv] [handout]
23. října Eva Jelínková Bingkai Lin: The Parameterized Complexity of $k$-Biclique [handout]
30. října Dušan Knop Daniel Marx: Can you beat treewidth? [PDF] [handout]
6. listpadu Martin Koutecký Thomas Rothvoß: Directed Steiner Tree and the Lasserre Hierarchy [arXiv] [handout]
13. listpadu Martin Böhm Boaz Barak, Prasad Raghavendra, David Steurer: Rounding Semidefinite Programming Hierarchies via Global Correlation [arXiv] [handout]
20. listpadu Radek Hušek Choongbum Lee, Sang-il Oum: Number of cliques in graphs with forbidden minor [arXiv] [handout]
27. listpadu Vojta Kaluža Thomas Rothvoß: The matching polytope has exponential extension complexity [arXiv] [handout]
4. prosince Michaela Seifertová Eran Nevo, Stedman Wilson: How many $n$-vertex triangulations does the $3$-sphere have? [arXiv] [handout]
11. prosince Homonolo
18. prosince Pavel Veselý Noga Alon, Troy Lee, Adi Shraibman: The Cover Number of a Matrix and its Algorithmic Applications [www] [handout]
25. prosince Vánoce
1. ledna Nový rok
8. ledna Martin Balko Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, Joshua Zahl: A semi-algebraic version of Zarankiewicz's problem [arXiv] [handout]
Summer semester 2014/2015
Feb 19 Paper presentation, program preparation. Starts at 10:40.
Feb 26 Michaela Seifrtová Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan: Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap [arXiv] [handout]
Mar 5 Debarati Das Allan Gronlund, Seth Pettie: Threesomes, Degenerates, and Love Triangles [arXiv] [handout]
Mar 12 Martin Böhm James R. Lee, Prasad Raghavendra, David Steurer: Lower bounds on the size of semidefinite programming relaxations [arXiv] [handout]
Mar 19 Pavel Veselý Venkatesan Guruswami, Ali Kemal Sinop: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives [arXiv] [handout]
Mar 26 Martin Balko Wojciech Samotij: Counting independent sets in graphs [arXiv] [handout]
Apr 2 Vojtěch Kaluža Pavle V. M. Blagojević, Florian Frick, Günter M. Ziegler: Tverberg plus constraints [arXiv] [handout]
Apr 9 Jaroslav Hančl Samuel Johnson, Marni Mishna, Karen Yeats: Towards a Combinatorial Understanding of Lattice Path Asymptotics [arXiv] [handout-X]
Apr 16 Radek Hušek Cody D. Murray, Ryan Williams: On the (Non) NP-Hardness of Computing Circuit Complexity [PDF] [handout]
Apr 23 No seminar
Apr 30 Elazar Goldenberg Irit Dinur, David Steurer: Analytical Approach to Parallel Repetition [arXiv] [handout]
May 7 Spring school
May 14 Dušan Knop Frédéric Havet, Stéphan Thomassé: Median orders of tournaments: a tool for the second neighbourhood problem and Sumner's conjecture. [PDF] [handout]
May 21 Tomáš Masařík Zeev Dvir, Sivakanth Gopi: 2-Server PIR with sub-polynomial communication [arXiv] [handout]
Preliminary program:

Archivované stránky semináře za minulé roky: 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.

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