Title: Online Correlated Selection

Speaker: Zhiyi Huang (Associate Professor, University of Hong Kong)

Abstract:

This tutorial will introduce a new technique called Online Correlated Selection (OCS) proposed by Fahrbach et al. in 2020. Since then, researchers have designed OCS algorithms for many settings, improving the state-of-the-art online algorithms for these problems, including resolving several decade-old open problems in online matching. The tutorial will also draw a connection to several classical problems, including balls into bins and online scheduling.

Bio:

Zhiyi Huang is an Associate Professor of Computer Science at the University of Hong Kong. His research areas are Theoretical Computer Science and Algorithmic Game Theory, focusing on optimization and decision-making under uncertainty. Before joining HKU, Zhiyi was a postdoc at Stanford University from 2013 to 2014, under Tim Roughgarden. He earned his Ph.D. in 2013 from the University of Pennsylvania, studying under Sampath Kannan and Aaron Roth. During his doctoral studies, Zhiyi interned at Microsoft Research Redmond with Nikhil R. Devanur in the summers of 2011 and 2012. He received his Bachelor's degree from the first "Yao Class" under Andrew Yao at Tsinghua University in 2008. Zhiyi received the Best Paper Awards at FOCS 2020 and SPAA 2015, the Excellent Young Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong Kong, and the Morris and Dorothy Rubinoff Dissertation Award.

Title: TCS and OR in Industry

Speaker: Huawei Taylor Lab

Abstract:

In our session, we will introduce how research from theoretical computer science and operational research are applied in industry. Also, we will present some research results motivated by real business problems. Finally, we will introduce several challenging problems, hoping further communition and potential cooperations.

Bio:

Huawei Taylor Lab is a research lab for Huawei Technologies. Its research areas include the core theories of theoretical computer science such as complexity theory, algorithm design, as well as its applications in different related domains such as economics and operations research. The missions of the lab are (1) to become a world-class research center in theoretical computer science and explore new frontiers in science and technology, and (2) to provide algorithmic solutions for Huawei and create value for our customers.
From a theory perspective, we work in the broad domain of theoretical computer science, including its intersection and interactions with other fields. Our objective is to solve important open questions and develop innovative techniques and theoretical tools that link theoretical computer science to other disciplines in science and technology. In particular, we hope to combine theoretical computer science, heuristic methods, operations research, and machine learning, and design innovative algorithms with both theoretical guarantees and real-world applicability.
From an application perspective, we work closely with different business sectors within the company and provide algorithmic solutions that can be directly applied to existing and new products and services at Huawei, such as ICT products and solutions, Consumer Business, and Huawei cloud service. Through the lens of our algorithms, we aspire to continuously provide value and solve problems for our customers.
One final mission of the Taylor Lab is to connect theory and application, and to bring together academia and industry. Through the means of joint laboratory, visiting scholars, collaborative project, postdocs, and internships, we aim to foster a close relationship with the global academic community and co-create research that better serves the society and the world.

Title: Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem

Speaker: Ken-ichi Kawarabayashi (Professor, National Institute of Informatics)

Abstract:

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (non-trivial) snark that can be embedded in the projective plane is the Petersen graph. This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph. Here, a replacement of a vertex v in a cubic graph G is the operation that takes a 2-connected planar (cubic) multigraph H containing some vertex u of degree 3, unifying G− v and H − u, and connecting the vertices in NG[v] in G− v with the three neighbors of u in H − u with 3 edges. Any graph obtained in such a way is said to be Petersen-like. This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability.

Bio:

Ken-ichi Kawarabayashi has been a professor at the National Institute of Informatics since 2009 and became a professor at the University of Tokyo in 2022. From 2019 to 2021, he also served as the deputy director general of the National Institute of Informatics. His research interests include graph theory, combinatorics, scalable algorithms, combinatorial optimization, and their application to machine learning, as well as the theoretical analysis of deep learning. In addition to his academic roles, Ken-ichi serves as an editor for Algorithmica, Journal of Graph Theory, Graphs and Combinatorics, TheoriTCS, and four other prestigious journals. He has been recognized with SODA'13 best paper.