Santhoshini Velusamy

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