Santhoshini Velusamy

Publication Activity (10 Years)

Years Active: 2017-2024
Publications (10 Years): 39

Top Topics

Ordering Heuristics

Constraint Satisfaction Problems

Additively Separable

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of All Finite CSPs. J. ACM 71 (2) (2024)
Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. Comput. Complex. 33 (1) (2024)
Sara Ahmadian, Sreenivas Gollapudi, Kostas Kollias, Vivek Kumar, Ameya Velingker, Santhoshini Velusamy
Efficient Location Sampling Algorithms for Road Networks. WWW (Companion Volume) (2024)
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
An Improved Lower Bound for Matroid Intersection Prophet Inequalities. ITCS (2023)
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. FOCS (2023)
Pranay Gorantla, Santhoshini Velusamy
On the size of maximum cut in planar graphs. CoRR (2023)
Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
Fair allocation of a multiset of indivisible items. SODA (2023)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. SODA (2023)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. Electron. Colloquium Comput. Complex. (2022)
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming beyond sketching for Maximum Directed Cut. Electron. Colloquium Comput. Complex. (2022)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming beyond sketching for Maximum Directed Cut. CoRR (2022)
Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy
Multi-Item Nontruthful Auctions Achieve Good Revenue. SIAM J. Comput. 51 (6) (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. CoRR (2022)
Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
Fair allocation of a multiset of indivisible items. CoRR (2022)
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. Electron. Colloquium Comput. Complex. (2022)
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
An Improved Lower Bound for Matroid Intersection Prophet Inequalities. CoRR (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. APPROX/RANDOM (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. FOCS (2022)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. CoRR (2022)
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy
On Sketching Approximations for Symmetric Boolean CSPs. APPROX/RANDOM (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear space streaming lower bounds for approximating CSPs. STOC (2022)
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy
On sketching approximations for symmetric Boolean CSPs. Electron. Colloquium Comput. Complex. (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Classification of the streaming approximability of Boolean CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming Approximation Resistance of Every Ordering CSP. APPROX-RANDOM (2021)
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy
Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs. CoRR (2021)
Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. Electron. Colloquium Comput. Complex. 28 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs in the dynamic streaming setting. CoRR (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. FOCS (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Classification of the streaming approximability of Boolean CSPs. CoRR (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs in the dynamic streaming setting. Electron. Colloquium Comput. Complex. 28 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR (2021)
Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. CoRR (2021)
Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy
Simple, Credible, and Approximately-Optimal Auctions. EC (2020)
Palash Dey, Jaikumar Radhakrishnan, Santhoshini Velusamy
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. MFCS (2020)
Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy
Simple, Credible, and Approximately-Optimal Auctions. CoRR (2020)
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
Optimal Streaming Approximations for all Boolean Max-2CSPs. CoRR (2020)
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. FOCS (2020)
Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. APPROX-RANDOM (2017)