Keynote Speakers
Title: Complexity Dichotomies for Maximum Weighted Digraph Partition Problem and Valued Constraint Satisfaction Problem
Speaker: Gregory Gutin
(Professor, Royal Holloway University of London)
Abstract:
In the Maximum Weighted Digraph k-Partition problem (k-MWDP), given a digraph D in which every arc uv is assigned a positive rational weight c(uv) and a k*k-matrix M(uv) with rational entries, we aim at finding a k-partition \(V_1,...,V_k\) of vertices of D such that the sum \(\sum_{uv\in A(D)}c(uv)M(uv)_{p(u),p(v)}\) is maximised, where \(x\in V_{p(x)}\) for every vertex x in D. Let F be a set of k*k-matrices with rational entries. Then k-MWDP(F) is k-MWDP in which matrices assigned to arcs are restricted to matrices in F. We'll discuss complexity dichotomies (P vs NPh) obtained for k-MWDP(F), especially for k=2. The dichotomies have applications in algorithmic game theory, economics and graph theory, see [1,2,3]. While the original NP-hardness proofs for 2-MWDP dichotomies for general digraphs, oriented graphs, symmetric digraphs and bipartite digraphs were graph-theoretical (see [1,2] for the listed families of digraphs apart from bipartite digraphs), much shorter proofs can be obtained for them, apart from the bipartite digraphs, using dichotomies for the Valued Constraint Satisfaction Problem.
Joint work with A. Deligkas, E. Eiben, G. Gutin, P.R. Neary, G. Osipov, M. Wahlstrom and A. Yeo.
Joint work with A. Deligkas, E. Eiben, G. Gutin, P.R. Neary, G. Osipov, M. Wahlstrom and A. Yeo.
Bio:
Gregory Gutin is a professor of computer science at Royal Holloway University of London, UK and a distinguished professor at Nankai University, China. His main research interests include parameterized, polynomial, exact and approximation algorithms, graphs and combinatorics, information security, combinatorial optimization, and theoretical economics. He has published two editions of a monograph (translated into Chinese) and edited two books. He has over 300 papers, chapters and sections published or accepted for publication in refereed journals, conference proceedings and books. There are more than 13150 citations to his publications.
He studied for his PhD under Professor Noga Alon at the School of Mathematics, Tel Aviv University, Israel and received his PhD (with distinction) in 1993. Between 1993 and 1996 he held visiting positions in Odense University, Denmark and then became a lecturer of Mathematics at Brunel University, UK. In 1996 I was awarded the Kirkman Medal of International Institute of Combinatorics and Applications.
Since 1st September 2000, he has been Professor at Royal Holloway University of London. He held the Royal Society Wolfson Research Merit award in 2014-2018 and was elected to Academia Europaea in 2017 and to AAIA (Asia-Pacific Artificial Intelligence Association) in 2021. He received best paper awards at information security access control symposium ACM SACMAT in 2015, 2016, 2021 and 2022. In 2019 he was presented with Amity Global Academic Excellence Award and in 2022 with AAIA Outstanding Contribution Award. In April 2024 he was appointed to a position of distinguished professor at Nankai University for three years.
[1] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems, Proc. IJCAI 2023.
[2] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem, arXiv:2307.01109.
[3] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Some coordination problems are harder than others, arXiv:2311.03195.
He studied for his PhD under Professor Noga Alon at the School of Mathematics, Tel Aviv University, Israel and received his PhD (with distinction) in 1993. Between 1993 and 1996 he held visiting positions in Odense University, Denmark and then became a lecturer of Mathematics at Brunel University, UK. In 1996 I was awarded the Kirkman Medal of International Institute of Combinatorics and Applications.
Since 1st September 2000, he has been Professor at Royal Holloway University of London. He held the Royal Society Wolfson Research Merit award in 2014-2018 and was elected to Academia Europaea in 2017 and to AAIA (Asia-Pacific Artificial Intelligence Association) in 2021. He received best paper awards at information security access control symposium ACM SACMAT in 2015, 2016, 2021 and 2022. In 2019 he was presented with Amity Global Academic Excellence Award and in 2022 with AAIA Outstanding Contribution Award. In April 2024 he was appointed to a position of distinguished professor at Nankai University for three years.
[1] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems, Proc. IJCAI 2023.
[2] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem, arXiv:2307.01109.
[3] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Some coordination problems are harder than others, arXiv:2311.03195.
Title: A Bidding Game for Allocation of Indivisible Goods
Speaker: Uriel Feige
(Professor, The Weizmann Institute)
Abstract:
We consider allocation of indivisible goods to agents with possibly unequal entitlements, in a setting without payments. We shall briefly survey some fairness notions associated with such settings. Thereafter we shall present an allocation mechanism referred to as the bidding game. The mechanism satisfies natural procedural fairness criteria, and the question that we ask is to what extent the final allocation that it outputs satisfies ex-post fairness criteria. The ex-post fairness notion that we shall consider is that of the anyprice share (APS). For simple classes of valuation functions (unit demand, identical items), we show strategies for the agents that guarantee that in the bidding game they receive at least their APS. For other classes of valuation functions (additive, submodular), we show strategies that guarantee at least a handsome fraction of the APS. These results imply the existence of allocations that give agents a handsome fraction of the APS, and moreover, lead to polynomial time algorithms for finding such allocations.
Bio:
Uriel Feige is a professor at the Department of Computer Science and Applied Mathematics of the Weizmann Institute of Science. He also earned his Phd there. He conducted postdoctoral research at Princeton University and at the IBM T.J. Watson Research Center, and later spent a sabbatical at the Compaq Systems Research Center. In 2004-2007, he took leave from the Weizmann Institute to work with Microsoft Research’s Theory Group, and he later served as a part time consultant at Microsoft Research, Israel. His main research areas are algorithms, computational complexity, algorithmic game theory, with a recent focus on fair allocations. He served as Program Committee Chair for STOC (2007) and ICALP (2023, Track A). His work was recognized by some awards, including a Godel Award (2001), a SIAM Outstanding Paper Prize (2005), and a FOCS test of time award (2021).
Title: Industrial Internet of Things
Speaker: Liu Yunhao
(Professor, Tsinghua University)
Abstract:
We have passed the period of Digital-Follow-up（数字后行）, and now we are in Digital Twin （数字并行）, and trying to enter Digital-lead-off （数字先行） of Industrial Internet of Things (IIOT).
Bio:
Yunhao Liu is Professor at Automation Department and Dean of the GIX in Tsinghua University, ACM Fellow and IEEE Fellow. Yunhao received his BS degree in Automation Department from Tsinghua University, an MS and a Ph.D. degree in Computer Science and Engineering in Michigan State University. He is the Honorary Chair of ACM China.
Title: When Combinatorial Optimization Meets Quantum Computing
Speaker: My Thai
(Professor, University of Florida)
Abstract:
The intersection of Combinatorial Optimization (CO) and Quantum Computing (QC) presents a promising frontier for advancing both fields. This talk explores the synergistic potential of CO and QC, examining how each domain can significantly enhance the other. Our journey first delves into the application of CO techniques in optimizing quantum algorithms, which are crucial for the practical implementation of QC. CO methods can streamline quantum circuit design, improve qubit allocation, and enhance the efficiency of quantum annealing processes. Conversely, we investigate how QC can revolutionize CO by providing new computational paradigms that solve classical optimization problems more efficiently than traditional methods. Quantum algorithms such as Grover's and the Quantum Approximate Optimization Algorithm (QAOA) offer exponential speedups for specific CO problems, promising transformative impacts on various industrial sectors reliant on optimization. By bridging these two fields, this talk aims to highlight the mutual benefits and pave the way for innovative research and practical applications that harness the full potential of both CO and QC.
Bio:
Dr. Thai is currently a University of Florida (UF) Research Foundation Professor in the Department of Computer & Information Sciences & Engineering and Associate Director of UF Nelms Institute for the Connected World. She is a Fellow of IEEE.
Dr. Thai is a leading authority who has done transformative research in trustworthy machine learning and optimization, especially for complex systems with applications to healthcare, social media, critical networking infrastructure, and cybersecurity. She has been working on various interdisciplinary topics, focusing on the underlying mathematical models, coupled with efficient computational techniques for dynamic, interdependent, and uncertainty systems. She is internationally recognized for pioneering contributions to the modeling, design, and optimization of complex systems. The results of her work have led to 7 books and 350+ articles in highly ranked international journals and conferences, with significant impacts to the theory and practice of network science and machine learning, including several best paper awards.
In responding to a world-wide call of responsible and safety AI, she is a pioneer in designing deep explanations for black-box ML models, while defending against explanation-guided attacks, evidenced by her Distinguished Papers Award at the Association for the Advancement of Artificial Intelligence (AAAI) conference on AI, 2023. At the same year, she was also awarded a Web Science Trust Test-of-Time award, for her landmark work on combating misinformation in social media. In 2022, she received an IEEE Big Data Security Women of Achievement Award. In 2009, she was awarded the Young Investigator (YIP) from the Defense Threat Reduction Agency (DTRA) and in 2010, she won the NSF CAREER Award. She is presently the Editor-in-Chief of Springer Journal of Combinatorial Optimization and book series editor of Springer Optimization and Its Applications.
Dr. Thai is a leading authority who has done transformative research in trustworthy machine learning and optimization, especially for complex systems with applications to healthcare, social media, critical networking infrastructure, and cybersecurity. She has been working on various interdisciplinary topics, focusing on the underlying mathematical models, coupled with efficient computational techniques for dynamic, interdependent, and uncertainty systems. She is internationally recognized for pioneering contributions to the modeling, design, and optimization of complex systems. The results of her work have led to 7 books and 350+ articles in highly ranked international journals and conferences, with significant impacts to the theory and practice of network science and machine learning, including several best paper awards.
In responding to a world-wide call of responsible and safety AI, she is a pioneer in designing deep explanations for black-box ML models, while defending against explanation-guided attacks, evidenced by her Distinguished Papers Award at the Association for the Advancement of Artificial Intelligence (AAAI) conference on AI, 2023. At the same year, she was also awarded a Web Science Trust Test-of-Time award, for her landmark work on combating misinformation in social media. In 2022, she received an IEEE Big Data Security Women of Achievement Award. In 2009, she was awarded the Young Investigator (YIP) from the Defense Threat Reduction Agency (DTRA) and in 2010, she won the NSF CAREER Award. She is presently the Editor-in-Chief of Springer Journal of Combinatorial Optimization and book series editor of Springer Optimization and Its Applications.