2 papers
cs.CC2022
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
Zhihuai Chen, Siyao Guo, Qian Li +2
We show how to distinguish circuits with negations (a.k.a -monotone functions) from uniformly random functions in $\exp\left(\tilde{O}\left(n^{1/3}k^{2/3}\right)\right)…
cs.DS2018
Subspace Embedding and Linear Regression with Orlicz Norm
Alexandr Andoni, Chengyu Lin, Ying Sheng +2
We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function…