Publications

Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy. "Streaming Algorithms via Local Algorithms for Maximum Directed Cut." SODA'25 arXiv

Santhoshini Velusamy and Huacheng Yu, "Optimal Streaming Algorithm for Detecting l2 Heavy Hitters in Random Ordered Streams." In preparation

Samuel Hwang, Noah Singer, and Santhoshini Velusamy, "Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds." In submission arXiv

Sara Ahmadian, Sreenivas Gollapudi, Kostas Kollias, Vivek Kumar, Ameya Velingker, and Santhoshini Velusamy, "Efficient Location Sampling Algorithms for Road Networks." WWW'24 Companion, ICML'23 workshop: Sampling and Optimization in Discrete Space, Publisher's version

Noah Singer, Madhu Sudan, and Santhoshini Velusamy. "Streaming Approximation Resistance of every Ordering CSP." Computational Complexity, 33(6), Publisher's version

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy, “Sketching Approximability of all Finite CSPs.” Journal of the ACM, 0004-5411, Publisher's version

Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy, “Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.” FOCS’23 arXiv

Raghuvansh R. Saxena, Santhoshini Velusamy, and Matthew S. Weinberg,  “An Improved Lower Bound for Matroid Intersection Prophet Inequalities.” ITCS'23 arXiv

Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy, “Streaming Complexity of CSPs with Randomly Ordered Constraints.” SODA'23 arXiv

Pranay Gorantla, Kunal Marwaha, and Santhoshini Velusamy, “Fair Allocation of a Multiset of Indivisible Items.” SODA'23 arXiv

Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, and Santhoshini Velusamy, “Multi-Item Nontruthful Auctions Achieve Good Revenue.” SIAM Journal on Computing, 51, 6. Publisher's version

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, and Santhoshini Velusamy, “Sketching Approximability of (Weak) Monarchy Predicates.” APPROX'22 arXiv

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy, “On Sketching Approximations for Symmetric Boolean CSPs.” APPROX'22 arXiv

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy, “Linear Space Streaming Lower Bounds for Approximating CSPs.” STOC'22 arXiv

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy, “Approximability of all Finite CSPs with Linear Sketches.” FOCS'21 arXiv

Noah Singer, Madhu Sudan, and Santhoshini Velusamy, “Streaming Approximation Resistance of every Ordering CSP.” APPROX'21 arXiv

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy, “Approximability of all Boolean CSPs with Linear Sketches.” arXiv

Mitali Bafna, Madhu Sudan, Santhoshini Velusamy, and David Xiang, "Elementary Analysis of Isolated Zeroes of a Polynomial System." arXiv

Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy, “Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT.” FOCS'20 arXiv

Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy, “Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes.” MFCS'20 Publisher's version

Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, and Santhoshini Velusamy, “Simple, Credible, and Approximately-Optimal Auctions.” EC'20 arXiv

Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy, “Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.” APPROX'17 Publisher's version