2 papers
cs.CC2025
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain +1
There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closene…
cs.DS2024
Fast White-Box Adversarial Streaming Without a Random Oracle
Ying Feng, Aayush Jain, David P. Woodruff
Recently, the question of adversarially robust streaming, where the stream is allowed to depend on the randomness of the streaming algorithm, has gained a lot of attention. In this…