Sotabase

Career

· Research Assistant Professor, Toyota Technological Institute at Chicago2023–
· PhD Student, Harvard University2018–
· BTech(Hons.) and MTech in Computer Science (dual degree), IIT Madras2014–

Publications (32)

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2017
36
cited
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat
IEEE Annual Symposium on Foundations of Computer Science · 2020
33
cited
Fair allocation of a multiset of indivisible items
ACM-SIAM Symposium on Discrete Algorithms · 2022
24
cited
Linear space streaming lower bounds for approximating CSPs
Electron. Colloquium Comput. Complex. · 2021
21
cited
Sketching approximability of all finite CSPs
2021
18
cited
Streaming approximation resistance of every ordering CSP
Computational Complexity · 2021
14
cited
Streaming complexity of CSPs with randomly ordered constraints
Electron. Colloquium Comput. Complex. · 2022
13
cited
Simple, Credible, and Approximately-Optimal Auctions
ACM Conference on Economics and Computation · 2020
11
cited
Approximability of all Boolean CSPs with linear sketches
2021
10
cited
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
IEEE Annual Symposium on Foundations of Computer Science · 2022
10
cited
Sketching Approximability of (Weak) Monarchy Predicates
Electron. Colloquium Comput. Complex. · 2022
9
cited
Approximability of all Boolean CSPs in the dynamic streaming setting∗
2021
6
cited
Streaming Algorithms via Local Algorithms for Maximum Directed Cut
arXiv.org · 2024
6
cited
Approximability of all finite CSPs in the dynamic streaming setting
Electron. Colloquium Comput. Complex. · 2021
5
cited
Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs
arXiv.org · 2021
5
cited
Multi-Item Nontruthful Auctions Achieve Good Revenue
SIAM journal on computing (Print) · 2020
5
cited
On sketching approximations for symmetric Boolean CSPs
Electron. Colloquium Comput. Complex. · 2021
5
cited
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Information Technology Convergence and Services · 2022
3
cited
Classification of the streaming approximability of Boolean CSPs
Electron. Colloquium Comput. Complex. · 2021
2
cited
Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
arXiv.org · 2024
2
cited
Sotabase
Santhoshini Velusamy | Researcher Profile | Sotabase | Sotabase