11 papers
Simple Linear Corrections for Compression in Late Interaction
Mihir Agarwal, Sabyasachi Basu, Viraj Agrawal
Late-interaction (multi-vector) models represent documents using a set of token-level vectors, providing a middle ground between cross-encoders and dense encoders in terms of quali…
EigenLI: Spectral Approximations to Late Interaction
Archish S, Sabyasachi Basu, Ankit Garg +2
Late-interaction models such as ColBERT achieve strong effectiveness by representing each document with many token-level vectors, but this expressivity leads to large indexing cost…
Finding Many Overlapping Dense Subgraphs Using Triadic Cohorts
Sabyasachi Basu, C. Seshadhri
Graphs are a standard representation for data in the social sciences, cybersecurity, computer infrastructure, bioinformatics, and more. Typical real-world graphs are sparse, meanin…
Retrieval Needs Multivectors: An Exponential Separation
Mihir Agarwal, Viraj Agrawal, Sabyasachi Basu +2
Recent works have highlighted the expressive limitations of embedding based retrieval models through both theoretical analyses and challenging benchmarks such as LIMIT. While multi…
Quantization Beyond Uniform Bit Allocation
K. S. Sreeramji, Sabyasachi Basu, Ravishankar Krishnaswamy +2
Quantization is a fundamental technique to handle the growing sizes of embeddings generated by modern models. Existing quantization schemes are largely embedding agnostic and alloc…
Query-Limited Community Recovery in Stochastic Block Models
Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen +1
We study exact community recovery in the two-community stochastic block model on vertices under limited and noisy access to network data. The learner may query a noisy neighbor…
Aggregating maximal cliques in real-world graphs
Noga Alon, Sabyasachi Basu, Shweta Jain +3
Maximal clique enumeration is a fundamental graph mining task, but its utility is often limited by computational intractability and highly redundant output. To address these challe…
Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets
Sabyasachi Basu, Daniel Paul-Pena, Kun Qian +3
Graphs are a fundamental data structure used to represent relationships in domains as diverse as the social sciences, bioinformatics, cybersecurity, the Internet, and more. One of…
A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
Sabyasachi Basu, Nadia Kōshima, Talya Eden +2
Computing distances and finding shortest paths in massive real-world networks is a fundamental algorithmic task in network analysis. There are two main approaches to solving this t…
Spectral Triadic Decompositions of Real-World Networks
Sabyasachi Basu, Suman Kalyan Bera, C. Seshadhri
A fundamental problem in mathematics and network analysis is to find conditions under which a graph can be partitioned into smaller pieces. The most important tool for this partiti…
The complexity of testing all properties of planar graphs, and the role of isomorphism
Sabyasachi Basu, Akash Kumar, C. Seshadhri
Consider property testing on bounded degree graphs and let denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all prop…