Backdoors can be realized as statistically natural latent directions in modern neural networks, achieving high attack success with negligible clean accuracy loss and resisting existing defenses.
Computational Lower Bounds for Sparse PCA
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite programming. We also prove that the statistical performance of this test cannot be strictly improved by any computationally efficient method. Our results can be viewed as complexity theoretic lower bounds conditionally on the assumptions that some instances of the planted clique problem cannot be solved in randomized polynomial time.
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
A randomized algorithm based on the basic SDP relaxation for sparse PCA achieves an approximation ratio bounded by the sparsity constant with high probability and O(log d) on average under a technical assumption satisfied for low-rank or exponentially decaying eigenvalue SDP solutions.
The low-degree likelihood ratio method predicts computational hardness of hypothesis testing problems, with new connections to spectral methods and a lower bound for tensor PCA.
citing papers explorer
-
Backdoor Channels Hidden in Latent Space: Cryptographic Undetectability in Modern Neural Networks
Backdoors can be realized as statistically natural latent directions in modern neural networks, achieving high attack success with negligible clean accuracy loss and resisting existing defenses.
-
A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
A randomized algorithm based on the basic SDP relaxation for sparse PCA achieves an approximation ratio bounded by the sparsity constant with high probability and O(log d) on average under a technical assumption satisfied for low-rank or exponentially decaying eigenvalue SDP solutions.
-
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
The low-degree likelihood ratio method predicts computational hardness of hypothesis testing problems, with new connections to spectral methods and a lower bound for tensor PCA.