International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong


Invited Speakers

Young Faculty Forum in TCS

An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs

Pan Peng

University of Science and Technology of China

There are two fundamental property testing models for bounded-degree directed graphs: the bidirectional model in which the algorithms are allowed to query both the outgoing edges and incoming edges of a vertex, and the unidirectional model in which only queries to the outgoing edges are allowed. It has been known that for directed graphs with both maximum indegree and maximum outdegree upper bounded by $d$, any property that can be tested with query complexity $O_{\varepsilon,d}(1)$ in the bidirectional model can be tested with $n^{1-\Omega_{\varepsilon,d}(1)}$ queries in the unidirectional model. It was left open if this transformation can be further improved or there exists any property that exhibits such an extreme separation.
We prove that testing subgraph freeness in which the subgraph contains $k$ source components, requires $\Omega(n^{1-\frac{1}{k}})$ queries in the unidirectional model. This directly gives the first explicit properties that exhibit an $O_{\varepsilon,d}(1)$ vs $\Omega(n^{1-\varepsilon})$ separation of the query complexities between the bidirectional model and unidirectional model. Furthermore, our lower bound also resolves a conjecture on the query complexity of testing $k$-star freeness.
Joint work with Yuyang Wang.

Pan Peng is a faculty member in the School of Computer Science and Technology of University of Science and Technology of China (USTC). His research interests lie on the intersection between theoretical computer science, network science and data science. Currently, he is focused on the theory and application of graph algorithms and big data algorithms. He was a lecturer (assistant professor) in the Department of Computer Science at University of Sheffield. He has held assistant researcher position of Institute of Software, Chinese Academy of Sciences, and postdoc positions of TU Dortmund and University of Vienna. His research has been published in various top venues such as STOC, CCC, SODA, COLT, PODS, ICML, KDD etc.