11 citations · 11 across the 2 of their papers we have counts for
3 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★ 11 cited
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…
cs.CC2016
Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
Chengyu Lin, Shengyu Zhang
The Sensitivity Conjecture and the Log-rank Conjecture are among the most important and challenging problems in concrete complexity. Incidentally, the Sensitivity Conjecture is kno…