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
302017
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
272020
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
17*2022
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
162022
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 approximation resistance of every ordering CSP
N Singer, M Sudan, S Velusamy
arXiv preprint arXiv:2105.01782, 2021
112021
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
102023
Approximability of all Boolean CSPs with linear sketches
CN Chou, A Golovnev, M Sudan, S Velusamy
arXiv preprint arXiv:2102.12351, 2021
10*2021
On Sketching Approximations for Symmetric Boolean CSPs
J Boyland, M Hwang, T Prasad, N Singer, S Velusamy
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2022
8*2022
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
72023
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
5*2023
Sketching approximability of (weak) monarchy predicates
CN Chou, A Golovnev, A Shahrasbi, M Sudan, S Velusamy
arXiv preprint arXiv:2205.02345, 2022
52022
An improved lower bound for matroid intersection prophet inequalities
RR Saxena, S Velusamy, SM Weinberg
arXiv preprint arXiv:2209.05614, 2022
22022
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
12022
Elementary analysis of isolated zeroes of a polynomial system
M Bafna, M Sudan, S Velusamy, D Xiang
arXiv preprint arXiv:2102.00602, 2021
12021
Sketching approximability of all finite CSPs
CN Chou, A Golovnev, M Sudan, S Velusamy
Journal of the ACM, 2024
2024
Efficient Location Sampling Algorithms for Road Networks
S Ahmadian, K Kollias, A Velingker, S Gollapudi, V Kumar, S Velusamy
ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023
2023
Approximability of Constraint Satisfaction Problems in the Streaming Setting
S Velusamy
Harvard University, 2023
2023
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
P Dey, J Radhakrishnan, S Velusamy
45th International Symposium on Mathematical Foundations of Computer Science …, 2020
2020
The system can't perform the operation now. Try again later.
Articles 1–19