Entropy Contractions in Markov Chains: Half-Step, Full-Step and Continuous-Time
Pietro Caputo, Zongchen Chen, Yuzhou Gu, Yury Polyanskiy
[arXiv version]
Tight Bounds for Noisy Computation of Threshold, Counting and Connectivity
Yuzhou Gu, Xin Li, Yinzhan Xu
Submitted
Exact condensation thresholds for NAE-SAT and the hypergraph stochastic block model
Yuzhou Gu
In preparation
Robust reconstruction on trees revisited
Yuzhou Gu, Yury Polyanskiy
In preparation
Log-concave Sampling over a Convex Body with a Barrier: a Robust and Unified Dikin Walk
Yuzhou Gu, Nikki Lijing Kuang, Yi-An Ma, Zhao Song, Lichen Zhang
Conference on Neural Information Processing Systems (NeurIPS) 2024
[arXiv version]
Community detection in the hypergraph stochastic block model and reconstruction on hypertrees
Yuzhou Gu, Aaradhya Pandey
Conference on Learning Theory (COLT) 2024
[conference version] [arXiv version]
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
Journal of Privacy and Confidentiality, 14(2), 2024
[journal version] [arXiv version]
Fast Sampling of \(b\)-Matchings and \(b\)-Edge Covers
Zongchen Chen, Yuzhou Gu
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024
[conference version] [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
International Conference on Learning Representations (ICLR) 2024
[conference version] [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]