FoCS Archive News - Before Sept 20
Seven papers accepted to the 31st SODA
We are pleased to report that members of the department's Theory and Foundations research theme have had 7 papers accepted to the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, to be held in Salt Lake City, Utah, USA, January 5-8, 2019. SODA is the premier international conference on algorithms research, and the papers are:
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal by M. S. Ramanujan, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
- An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs by Sayan Bhattacharya, Janardhan Kulkarni
- Coarse-Grained Complexity for Dynamic Algorithms by Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
- Combinatorial Generation via Permutation Languages by Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, Aaron Williams
- On the Power of Relaxed Local Decoding Algorithms by Tom Gur, Oded Lachish
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity by Alessandro Chiesa, Tom Gur, Igor Shinkar
- Sublinear time approximation of the cost of a metric k-nearest neighbor graph by Artur Czumaj, Christian Sohler