Santhoshini Velusamy

According to our database, Santhoshini Velusamy authored at least 21 papers between 2017 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Streaming approximation resistance of every ordering CSP.

Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

Comput. Complex., June, 2024

Sketching Approximability of All Finite CSPs.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

J. ACM, April, 2024

Efficient Location Sampling Algorithms for Road Networks.

Sara Ahmadian, Sreenivas Gollapudi, Kostas Kollias, Vivek Kumar, Ameya Velingker, Santhoshini Velusamy

Proceedings of the Companion Proceedings of the ACM on Web Conference 2024, 2024

2023

Fair allocation of a multiset of indivisible items.

Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

An Improved Lower Bound for Matroid Intersection Prophet Inequalities.

Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.

Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Multi-Item Nontruthful Auctions Achieve Good Revenue.

Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy

SIAM J. Comput., 2022

Streaming beyond sketching for Maximum Directed Cut.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Streaming complexity of CSPs with randomly ordered constraints.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Sketching Approximability of (Weak) Monarchy Predicates.

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

On sketching approximations for symmetric Boolean CSPs.

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

2021

Linear Space Streaming Lower Bounds for Approximating CSPs.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Approximability of all finite CSPs in the dynamic streaming setting.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Classification of the streaming approximability of Boolean CSPs.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs.

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

CoRR, 2021

Approximability of all finite CSPs with linear sketches.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Optimal Streaming Approximations for all Boolean Max-2CSPs.

Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy

CoRR, 2020

Simple, Credible, and Approximately-Optimal Auctions.

Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy

Proceedings of the EC '20: The 21st ACM Conference on Economics and Computation, 2020

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes.

Palash Dey, Jaikumar Radhakrishnan, Santhoshini Velusamy

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat.

Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2017

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.

Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy

Proceedings of the Approximation, 2017