Follow
Santhoshini Velusamy
Title
Cited by
Cited by
Year
Streaming complexity of approximating max 2csp and max acyclic subgraph
V Guruswami, A Velingker, S Velusamy
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2017
372017
Optimal streaming approximations for all boolean max-2csps and max-ksat
CN Chou, A Golovnev, S Velusamy
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
352020
Linear space streaming lower bounds for approximating CSPs
CN Chou, A Golovnev, M Sudan, A Velingker, S Velusamy
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing …, 2022
192022
Fair allocation of a multiset of indivisible items
P Gorantla, K Marwaha, S Velusamy
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023
182023
Approximability of all finite CSPs with linear sketches
CN Chou, A Golovnev, M Sudan, S Velusamy
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022
162022
Streaming approximation resistance of every ordering CSP
NG Singer, M Sudan, S Velusamy
computational complexity 33 (1), 6, 2024
142024
Simple, credible, and approximately-optimal auctions
C Daskalakis, M Fishelson, B Lucier, V Syrgkanis, S Velusamy
Proceedings of the 21st ACM Conference on Economics and Computation, 713-713, 2020
132020
Streaming complexity of CSPs with randomly ordered constraints
RR Saxena, N Singer, M Sudan, S Velusamy
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023
122023
Improved streaming algorithms for Maximum Directed Cut via smoothed snapshots
RR Saxena, NG Singer, M Sudan, S Velusamy
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS …, 2023
112023
On sketching approximations for symmetric Boolean CSPs
J Boyland, M Hwang, T Prasad, N Singer, S Velusamy
arXiv preprint arXiv:2112.06319, 2021
11*2021
Approximability of all Boolean CSPs with linear sketches
CN Chou, A Golovnev, M Sudan, S Velusamy
arXiv preprint arXiv:2102.12351, 2021
92021
Sketching approximability of (weak) monarchy predicates
CN Chou, A Golovnev, A Shahrasbi, M Sudan, S Velusamy
arXiv preprint arXiv:2205.02345, 2022
82022
Multi-Item Nontruthful Auctions Achieve Good Revenue
C Daskalakis, M Fishelson, B Lucier, V Syrgkanis, S Velusamy
SIAM Journal on Computing 51 (6), 1796-1838, 2022
32022
An improved lower bound for matroid intersection prophet inequalities
RR Saxena, S Velusamy, SM Weinberg
arXiv preprint arXiv:2209.05614, 2022
32022
Sketching approximability of all finite CSPs
CN Chou, A Golovnev, M Sudan, S Velusamy
Journal of the ACM 71 (2), 1-74, 2024
22024
Approximability of Constraint Satisfaction Problems in the Streaming Setting
S Velusamy
Harvard University, 2023
22023
Elementary analysis of isolated zeroes of a polynomial system
M Bafna, M Sudan, S Velusamy, D Xiang
arXiv preprint arXiv:2102.00602, 2021
12021
Streaming Algorithms via Local Algorithms for Maximum Directed Cut
RR Saxena, NG Singer, M Sudan, S Velusamy
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2025
2025
Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
S Hwang, NG Singer, S Velusamy
arXiv preprint arXiv:2411.12976, 2024
2024
Efficient Location Sampling Algorithms for Road Networks
S Ahmadian, S Gollapudi, K Kollias, V Kumar, A Velingker, S Velusamy
Companion Proceedings of the ACM on Web Conference 2024, 899-902, 2024
2024
The system can't perform the operation now. Try again later.
Articles 1–20