Fooling Gaussian PTFs via local hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2020年份
6被引次数
4顶会引用
摘要
We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d O(logd) · logn. All previous generators had a seed length with at least a 2 d dependence on d.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
引用它的顶会 Paper4
- Positive spectrahedra: invariance principles and pseudorandom generatorsSrinivasan Arunachalam, Penghui YaoSTOC 2022 · 被引用 4 次
- Detecting Low-Degree TruncationAnindya De, Huan Li, Shivam Nadimpalli, Rocco A. ServedioSTOC 2024 · 被引用 2 次
- PTF Testing Lower Bounds for Non-Gaussian Component AnalysisIlias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis PittasFOCS 2025 · 被引用 1 次
- Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFsIlias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu 等STOC 2024
相关 Paper
- Fooling polynomials using invariant theory*Harm Derksen, Emanuele ViolaFOCS 2022 · 被引用 2 次
- Fooling Constant-Depth Threshold Circuits (Extended Abstract)Pooya Hatami, William M. Hoza, Avishay Tal, Roei TellFOCS 2021 · 被引用 4 次
- Testably Learning Polynomial Threshold FunctionsLucas Slot, Stefan Tiegel, Manuel WiedmerNeurIPS 2024 · 被引用 13 次
- Algorithmic Thresholds for Refuting Random Polynomial SystemsJun-Ting Hsieh, Pravesh K. KothariSODA 2022 · 被引用 2 次
- Learning Polynomial Transformations via Generalized Tensor DecompositionsSitan Chen, Jerry Li, Yuanzhi Li, Anru R. ZhangSTOC 2023 · 被引用 2 次
