TUNGA 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

Speakers

Schedule

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

11:30Sté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:00David WoodruffTight Bounds for L1 Oblivious Subspace Embeddings
14:25Sergio CabelloMaximum matchings in geometric intersection graphs
14:50Hamed HatamiSign-rank vs discrepancy
15:15Tasos SidiropoulosRobust metric embeddings
15:40Shanghua TengScalable Sparse Newton’s Method for Gaussian Markov Random Fields
   
16:05coffee break 
   
16:30László Miklós LovászA Fast New Algorithm for Weak Graph Regularity
16:55Marcin WrochnaGraph structure useful for approximating MaxCSPs
17:20Artur CzumajRandom graph exploration and testing of planar graphs
17:45Satoru IwataPfaffian and Matroid Matching
18:10Ken-ichi KawarabayashiThe Directed Flat Wall Theorem

Organization committee