BASICS 2026 新春学术研讨会

We shall provide a finer analysis of 2-dimensional walks admitted by 2-VASSes. The new characterization is useful in providing tighter upper bound for the shortest paths in 2-VASSes.

The CFI-graphs, named after Cai, Fuerer, and Immerman, are central to the study of the graph isomorphism testing and of fixed-point logic with counting. They are colored graphs, and the coloring plays a role in many of their applications. As usual, it is not hard to remove the coloring by some extra graph gadgets, but at the cost of blowing up the size of the graphs and changing some parameters of them as well.

Since their introduction, it has been shown that certain uncolored variants of CFI-graphs serve the same purposes as the original colored graphs. We prove that this in fact remains true for the graphs obtained by simply forgetting the colors from the original CFI-graphs. To establish this, we provide a systematic analysis of the automorphism groups of the uncolored CFI-graphs. Furthermore, using the linear-algebraic framework introduced by Roberson, we investigate homomorphism counts on these graphs.

Joint work with Joerg Flum (Freiburg) and Mingjun Liu (Regensburg)

In the era of big data, massive datasets emerge in almost every application domain. Processing data in a traditional way, which takes at least time and space linear in the input size, becomes more-and-more commercially unaffordable. Important topics within sublinear algorithms include parallel computation (sublinear time), streaming algorithms (sublinear space), and communication complexity (sublinear communication), to name a few.

In this talk, I will investigate the above topics through the lens of two fundamental problems: graph connectivity and bipartite matching. For graph connectivity, I will start with the simplest possible parallel algorithm with running time \(O(\log n)\), then introduce the recent breakthroughs of how to break the \(O(\log n)\) barrier. I will also show how to achieve \(o(\log n)\) time and linear work, which is optimal. For bipartite matching, I will start with a simple approximate streaming algorithm whose correctness proof is based on combinatorial auctions, then I will introduce our recent work that finds the exact bipartite matching in the semi-streaming model that takes sublinear passes unless the graph is extremely dense.

本报告介绍一种基于路径统计的图查询基数估计框架 PathCE。该框架通过构建路径中心摘要图高效提取短路径统计信息，并将复杂图查询系统性地分解为更简单的子查询，从而以更少的迭代次数获得查询基数的上界估计。实验结果表明，PathCE 在估计精度、查询时延和摘要构建开销等方面均优于现有方法。最后，报告简要讨论在 PathCE 框架中融合谓词信息的方法，以进一步提升图数据库中带谓词查询的基数估计能力。

系统软件的复杂性导致整体验证难度极大，模块化的分治验证方法是降低验证难度的必要手段。现有的模块化程序验证方法存在多方问题，导致无法适用于实际系统软件验证。本报告介绍我们针对这些问题的一些探索和解决方法。

In this talk, I will briefly introduce my recent work on online scheduling problems. I will discuss how we have overcome theoretical barriers in classical scheduling models, as well as the intersection of online scheduling with economic perspectives and AI。

We study the approval-based multi-winner election problem where \(n\) voters jointly decide a committee of \(k\) winners from \(m\) candidates. We focus on the axiom \(\text{average justified representation}\) (AJR) proposed by Fernandez et al. (2017). AJR postulates that every group of voters with a common preference should be sufficiently represented in that their average satisfaction should be no less than their Hare quota.

Formally, for every group of \(\lceil \ell \cdot \frac{n}{k} \rceil\) voters with \(\ell\) common approved candidates, the average number of approved winners for this group should be at least \(\ell\). It is well-known that a winning committee satisfying AJR is not guaranteed to exist for all multi-winner election instances.

In this paper, we study the likelihood of the existence of AJR under the Erdős--Rényi model. We consider the Erdős--Rényi model parameterized by \(p \in [0,1]\) that samples instances where each voter approves each candidate with probability \(p\). We provide a clean and complete characterization of the existence of AJR committees in the case where \(m\) is a constant and \(n\) tends to infinity. We show that there are two phase transition points \(p_1\) and \(p_2\) (with \(p_1 \le p_2\)) for the parameter \(p\).

Vector addition systems are important computation models that are equivalent to Petri nets. In the line of work addressing the reachability problem of VASS, the concept of geometric dimension (the dimension of the vector space spanned by simple cycle effects) was found important to complexity analysis. It is reasonable to study the reachability problem under fixed geometric dimension but not fixed number of counters. In this talk, I will introduce our recent advances on geometrically 2-dimensional vector addition systems and its application to other VASS reachability problems.

The random k-SAT problem has attracted lots of attention in both computer science and statistical physics. The fundamental problem is to understand for what value of the clause density, a solution exists and can be found efficiently by an algorithm. While significant progress has been made toward the thresholds for satisfiability and solution search in recent years, this talk explores two deeper challenges: the problems of uniformly sampling solutions, and counting the number of them.

We present a near-linear-time almost uniform sampler when clause densities \(\alpha \lesssim 2^{k/3}\), and an efficient approximate counting algorithm that succeeds up to densities \(\alpha \le 2^k/\text{poly}(k)\). In particular, the \(2^k\) term matches the satisfiability and algorithmic threshold for random k-SAT formulae and extends beyond the \(2^{k/2}\) lower bound established for worst-case instances.