Non-linear log-Sobolev inequalities for the Potts channel with applications to reconstruction problems
Yuzhou Gu, Yury Polyanskiy
Communications in Mathematical Physics, 404(2):769–831, 2023
[journal version] [arXiv version]
Generalized Rainbow Differential Privacy
Yuzhou Gu, Ziqi Zhou, Onur Günlü, Rafael G. L. D'Oliveira, Parastoo Sadeghi, Muriel Médard, Rafael F. Schaefer
[arXiv version]
Fast Sampling of \(b\)-Matchings and \(b\)-Edge Covers
Zongchen Chen, Yuzhou Gu
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024
[arXiv version]
Weak Recovery Threshold for the Hypergraph Stochastic Block Model
Yuzhou Gu, Yury Polyanskiy
Conference on Learning Theory (COLT) 2023
[conference version] [arXiv version]
Uniqueness of BP fixed point for the Potts model and applications to community detection
Yuzhou Gu, Yury Polyanskiy
Conference on Learning Theory (COLT) 2023
[conference version] [arXiv version]
Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Yuzhou Gu, Zhao Song, Lichen Zhang
[arXiv version]
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang
[arXiv version]
A Faster Small Treewidth SDP Solver
Yuzhou Gu, Zhao Song
[arXiv version]
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
ACM Symposium on Theory of Computing (STOC) 2023
[conference version] [arXiv version]
Stochastic block model entropy and broadcasting on trees with survey
Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu, Yury Polyanskiy
Conference on Learning Theory (COLT) 2021
Best Student Paper Award
[conference version] [arXiv version]
Faster monotone min-plus product, range mode, and single source replacement paths
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu
International Colloquium on Automata, Languages and Programming (ICALP) 2021
[conference version] [arXiv version]
Broadcasting on trees near criticality
Yuzhou Gu, Hajir Roozbehani, Yury Polyanskiy
IEEE International Symposium on Information Theory (ISIT) 2020
[conference version] [arXiv version]
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson
Innovations in Theoretical Computer Science (ITCS) 2019
[conference version] [arXiv version]
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson
SIAM Journal on Computing (SICOMP), 49(3):465-496, 2020
[journal version]
Nearly optimal separation between partially and fully retroactive data structures
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2018
[conference version] [arXiv version]
Zero-error communication over adder MAC
Yuzhou Gu
[arXiv version]
Graph magnitude homology via algebraic Morse theory
Yuzhou Gu
[arXiv version]
Generalized equivariant model structure on \(\text{Cat}^I\)
Yuzhou Gu
[arXiv version]
Some results on reversible gate classes over non-binary alphabets
Yuzhou Gu
[arXiv version]