Our research focuses on research on many areas in theoretical computer science and mathematics, with a primary focus on logic, algorithms, computational complexity, mechanism design, algorithmic game theory and so on. The following is a list of interesting research areas for reference:
- Logic
- Computable Algebraic Systems and Model Theory
- Games on Finite Graphs
- Mechanism Design
- Exact and Parameterized Algorithms
- Graph Algorithms and Graph Theory
- Optimization and Heuristic Search
- Computational Social Choice
See some of our current topics and projects.
Publications
Our group is committed to publishing theoretical computer science-related results in prestigious journals and conferences, such as JACM, SIAM J. on Computing, Information and Computation, STOC, FOCS, SODA, LICS, AAAI, IJCAI, WWW, KDD, and so on.
Bakh won the best paper award in STOC 2017. In 2020, our group published about 20 papers in top journals and conferences.
Seminars
We will deliver the information on three types of seminars. All related people are welcomed.
- Chengdu A&L Seminars: A series of monthly held seminars organized by our group. We will invite experts from all over the world to report on a broad range of topics related to theoretical computer science.
- Weekly Seminars: A series of seminars that are mainly delivered by students and held weekly. It is often arranged as an open discussion.
- Other Seminars: We also deliver the information of some related seminars, some of which may be held by other organizers.
Research Areas
Below we also introduce some of our current topics and projects.
Topic 1: Games played on finite graphs
This is one of the important topics in model checking and verification in the last 20 or so years. The topic has deep connections to complexity theory, graph algorithms, and automata. The key task is to design an algorithm that, given a game specification in a given graph with opposing players, finds the winner of the game. There are many challenging and interesting questions in this area of research.
Topic 2: Automatic structures
A finite automaton is a simplest model of computation. The goal of this project is to use finite automata to represent infinite algebraic structures. A good example is the algebraic structure consisting of integers with the addition operation. When the integers are represented in binary, you can perform the addition operation by using only two states: the carry state and the non-carry state. In other words, a finite automaton with just two states suffices to represent the addition of all integers. One of the most challenging questions in the area is the following. Which structures admit finite automata representation? The area is among the cutting-edge research areas in logic and computer science. The area has deep connections with automata, computability, model checking, logic, and algebra.
Topic 3: Very large graphs and their properties
Nowadays networks with millions and many billion nodes can easily be found. Examples include social networks, various biological networks, and particle systems such as crystals. Understanding such large graphs is among the most challenging problems in many areas of computer science, mathematics, and other sciences. The project aims to develop a mathematical framework designed towards studying large graphs. One idea is the following. Suppose you have a very large graph G. A view of G is a graph G^{\prime} obtained from G by making G smaller. Obviously, there are (exponentially) many views of G. The question is how do you construct an appropriate view of G given that you want to find some particular properties or nodes of G? For instance, you might want to know if G is tree-like or path-like or if you want to find a center node of G. The project will address these and similar types of questions.
Topic 4: Computable structures
This is one of the key areas of modern computability and logic. What is a computable structure? What does it mean that two computable structures are similar? What does it mean for a graph or tree to be computable? These questions are hard and they have been addressed by famous experts in computability and logic. This project aims to develop the concept of computable Markov chains with a hope of a theory towards understanding infinite yet countable Markov chains with an eye toward computability. If successful, this project will connect computability with probability and algorithmic randomness.
Topic 5: Experimental Algorithms
Combinatorial optimization problems are ubiquitous in data mining, artificial intelligence, and database optimization. The theoretical aspects of many combinatorial problems have been studied for decades. In this project, we will turn to more practical matters of algorithms. Specifically, we study the design, analysis, implementation, optimization, profiling, and experimental evaluation of algorithms, in reality, aiming at bridging the gap between theory and practice. We are particularly interested in the experimental performance of algorithms with real-world input and running under constrained machine resources like limited cache, memory capacity, and core numbers. Currently, we focus on some fundamental \mathbf{NP}-hard problems like Clique, Steiner Tree, and Feedback Vertex/Arc Set problems.
Topic 6: Exact and Parameterized Algorithms
Under \mathbf{P} \neq \mathbf{NP}, no \mathbf{NP}-hard problems can be solved in polynomial time. Exact and parameterized algorithms study how fast we can solve \mathbf{NP}-hard problems within exponential running-time bounds. Most \mathbf{NP}-complete problems have a simple brute-force algorithm with a running-time bound \mathcal{O}^{*}(2^{n}). For some problems, we can solve them in \mathcal{O}^{*}(c^{n}) time for a constant c much smaller than 2, say 1.05. For some other problems, the best-known bounds are still \mathcal{O}^{*}(2^{n}), even after decades of effort. For parameterized algorithms, we want to design algorithms such that the exponential part of the running time is only related to some parameter, not the whole input size. So when the parameter is small, parameterized algorithms may be fast and practical, although they are still exponential. For example, the vertex cover problem can be solved in \mathcal{O}(1.2738^{k}+n^{2}), where k is the solution size and n is the number of vertices in the graph. When k<50 and n=3000, this algorithm is still very fast. Currently, we focus on SAT, Vertex Cover, Independent Set, Feedback Set, Dominating Set, TSP, and other basic \mathbf{NP}-hard problems.
Topic 7: Mechanism Design
Mechanism design (a subfield of microeconomics and game theory) can be thought of as the integrated use of game theory and social choice theory. It is interested in designing economic mechanisms, just like computer scientists are interested in designing algorithms, protocols, or systems. Because it goes backward from the end of the game, it is also called reverse game theory. It has important applications in economics and politics, such as market design, auction theory, and social choice theory. Currently, we focus on the following topics: extending auction mechanisms to social networks and designing mechanisms in crowdsourcing under network settings. Network setting is a new mechanism design setting where every player in the game is connected to other players. Our goal is to design appropriate mechanisms to encourage players already in the game to invite their neighbors to the auction, even if they are competing for the same resources.
Topic 8: Graph Theory and Graph Algorithms
We are interested in many graph problems. Here we highlight two research lines. One is about coloring and improper coloring problems. The other research line is about graph minor theory. We study treewidth, bidimensionality, and other theories and use them to design fast (sub-exponential) algorithms.
Topic 9: Voting
In a voting system, several agents give scores (or an ordering) to a set of candidates independently based on their own personal criteria. We will combine the individual scores (orders) to select a set of candidates, called a committee. It is a fundamental process integral to everything and intrinsic to our daily life. However, it is not so easy to find a satisfying committee. We study the criteria, algorithms, and computational complexity of elections.
Topic 10: Object Allocation
Object allocation is an essential and extremely studied topic in the fields of game theory, economics, social choice, and computer science, which is to assign a set of indivisible (or divisible) objects to a set of agents satisfying some requirements. With different settings and requirements, different models of object allocation have been proposed. One of the most important criteria is fairness. We hope the allocation satisfies some fairness criteria. Then different problems arise: How to set good fairness criteria? Does fair allocation always exist? How fast can we find fair allocations? How optimal are the fair allocations?