• Mikhail Y. Kovalyov
    Professor
    United Institute of Informatics Problems, National Academy of Sciences of Belarus

    Title:

    A Little-Known Interpretation of Dynamic Programming


    Abstract:

    Dynamic programming (DP) is a common method for solving decision problems, along with complete enumeration, divide and conquer, branching methods (branch and bound, branch and cut), constraint programming, mathematical programming modeling, etc. We describe the classical key concepts and principles of DP with reference to their historical roots (the works of Andrey Markov and Richard Bellman). Then we present the general ideas of our interpretation of DP, which operates with the concepts of partial solutions, their states, and dominance relation. Our interpretation will be demonstrated using examples of the 0-1 knapsack problem, the dual bin packing problem, the shortest path problem, the traveling salesman problem, and batch scheduling problems. General methods for transforming DP into Fully Polynomial Time Approximation Scheme will be presented last.


    Bio:

    Mikhail Y. Kovalyov is a principal researcher in the United Institute of Informatics Problems (Minsk, Belarus) and corresponding member of the National Academy of Sciences of Belarus. He has contributed to the theory of fully polynomial time approximation schemes, scheduling, production research, computational complexity, algorithm design, logistics, bio-informatics. He has published in top Operational Research, Computer Science and Industrial Research journals. He serves on the editorial boards of Computers and Operations Research, European Journal of Operational Research, INFORMS Journal on Computing, Omega, OR Spectrum and Journal of Scheduling.


  • Jiangchuan Liu

    Professor

    School of Computing Science Simon Fraser University

    Title:

    Networked Live Video Analytics: From Design to Deployment


    Abstract:

    Live video analytics over wide-area networks have seen a wide range of applications, e,g., environment monitoring, industry automation, and self-driving, to name but a few. In this talk, based on our recent research and development experiences, I will discuss our works on the algorithm and system design in this field, from severless-based pipeline optimization, 360-degree video analytics, to streaming analytics over space networking. We will then discuss the challenges and solutions toward realworld deployment in remote ecosystems for wild salmon conservation.


    Bio:

    Jiangchuan Liu is a Full Professor in the School of Computing Science, Simon Fraser University, British Columbia, Canada. He is a Fellow of The Canadian Academy of Engineering, an IEEE Fellow, and an NSERC E.W.R. Steacie Memorial Fellow. In the past he worked as an Assistant Professor at The Chinese University of Hong Kong, a research fellow at Microsoft Research Asia, and an EMC-Endowed Visiting Chair Professor of Tsinghua University. He received the BEng degree (cum laude) from Tsinghua University, Beijing, China, in 1999, and the PhD degree from The Hong Kong University of Science and Technology in 2003, both in computer science. He is a co-recipient of the inaugural Test of Time Paper Award of IEEE INFOCOM (2015), ACM SIGMM TOMCCAP Nicolas D. Georganas Best Paper Award (2013), ACM Multimedia Best Paper Award (2012), and IEEE ICDCS Distinguished Paper Award (2024). His research interests include multimedia systems and networks, cloud and edge computing, social networking, online gaming, and Internet of things/RFID/backscatter. He has served on the editorial boards of IEEE/ACM Transactions on Networking, IEEE Transactions on Network Sciences and Engineering, IEEE Transactions on Big Data, IEEE Transactions on Multimedia, IEEE Communications Surveys and Tutorials, and IEEE Internet of Things Journal. He is a Steering Committee member of IEEE Transactions on Mobile Computing and Steering Committee Chair of IEEE/ACM IWQoS (2015-2017). He was TPC Co-Chair of IEEE INFOCOM'2021 and General Chair of INFOCOM'2024.


  • He Sun
    Reader
    School of Informatics
    University of Edinburgh

    Title:

    Spectral Clustering: Basics and Recent Advancements


    Abstract:

    Spectral clustering is one of the most fundamental clustering algorithms in computer science, and has comprehensive applications in machine learning, parallel and distributed computing, and data science. This talk will introduce the basics of spectral clustering, starting with its roots in spectral graph theory and its connection to eigenvalues and eigenvectors of graph Laplacians, and analyse its performance on real-world datasets.
    The second part of the talk will focus on recent advancements in spectral clustering, examining several new directions. I will discuss techniques for designing spectral clustering algorithms in dynamic settings, methods for uncovering more complex cluster structures in distributed environments, and the state-of-the-art for its efficient implementation. This discussion aims to bridge foundational knowledge with the latest developments, offering insights for both practitioners and researchers in theoretical computer science, machine learning, and distributed computing.


    Bio:

    He Sun is a Reader in the School of Informatics, University of Edinburgh. He received his PhD from Fudan University in 2010 and worked at the Max Planck Institute for Informatics (2010-2014), UC Berkeley (2014), and University of Bristol (2015-2017), before joining the University of Edinburgh in 2017. His research interests include algorithmic spectral graph theory, unsupervised learning, computational geometry, and randomised algorithms.
    He received the President's Medal of Fudan University (2004), Shanghai Outstanding PhD Thesis Award (2010), Simons-Berkeley Research Fellowship (2014), and has so far received research grants of about 2.5 million pounds from different research foundations and industrial partners. In 2020, he was awarded an EPSRC Fellowship of 1.5 million pounds for developing advanced spectral algorithms and their open-source implementation.