59 citations · 104 across the 8 of their papers we have counts for
4 papers · 1 filter
Smoothed complexity of local Max-Cut and binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +2
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most , where is the number of nodes in the graph and is a…
Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang +1
This paper explores a theory of generalization for learning problems on product distributions, complementing the existing learning theories in the sense that it does not rely on an…
Settling the Sample Complexity of Single-parameter Revenue Maximization
Chenghao Guo, Zhiyi Huang, Xinzhi Zhang
This paper settles the sample complexity of single-parameter revenue maximization by showing matching upper and lower bounds, up to a poly-logarithmic factor, for all families of v…
Decomposition of symmetric multipartite observable
You Zhou, Chenghao Guo, Xiongfeng Ma
Production and verification of multipartite quantum state are an essential step in quantum information processing. In this work, we propose an efficient method to decompose symmetr…