Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Talks in 2017

January 05, Bernhard Haeupler (Carnegie Mellon University): Synchronization Strings: Optimal Coding for Insertions and Deletions [details]
January 12, David Steurer (Cornell Univ., Ithaca, and Inst. of Advanced Study, Princeton): Efficient algorithms for tensor decomposition and their applications [details]
January 24, Rajko Nenadov (Monash University): Optimal induced universal graphs for bounded-degree graphs [details]

February 02, Rati Gelashvili (MIT): Time-Space Trade-Offs in Population Protocols [details]
February 07, Dan Alistarh: The Power of Choice in Priority Scheduling [details]
February 09, Stefan Weltge (IFOR): Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank [details]
Friday, February 10, in CAB G11, Ioannis Emiris (University of Athens): Dimensionality reduction for search in general dimension [details]
February 14, Zur Luria (ITS): Hamiltonian spheres in random hypergraphs [details]
February 16, Jukka Suomela (Aalto University): Understanding computation with computation [details]
February 21, Mohsen Ghaffari: LOCAL Algorithms: The Chasm Between Randomized and Deterministic [details]
February 23, Penny Haxell (University of Waterloo): Stability for matchings in regular hypergraphs [details]
February 28, Jerri Nummenpalo: Finding One of Many Needles in a Haystack: Searching and Sampling SAT [details]

March 02, Pascal Pfister: Asymptotically Optimal Amplifiers for the Moran Process [details]
March 07, David Adjiashvili (IFOR): Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs [details]
March 09, Daniel Kral (University of Warwick): Graph limits and extremal combinatorics [details]
March 14, Jara Uitto: Lower Bounds for the Ants Nearby Treasure Search (ANTS) Problem [details]
March 16, Shoham Letzter (ITS): Long monochromatic paths in 2-coloured random tournaments [details]
March 21, Torsten Mütze (TU Berlin): Trimming and gluing Gray codes [details]
March 23, Richard Montgomery (Trinity College, Cambridge): Subdivisions in $C_4$-free graphs [details]
March 28, Matija Bucic: Directed Ramsey number for trees [details]
March 30, Patrick Schnider: How to share a pizza [details]

April 04, Malte Milatz: Linear Programs, Violators, and Random Walks [details]
April 06, Alexey Pokrovskiy: Fast draws in strong games [details]
April 11, Frank Mousset: Minimum degree conditions for large trees [details]
April 13, Nemanja Skoric: Bootstrapping graph packing [details]
April 25, Manuel Wettstein: An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings [details]
April 27, Pascal Su: Labeling Schemes for Rooted Trees [details]

May 02, Kenneth Clarkson (IBM Research Almaden): Low-rank PSD Approximation in Input-Sparsity Time [details]
May 04, Ralph Keusch: Routing in internet-like graphs by using only local information [details]
May 09, Miloš Trujić: Local resilience of sparse random graph properties at the threshold [details]
May 11, Kilian Risse: Phases of Unique Sink Orientations and Their Role in Finding the Sink [details]
May 16, Manuela Fischer: Deterministic Distributed Matching via Rounding [details]
May 18, Luis Barba: Subquadratic Algorithms for Algebraic Generalizations of 3SUM [details]
May 23, Roger Wattenhofer: Online Matching [details]
May 30, Vytautas Gruslys (University of Cambridge): Tilings of high-dimensional spaces [details]

June 01, Ahad N. Zehmakan: Opinion spreading in random geometry [details]
June 06, Mohsen Ghaffari: (Blackboard Talk) Improved LOCAL Algorithms for the Lovasz Local Lemma, with Ramifications on LOCAL Complexities [details]
June 08, Jason Li (Carnegie Mellon University): Shortcuts in Excluded Minor Graphs [details]
Monday, June 26, Asaf Ferber (MIT): Counting H-free graphs [details]
June 27, József Balogh (University of Illinois): An improved lower bound for Folkman's theorem [details]
Wednesday, June 28, Marlo Eugster (Master's thesis): Vertex covering by monochromatic cycles [details]
June 29, Christoph Koch (University of Warwick): How to (re-)establish a brand: bootstrap percolation in social networks [details]

July 06, Jara Uitto: Tight Lower Bounds for the Cops and Robbers Game (Practice Talk) [details]
July 11, Anders Martinsson (Chalmers University): Edge-orderings and long increasing paths in graphs [details]

August 03, Peter Davies (University of Warwick): Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks [details]
August 10, Christiana Lymouri: Simple and Near-Optimal Distributed Coloring for Sparse Graphs [details]

Monday, September 11, in CAB G11, Haris Angelidakis (Toyota Technological Institute at Chicago): Algorithms for Stable and Perturbation-Resilient Problems [details]
September 19, Emo Welzl: Lower Bounds for Searching Robots, some Faulty [details]
September 21, Manuela Fischer: Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching [details]
September 26, Alexander Pilz: Arrangements of Approaching Pseudo-Lines [details]
September 28, Jakub Tarnawski (EPFL): Matching is in Quasi-NC [details]

October 03, Ralph Keusch: Edge-coloring graphs against an adversary [details]
October 05, Dániel Korándi (EPFL): On the Turán number of ordered forests [details]
October 10, Malte Milatz: Random walks on polytopes [details]
October 12, Nina Kamcev: Zero forcing in random and pseudorandom graphs [details]
October 17, Luis Barba: Convex hulls in the presence of obstacles [details]
October 19, Igor Balla: Equiangular Subspaces [details]
October 24, Thomas Dueholm Hansen (Aarhus University): Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made [details]
October 26, Jara Uitto: Distributed Degree Splitting and Edge Coloring [details]
October 31, Omri Ben-Eliezer (Tel Aviv University): The ordered graph removal lemma [details]

November 02, Dan Alistarh: Computing with Soup: New Results and Techniques in Population Protocols [details]
November 07, Dmitry Shabanov (Lomonosov Moscow State University): On the chromatic number of a sparse random hypergraph [details]
November 09, Patrick Schnider: Measures of depth for multiple points [details]
November 14, Natasha Morrison (University of Oxford): Bootstrap Percolation in the Hypercube [details]
November 16, Asier Mujika: Fast-Slow Recurrent Neural Networks [details]
November 21, Ahad N. Zehmakan: Majority Model on Random Regular Graphs [details]
November 23, Tuan Tran: Erdos-Rothschild problem for intersecting families [details]
November 28, Nina Corvelo Benz: Black and White Bin Packing [details]
November 30, Charlotte Knierim: Clique coloring of dense random graphs [details]

December 05, Aleksandr Efremov: Homomorphisms Are a Good Basis for Counting Small Subgraphs [details]
December 07, Torsten Mütze: Rainbow cycles in flip graphs [details]
December 12, Jerri Nummenpalo: Sparse Kneser graphs are Hamiltonian [details]
December 14, Shoham Letzter: Path partitions of regular graphs [details]