4 papers
Fooling Thresholds of Halfspaces
Minglong Qin, Penghui Yao, Mingnan Zhao +1
We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of func…
A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
Penghui Yao, Mingnan Zhao
Developing explicit pseudorandom generators (PRGs) for prominent categories of Boolean functions is a key focus in computational complexity theory. In this paper, we investigate th…
On the complexity of proximal gradient and proximal gradient-Newton-CG methods for -regularized Optimization
Hong Zhu
In this paper, we propose two second-order methods for solving the \(\ell_1\)-regularized composite optimization problem, which are developed based on two distinct definitions of a…
Quantum Pseudorandom Scramblers
Chuhan Lu, Minglong Qin, Fang Song +2
Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state tha…