Program

The conference will be held in the Crowne Plaza Chengdu West by IHG hotel (成都新希望高新皇冠假日酒店). See this page for details of the venue.

Program at a Glance

August 15th:

  • Time: 08:45 - 20:30
  • Venue: Main Venue
08:45 - 09:00 Opening Session (Session Chair: TBD)
09:00 - 09:50 Invited Talk 1
Session Chair: TBD
Andrew Chi-Chih Yao
Cryptography in the Age of AI, Bio and Quantum
09:50 - 10:40 Invited Talk 2
Session Chair: TBD
Saket Saurabh
FPT Approximation Algorithms for Coverage and Satisfiability Problems
10:40 - 11:10 Coffee Break
11:10 - 12:10 Session 1: Approximation Algorithms I

Session Chair: TBD
(#11) Tong Xu, Wei Yu and Zhaohui Liu. An Improved Approximation Algorithm for the Minimum $k$-Star Partition Problem
(#170) Mengzhen Li, Chenchen Wu, Dachuan Xu and Yicheng Xu. Approximating per-scenario bound for the two-stage stochastic facility location problem
(#91) Lunhao Zhang, Pengzhi Gao and Peng Zhang. Doubly Constrained Fair Clustering for General p-Norms
12:10 - 14:10 Lunch Break
14:10 - 15:30 Session 2: Parameterized Algorithms

Session Chair: TBD
(#135) Chengcheng Sun, Haitao Jiang, Guojun Li and Daming Zhu. A Randomized Fixed-Parameter Tractable Algorithm for Sorting Unsigned Genomes by Translocations: Breaking the 1.375 Approximation Barrier
(#199) Feng Shi, Yicong Zhu, Guangwei Wu, Jingyi Liu and Jianxin Wang. Improved Parameterized Algorithms for Scheduling with Precedence Constraints and Time Windows
(#96) Panfeng Liu and Biaoshuai Tao. Parameterized Complexity of Influence Maximization
(#172) Faisal N. Abu-Khzam, Tom Davot, Lucas Isenmann and Sergio Thoumi. On the Complexity of 2-Club Cluster Editing with Vertex Splitting
15:30 - 16:00 Coffee Break
16:00 - 17:20 Session 3: Computational Complexity

Session Chair: TBD
(#9) Yuan Li, Haowei Wu and Yi Yang. Average-Case Deterministic Query Complexity of Boolean Functions with Fixed Weight
(#29) Walid Ben-Ameur, Harmender Gahlawat and Alessandro Maddaloni. Hunting a rabbit is hard
(#54) Hao Wu. A Nearly-$4\log n$ Depth Lower Bound for Formulas With Restriction on Top
(#171) Jinghui Xia and Zengfeng Huang. Optimal Framework for Clustering with Noisy Queries
18:30 - 20:30 Banquet

August 16th:

  • Time: 09:00 - 17:20
  • Venue: Main Venue
09:00 - 09:50 Invited Talk 3
Session Chair: TBD
Andrei Bulatov
The Complexity of CSP-Based Ideal Membership Problems
09:50 - 10:40 Invited Talk 4
Session Chair: TBD
Shang-Hua Teng
P+P ≧ PSPACE: Deep Logic, Strategic Losing, and Game Secrets
10:40 - 11:10 Coffee Break
11:10 - 12:10 Session 4: Economics and Computation I

Session Chair: TBD
(#77) Guanhao Li. Equivalence of Connected and Peak-Pit Maximal Condorcet Domains
(#82) Yaru Yang, Honglin Ding and Wentao He. Online Budget Allocation Maximization Problem on Two Uniform Machines with a Common Due Date
(#97) Yan Liu, Ying Qin and Zihe Wang. Simultaneous All-Pay Auctions with Budget Constraints
12:10 - 14:10 Lunch Break
14:10 - 15:50 Session 5: Computational Geometry

Session Chair: TBD
(#148) Sathish Govindarajan, Mayuresh Patle and Siddhartha Sarkar. Minimum Membership Geometric Set Cover in the Continuous Setting
(#174) Aleksa Džuklevski, Dömötör Pálvölgyi, Alexey Pokrovskiy, Csaba D. Tóth, Tomáš Valla and Lander Verlinde. Erdős-Szekeres Maker-Breaker Games
(#180) Bhavya Bansal, Raghunath Reddy Madireddy and Supantha Pandit. Minimum-Membership Geometric Dominating Set: Complexity and Algorithms
(#188) Minati De, Ratnadip Mandal and Satyam Singh. New Lower Bound and Algorithm for Online Geometric Hitting Set Problem
15:50 - 16:20 Coffee Break
16:20 - 17:20 Session 6: Graph Algorithms and Graph Theory I

Session Chair: TBD
(#20) Yaqiao Li. Undecidability of polynomial inequalities in subset densities and additive energies
(#194) Pan Peng and Kefan Yu. Testing Some First-Order Logic Properties on Sparse Graphs
(#12) Wen Xia, Jorik Jooken, Jan Goedgebeur, Iain Beaton, Ben Cameron and Shenwei Huang. Vertex-Critical $(P_5,W_4)$-Free Graphs
(#51) Xiaofei Liu and Weidong Li. Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints

August 17th:

  • Time: 09:00 - 17:40
  • Venue: Parallel Session Venue 1 & Parallel Session Venue 2
Parallel Session Venue 1 Parallel Session Venue 2
09:00 - 10:20 Session 7-I: Economics and Computation II

Session Chair: TBD
(#118) Yinghui Wen, Xin   Tong, Jiong Guo and Aizhong Zhou. Pareto   Optimal Matching with Multilayer Preferences: How Hard Can It Be? Session 7-II: Approximation Algorithms II

Session Chair: TBD
(#104) Ruiqing Sun. Bilevel adversarial   scheduling problem on parallel machines
(#31) Zhengyang Liu,   Haolin Lu, Liang Shan and Zihe Wang. On the Oscillations in Cournot Games with   Best Response Strategies (#142) Qinqin Gong,   Chunlin Hao, Donglei Du and Ruiqi Yang.Improved Approximation Algorithms   for Combinatorial Contracts with Type Constraints
(#59) Zheng Chen, Bin   Deng, Bo Li, Minming Li, Weidong Li and Guochuan Zhang. Fair and Efficient   Graphical Resource Allocation with Matching-Induced Utilities (#144) Qinqin Gong,   Zixuan Wang, Yang Lv and Ruiqi Yang. Approximation Algorithms for the Maximum   Connected Submodular Functions
(#61) Gennaro Auricchio,   Zeyu Ren, Zihe Wang and Jie Zhang. On the Distortion of Multi-winner Election   Using Single-Candidate Ballots (#62) Guangwei Wu,   Hongyun He, Guozhen Rong, Feng Shi and Yongjie Yang. On Online Approximation   Algorithms for Two-Stage Bins
10:20 - 10:50 Coffee Break
10:50 - 12:10 Session 8-I: String Algorithms and Discrete Structures I

Session Chair: TBD
(#32) Markus Lohrey and Andreas Rosowski. Finding cycle types in permutation groups with few generators Session 8-II: Learning and Data Related Theory I

Session Chair: TBD
(#179) Ting Liang, Xiaoliang Wu, Junyu Huang and Qilong Feng. Coresets for k-Median of Lines with Group Fairness Constraints
(#168) Wenfeng Lai, Haitao Jiang, Daming Zhu and Binhai Zhu. Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals (#34) Zichun Ye, Chihao Zhang and Jiahao Zhao. Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
(#81) Long-Shang Cho, Kai-Wei Chang and Chin Lung Lu. A Sparse Dynamic Programming Algorithm for Solving the Coding Sequence Design Problem (#95) Tingting Zhang, Yuan Yuan, Xiao Zhang, Yifei Zou, Zhipeng Cai and Dongxiao Yu. A Robust Distributed Minimax Learning Method against Model Poisoning Attacks
(#147) Tiantian Li, Siqi Jiang, Haitao Jiang and Daming Zhu. Longest Double-Bounded k-tuple Common Substrings
(#113) Siu-Wing Cheng and Man Ting Wong. A Dynamic Working Set Method for Compressed Sensing
12:10 - 14:10 Lunch Break
14:10 - 15:30 Session 9-I: Graph Algorithms and Graph Theory II

Session Chair: TBD
(#2) Yu Nakahata. Reconfiguring Multiple Connected Components with Size Multiset Constraints Session 9-II: Combinatorial Optimization

Session Chair: TBD
(#63) Yuxuan Wang, Yunhao   Li, Zhouxing Su, Junwen Ding, Qingyun Zhang and Zhipeng Lü. Adaptive Weighting-based Local Search for Route Number Minimization   for Vehicle Routing Problem with Time Windows
#183) Ruixi Luo, Taikun Zhu and Kai Jin. Sum-of-Max Chain Partition of a Tree (#109) Menghua Jiang, Rui   Zhang and Yin Chen. Improving Local Search for Weighted   Partial MaxSAT by Initializing with Historical Information
(#4) Chilei Wang, Qiang-Sheng Hua and Hai Jin. Massively Parallel Approximate Steiner Tree Algorithms (#115) Zhicheng Liu, Yang   Lv, Yapu Zhang and Zhenning Zhang. Regularized   Submodular Maximization over Integer Lattice
(#69) Yang Hu, Bo Ning and Xiumin Wang. A sufficient condition for the existence of two completely independent spanning trees (#202) Song Cao, Taikun   Zhu and Kai Jin. Discrete Effort Distribution via   Regrettable Greedy Algorithm
15:30 - 16:00 Coffee Break
16:00 - 17:20 Session 10-I: Graph Algorithms and Graph Theory III

Session Chair: TBD
(#39) Baohua Niu, Yan Wang, Baolei Cheng, Hai Liu, Bai Yin, Jianxi Fan and Xinyang Cai. Fault diagnosability evaluation of BCCC data center networks Session 10-II: Learning and Data Related Theory II
&
String Algorithms and Discrete Structures II

Session Chair: TBD
(#126) Yifei Wang, Jiayan Zhu, Yao Xu, Xin Li and Jiamou Liu. Redefining Entity Integration: Theoretical Insights for GNN-based Recommender Systems
(#140) Yuan Wang, Jianhang Sun, Zhipeng Lü, Zhouxing Su, Junwen Ding and Qingyun Zhang. A Multi-start Variable Neighborhood Tabu Search Algorithm for the Cyclic Bandwidth Problem (#7) Zizheng Guo, Jun Wu, Pengyu Chen, Yanzhang Fu and Dongjing Miao. Data Debugging is NP-hard for Classifiers Trained with SGD
(#15) Jianqi Zhou, Zhongyi Zhang and Jiong Guo. An FPT Factor-11 Approximation Algorithm for TSP (#71) Dongrun Cai, Xue Chen, Wenxuan Shu, Haoyu Wang and Guangyi Zou. Revisit the Partial Coloring Method: Prefix Spencer and Sampling
(#14) Jianqi Zhou, Zhongyi Zhang, Yinghui Wen and Jiong Guo. From Metric to General Graphs: FPT Constant-Factor Approximation Algorithms for Three Location Problems (#89) Eric Rivals and Pengfei Wang. Counting overlapping pairs of words
17:20 - 17:40 Closing