Sabyasachi Basu

Preprints

Retrieval Needs Multivectors: An Exponential Separation
Mihir Agarwal, Viraj Agrawal, Sabyasachi Basu, Ankit Garg, Kirankumar Shiragur arXiv (in submission)

Query-Limited Community Recovery in Stochastic Block Models
Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi arXiv (in submission)

EigenLI: Spectral Approximations to Late Interaction
Archish S, Sabyasachi Basu, Ankit Garg, Ravishankar Krishnaswamy, Kirankumar Shiragur (in submission)

Finding Many Overlapping Dense Subgraphs Using Triadic Cohorts

Sabyasachi Basu, C. Seshadhri arXiv 2026

Optimal storage codes on graphs with fixed locality
Sabyasachi Basu, Manuj Mukherjee arXiv 2023

Published/Accepted

Quantization Beyond Uniform Bit Allocation in Matryoshka Embeddings [VecDB '26]

K. S. Sreeramji, Sabyasachi Basu, Ravishankar Krishnaswamy, Kirankumar Shiragur, Yujia Wang OpenReview

Aggregating maximal cliques in real-world graphs [VLDB '26, PVLDB Vol 19 Issue 9]
Noga Alon, Sabyasachi Basu, Shweta Jain, Haim Kaplan, Jakub Łącki, Blair D. Sullivan arXiv, PVLDB

Density-Accuracy Tradeoffs in Real-World Graph Spanners [extended abstract in ACDA '25] Nadia Koshima*, Tim Rieder*, Sabyasachi Basu, Talya Eden, Omri Ben-Eliezer (2 page EA)

Covering maximal cliques in real-world graphs with dense subgraphs [extended abstract in ACDA '25] Sabyasachi Basu, Shweta Jain, Haim Kaplan, Jakub Łącki, Blair Sullivan (2 page EA)

A Sublinear Algorithm for Approximate Shortest Paths in Large Networks [WSDM '25]
Sabyasachi Basu, Nadia Koshima (equal contribution), Talya Eden, Omri Ben-Eliezer, C. Seshadhri arXiv

Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets [CIKM 2024]
Sabyasachi Basu, Daniel Paul-Pena (equal contribution), Kun Qian, C. Seshadhri, Eddie Huang, Karthik Subbian arXiv

Spectral Triadic Decompositions of Real-World Networks [SIAM Journal on Mathematics of Data Science, 2024]

Sabyasachi Basu, Suman Kalyan Bera, C. Seshadhri arXiv

A version of the theoretical analysis is on the UCSC website as a technical report

The complexity of testing all properties of planar graphs, and the role of isomorphism [SODA 22]

Sabyasachi Basu, Akash Kumar, C. Seshadhri ECCC arXivHighlighted in Oded's choices

Google Sites

Report abuse

Preprints

Retrieval Needs Multivectors: An Exponential SeparationMihir Agarwal, Viraj Agrawal, Sabyasachi Basu, Ankit Garg, Kirankumar Shiragur arXiv (in submission)

Query-Limited Community Recovery in Stochastic Block ModelsSabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi arXiv (in submission)

EigenLI: Spectral Approximations to Late Interaction Archish S, Sabyasachi Basu, Ankit Garg, Ravishankar Krishnaswamy, Kirankumar Shiragur (in submission)