NEWS

Prof. KAWARABAYASHI Ken-ichi won The 2021 Fulkerson Prize Award The Fulkerson Prize Title Deterministic Edge Connectivity in Near-Linear Time Name KAWARABAYASHI Ken-ichi (NII) Mikkel Thorup(University of Copenhagen) The citation for the award “Determining the edge connectivity of a graph is one of the most fundamental graph problems. Kawarabayashi and Thorup’s work does not just improve the running time of the algorithm, impressive as that is. Its main contributions are conceptual:the paper introduces powerful and impactful new ideas that will have a long-lasting influence on the field. The most powerful of these ideas is a fast deterministic sparsification that essentially preserves all the non-trivial minimum cuts of the graph. “ Organization […] MORE

Lin Bingkai has received Best ICALP Paper at ICALP 2019 【ICALP 2019, July 8-12, 2019, Patras, Greece】 Track A – Bingkai Lin: “A Simple Gap-producing Reduction for the Parameterized Set Cover Problem”.

Date: July 4, 2019 11:00-12:00 Speaker：Lin Bingkai Title：A Simple Gap-producing Reduction for the Parameterized Set Cover Problem  Details：https://sites.google.com/view/tcs-tokyo/home This paper is accepted at ICALP 2019

Date：June 20, 2019 11:00 – 12:00 Speaker: Nobutaka Shimizu Title：Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models Detais：https://sites.google.com/view/tcs-tokyo/home

Date：June 6, 2019 10:30 – 12:00 Speaker：Benjamin Rossman Title：Criticality and decision-tree size of AC^0 functions Speaker：Rahul Santhanam Title：Why are Proof Complexity Lower Bounds Hard? Details: https://sites.google.com/view/tcs-tokyo/home

Date：May 23, 2019 11:00 – 12:00 Speaker: Yoichi Iwata Title：0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms (FOCS’18) Details：https://sites.google.com/view/tcs-tokyo/home