Papers

Forthcoming
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Forthcoming. “Approximability of all finite CSPs in the dynamic streaming setting.” FOCS'21. ECCC Version
2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. 2021. “Approximability of all Boolean CSPs in the dynamic streaming setting”. ECCC Version
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. 2021. “Linear Space Streaming Lower Bounds for Approximating CSPs”. ECCC Version
Noah Singer, Madhu Sudan, and Santhoshini Velusamy. 2021. “Streaming approximation resistance of every ordering CSP.” APPROX'21. ECCC Version
2020
Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy. 2020. “Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes.” MFCS'20. Publisher's Version
Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. 2020. “Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT.” FOCS'20. arXiv Version
Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, and Santhoshini Velusamy. 2020. “Simple, Credible, and Approximately-Optimal Auctions.” EC'20. arXiv Version
2017
Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. 2017. “Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.” APPROX'17. Publisher's Version