Keynote Speakers

Some Recent Development in the Classification Program of Counting Problems

Abstract: First I will give an overview of some recent development in the complexity classification of counting problems. This is addressed in three successively more general frameworks: Graph homomorphisms (or vertex models), Counting constraint satisfaction problems (#CSP), and Holant problems. Then I will describe some complexity dichotomy theorems that classify every problem in a class into either polynomial-time computable ones, or #P-hard problems, depending on the specific constraint functions that define the problem. There are also complexity trichotomy theorems that carve out a broad class of problems that are #P-hard in general but solvable in polynomial-time on planar instances. These include Valiant's holographic reductions to Kasteleyn's algorithm for planar perfect matchings, and more. And many open problems still remain.

Optimal Mechanism Design: Simplicity and Robustness

Abstract: Mechanism design is a central topic of microeconomics. We focus on revenue maximizing auctions in this talk. We will first introduce the celebrated Myerson’s optimal auction and discuss the assumptions made by Myerson. We motivate the mechanism design problem of relaxing the assumptions and discuss some of the exciting work regarding the simplicity and robustness of auctions.
This talk is based on the following joint works:
• Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, Tao Xiao: Tight approximation ratio of anonymous pricing. STOC 2019
• Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, Tao Xiao: Tight Revenue Gaps among Simple Mechanisms. SODA 2019
• Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang: Correlation-Robust Analysis of Single Item Auction. SODA 2019
• Nick Gravin, Pinyan Lu: Separation in Correlation-Robust Monopolist Problem with Budget. SODA 2018

ALGORAND----The Truly Distributed Blockchain

Abstract: In its ideal model, a blockchain consists of a digital ledger of unalterable data, readable by everyone, to which every everyone can add new data. If adequately implemented, this model stands to revolutionize the way societies and traditional economies operate. By removing costly intermediaries and introducing new paradigms of trust, the model makes traditional transactions (e.g., payments) more efficient, and totally new ways of transacting (e.g., smart contracts) possible.
Unfortunately, as currently implemented, most blockchains cannot achieve their enormous potential. We shall argue, however, that they can be adequately implemented by means of dramatically different approaches.

Multi-Agent Learning

Abstract:Multi-agent learning arises in a variety of domains where intelligent agents interact not only with the (unknown) environment but also with each other. It has an increasing number of applications ranging from controlling a group of autonomous vehicles/robots/drones to coordinating collaborative bots in production lines, optimising distributed sensor networks/traffic, and machine bidding in competitive e-commerce and financial markets, just to name a few.

Yet, the non-stationary nature calls for new theory that brings interactions into the learning process. In this talk, I shall provide an up-to-date introduction on the theory and methods of multi-agent AI, with a focus on competition, collaboration, and communications among intelligent agents. The studies in both game theory and machine learning will be examined in a unified treatment. I shall also sample our recent work on the subject including mean-field multiagent reinforcement learning, stochastic potential games, and solution concepts beyond Nash-equilibrium.

Some Open Problems in Decision Tree Complexity

Abstract: Decision tree is a simple but important computational model for Boolean functions. Decision tree complexity has been a widely studied subarea in computational complexity. In this talk, beside some basic concepts and models in decision tree complexity, I will mainly introduce some open problems and survey their recent progress, including the proof of sensitivity conjecture and quantum evasiveness conjecture.

Model-Checking Quantum Markov Chains

Abstract: Model-checking is one of the dominant techniques for verification of computer (hardware and software) systems. It automatically checks whether a desired property is satisfied by a system. The properties that are checked are usually specified in a logic, in particular, temporal logic; typical properties are deadlock freedom, invariants, safety, request-response properties. The systems under checking are mathematically modelled as e.g. (finite-state) automata, transition systems, Markov chains and Markov decision processes.
In this talk, I'll discuss the essential difficulties in developing model-checking techniques for quantum systems that are never present in model checking classical systems, and review a new line of researches pursued by the author and their collaborators on checking general quantum systems modelled as quantum Markov chains, including quantum computing and communication hardware and software.