Keynote Speakers

Title: Some Mathematical Problems in Quantum Circuit Synthesis and Optimization

Speaker: Xiaoming Sun, Chinese Academy of Sciences, China

Abstract:

Quantum circuits, which serve as a general mathematical model for describing quantum algorithms, have become one of the key research areas in the field of quantum computing. Currently, quantum computing has entered a new stage of Noisy Intermediate-Scale Quantum Systems (NISQ), in which the synthesis and optimization of quantum circuits have become particularly important. Similar to the complexity of classical circuits, the complexity of quantum circuits also focuses on the optimization of circuit size and depth, while the metrics of quantum circuits are more complex, involving the number of auxiliary qubits, the levels used, and many other aspects. In this report, we will discuss a series of mathematical problems and research progress involved in the optimization of quantum circuits, and explore the connections between these problems and some classic famous problems such as Babai's conjecture about the diameter of Kaley graphs, etc.

Title: On the Finite Character of Learnability: A Fundamental Theorem of Supervised Learning

Speaker: Shang-Hua Teng, University of Southern California, USA

Abstract:

Recent work on learning has yielded a striking result: the learnability of various problems can be undecidable, or independent of the standard ZFC axioms of set theory. Furthermore, the learnability of such problems can fail to be a property of finite character: informally, it cannot be detected by examining finite projections of the problem. On the other hand, learning theory abounds with notions of dimension that characterize learning and consider only finite restrictions of the problem, i.e., are properties of finite character. How can these results be reconciled? More precisely, which classes of learning problems are vulnerable to logical undecidability, and which are within the grasp of finite characterizations?

We demonstrate that the difficulty of supervised learning with metric losses admits a tight finite characterization. In particular, we prove that the sample complexity of learning a hypothesis class can be detected by examining its finite projections. For realizable and agnostic learning with respect to a wide class of proper loss functions, we demonstrate an exact compactness result: a class is learnable with a given sample complexity precisely when the same is true of all its finite projections. For realizable learning with improper loss functions, we show that exact compactness of sample complexity can fail, and provide matching upper and lower bounds of a factor of 2 on the extent to which such sample complexities can differ. We conjecture that larger gaps are possible for the agnostic case. At the heart of our technical work is a compactness result concerning assignments of variables that maintain a class of functions below a target value, which generalizes Hall's classic matching theorem and may be of independent interest.

Joint work with Julian Asilis, Siddartha Devic, Shaddin Dughmi, and Vatsal Sharan

Title: Lightweight Algorithms to Learning Solutions for Large-scale Maximization

Speaker: My T. Thai, University of Florida, USA

Abstract:

The landscape of large-scale maximization is rapidly evolving, demanding innovative data-driven approaches. Viral marketing stands as a prime example of this challenge, requiring strategies that transcend traditional combinatorial methods and embrace learning-based solutions. This keynote delves into the forefront of viral marketing optimization, exploring advanced algorithms that efficiently navigate the complexities of billion-scale networks. We begin with a (1-1/e)-approximation algorithm, enhanced with accelerated sampling frameworks, to offer near-exact solutions for this NP-hard problem. Expanding our scope to heterogeneous multiplex networks, we introduce combinatorial algorithms adept at capturing the intricate dynamics of overlapping user interactions. We further discuss a transformative framework designed to overcome fundamental obstacles inherent in traditional approaches, via the power of machine learning. Finally, the keynote concludes with MIM-Reasoner, which exploits the reinforcement learning with probabilistic graphical models to effectively tackle viral marketing challenges across diverse platforms.