Abstract:
We consider a generalized poset sorting problem (GPS), in which we are given a query graph $G = (V, E)$ and an \emph{unknown poset} $\mathcal{P}(V, \prec)$ that is defined on the same vertex set $V$, and the goal is to make as few queries as possible to edges in $G$, in order to fully recover $\mathcal{P}$, where each query $(u, v)$ returns the relation between $u, v$, i.e., $u \prec v$, $v \prec u$ or $u \not \sim v$. This generalizes both the poset sorting problem [Faigle et al., SICOMP 88] and the generalized sorting problem [Huang et al., FOCS 11].
We give algorithms with $\tilde{O}(n \poly(k))$ query complexity when $G$ is a complete bipartite graph or $G$ is stochastic under the \ER model, where $k$ is the \emph{width} of the poset, and these generalize [Daskalakis et al., SICOMP 11] which only studies complete graph $G$. Both results are based on a unified framework that reduces the poset sorting to partitioning the vertices with respect to a given pivot element, which may be of independent interest.
Moreover, we also propose novel algorithms to implement this partition oracle. Notably, we suggest a randomized BFS with vertex skipping for the stochastic $G$, and it yields a nearly-tight bound even for the special case of generalized sorting (for stochastic $G$) which is comparable to the main result of a recent work [Kuszmaul et al., FOCS 21] but is conceptually different and simplified.
Our study of GPS also leads to a new $\tilde{O}(n^{1 - 1 / (2W)})$ competitive ratio for the so-called weighted generalized sorting problem where $W$ is the number of distinct weights in the query graph. This problem was considered as an open question in [Charikar et al., JCSS 02], and our result makes important progress as it yields the first nontrivial sublinear ratio for general weighted query graphs (for any bounded $W$). We obtain this via an $\tilde{O}(nk + n^{1.5})$ query complexity algorithm for the case where every edge in $G$ is guaranteed to be comparable in the poset, which generalizes a $\tilde{O}(n^{1.5})$ bound for generalized sorting [Huang et al., FOCS 11].
About the speaker:
Yuhao Zhang is an Associate Professor of John Hopcroft Center for Computer Science at Shanghai Jiao Tong University since 2021, working in the field of theoretical computer science. I obtained my Ph.D. (2016~2020) from the Department of Computer Science at the University of Hong Kong, Supervised by Dr. Zhiyi Huang. Before that, I got my B.E. from the College of Computer Science and Technology at Zhejiang University (2012~2016). During my undergraduate study, I started to be interested in theoretical computer science when I joined the research group of Prof. Guochuan Zhang.
My research focuses on Online Algorithms and Approximation Algorithms. I am dedicated to designing algorithms with provable guarantees for real-world applications and advancing general mathematical frameworks for analyzing their performance.