4 papers
Minimum Number of Monochromatic Subgraphs of a Random Graph
Yatin Dandi, David Gamarnik, Haodong Zhu
We consider the problem of minimizing the number of monochromatic subgraphs of a random graph, when each node of the host graph is assigned one of the two colors. Using a recently…
Asymptotic size of the Karp-Sipser Core in Configuration Model
Arnab Chatterjee, Joon Hyung Lee, Haodong Zhu
We study the asymptotic size of the Karp-Sipser core in the configuration model with arbitrary degree distributions. The Karp-Sipser core is the induced subgraph obtained by iterat…
Asymptotic diameter of preferential attachment model
Hang Du, Shuyang Gong, Zhangsong Li +1
We study the asymptotic diameter of the preferential attachment model with parameters and . Building on the recent work \cite{VZ25…
Noisy Linear Group Testing: Exact Thresholds and Efficient Algorithms
Lukas Hintze, Lena Krieg, Olga Scheftelowitsch +1
In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective wi…