6 papers
Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent
Yihang Sun, Huaijin Wang, Patrick Hayden +1
The Energy Conserving Descent (ECD) algorithm was recently proposed (De Luca & Silverstein, 2022) as a global non-convex optimization method. Unlike gradient descent, appropriately…
Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation
Yihang Sun, Guanyang Wang, Jose Blanchet
We study the estimation of repeatedly nested expectations (RNEs) with a constant horizon (number of nestings) using quantum computing. We propose a quantum algorithm that achieves…
Size of the largest sum-free subset of and
Saba Lepsveridze, Yihang Sun
We determine the density of the largest sum-free subset of the lattice cube for and . This solves a conjecture of Cameron and Aydinian in dime…
On the number of modes of Gaussian kernel density estimators
Borjan Geshkovski, Philippe Rigollet, Yihang Sun
We consider the Gaussian kernel density estimator with bandwidth $β^{-\frac12}$ of iid Gaussian samples. Using the Kac-Rice formula and an Edgeworth expansion, we prove that t…
Computation of Approximately Stable Committees in Approval-based Elections
Drew Gao, Yihang Sun, Jan Vondrák
Approval-based committee selection is a model of significant interest in social choice theory. In this model, we have a set of voters , a set of candidates $\mathcal{C…
Rainbow common graphs must be forests
Yihang Sun
We study the rainbow version of the graph commonness property: a graph is -rainbow common if the number of rainbow copies of (where all edges have distinct colors) in an…