Theory Underlying Algorithms

Co-located with SODA'20, January 5-8, 2020, at Hilton Salt Lake City Center, Utah

Many aspects of contemporary computer science are deeply dependent on advances in mathematics. In particular, developments in graph theory, algebra, geometry, topology, logic and number theory form foundation for many recent results in algorithm design, complexity theory and cryptography. The workshop aims to bring closer experts from these fields and to provide a venue for theory-building works with a potential for future applications in computer science.

Joint SODA/TUNGA Plenary Speaker

- Stéphan Thomassé (École Normale Supérieure de Lyon, France)

Speakers

- Sergio Cabello (University of Ljubljana)
- Artur Czumaj (University of Warwick)
- Hamed Hatami (McGill University)
- Satoru Iwata (University of Tokyo)
- László Miklós Lovász (Massachusetts Institute of Technology)
- Tasos Sidiropoulos (University of Illinois at Chicago)
- Shanghua Teng (University of Southern California)
- David Woodruff (Carnegie Mellon University)
- Marcin Wrochna (University of Oxford)

Schedule

Joint SODA/TUNGA plenary talk on Tuesday, January 7, in Grand Ballroom C.

11:30 | Stéphan Thomassé | Computing Maximum Independent Set in Graph Classes |

All other talks take place on Tuesday, January 7 in the Canyon A&B room.

14:00 | David Woodruff | Tight Bounds for L1 Oblivious Subspace Embeddings |

14:25 | Sergio Cabello | Maximum matchings in geometric intersection graphs |

14:50 | Hamed Hatami | Sign-rank vs discrepancy |

15:15 | Tasos Sidiropoulos | Robust metric embeddings |

15:40 | Shanghua Teng | Scalable Sparse Newton’s Method for Gaussian Markov Random Fields |

16:05 | coffee break | |

16:30 | László Miklós Lovász | A Fast New Algorithm for Weak Graph Regularity |

16:55 | Marcin Wrochna | Graph structure useful for approximating MaxCSPs |

17:20 | Artur Czumaj | Random graph exploration and testing of planar graphs |

17:45 | Satoru Iwata | Pfaffian and Matroid Matching |

18:10 | Ken-ichi Kawarabayashi | The Directed Flat Wall Theorem |

Organization committee

- Zdeněk Dvořák (Charles University, Czech Republic), contact for participation and organization inquiries
- Ken-ichi Kawarabayashi (National Institute of Informatics, Japan)
- Jaroslav Nešetřil (Charles University, Czech Republic)