24 citations · 26 across the 3 of their papers we have counts for
6 papers
A Hyperbolic Extension of Kadison-Singer Type Results
Ruizhe Zhang, Xinzhi Zhang
In 2013, Marcus, Spielman, and Srivastava resolved the famous Kadison-Singer conjecture. It states that for independent random vectors that have expected squa…
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts, Yin Tat Lee, Xinzhi Zhang
The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic.…
An Improved Approximation Algorithm for the Minimum -Edge Connected Multi-Subgraph Problem
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan +1
We give a randomized -approximation algorithm for the minimum -edge connected spanning multi-subgraph problem, -ECSM.
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…