4 papers
On Differential Privacy for Adaptively Solving Search Problems via Sketching
Shiyuan Feng, Ying Feng, George Z. Li +3
Recently differential privacy has been used for a number of streaming, data structure, and dynamic graph problems as a means of hiding the internal randomness of the data structure…
Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
Yuzhou Gu, Nikki Lijing Kuang, Yi-An Ma +2
We consider the problem of sampling from a -dimensional log-concave distribution for -Lipschitz , constrained to a convex body with an efficient…
Streaming Semidefinite Programs: Passes, Small Space and Fast Runtime
Zhao Song, Mingquan Ye, Lichen Zhang
We study the problem of solving semidefinite programs (SDP) in the streaming model. Specifically, constraint matrices and a target matrix , all of size together…
A Nearly-Optimal Bound for Fast Regression with Guarantee
Zhao Song, Mingquan Ye, Junze Yin +1
Given a matrix and a vector , we consider the regression problem with guarantees: finding a vector $x'\in \mathbb{R}^…