9 papers
Counting Triangles in Graph Streams with Repeatable and Forgettable Edges
Sourav Chakraborty, Debarshi Chanda, Arijit Ghosh +3
Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often con…
Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones
Ayoub Ghriss, Sourav Chakraborty
Linear attention promises constant-time recurrent inference but degrades sharply on associative recall. We formulate attention recall as a spherical-packing problem and introduce K…
Computing over Data Streams using Catalytic Space
Ripley Becker, Sourav Chakraborty, Debarshi Chanda +2
We introduce a streaming model with \emph{catalytic memory}, an auxiliary workspace that must be returned to its initial state at the end of the computation. We show that catalytic…
Flickering Multi-Armed Bandits
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1
We introduce Flickering Multi-Armed Bandits (FMAB) to model sequential decision-making in environments with changing action availability, where accessibility of the next action is…
A Unified Framework for Locality in Scalable MARL
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1
Scalable methods for networked multi-agent reinforcement learning let each agent plan using only a small neighborhood of the agent graph. This works only when the system is value-l…
Multi-Agent Lipschitz Bandits
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1
We study the decentralized multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space where hard collisions yield zero reward. Our objective is to…
Are Large Random Graphs Always Safe to Hide?
Sourav Chakraborty, Sujata Ghosh, Smiha Samanta
We discuss winning possibilities of players in various variants of cops and robber game played on large random graphs, a testbed for various kinds of network queries, search proble…
Assessing the Quality of Binomial Samplers: A Statistical Distance Framework
Uddalok Sarkar, Sourav Chakraborty, Kuldeep S. Meel
Randomized algorithms depend on accurate sampling from probability distributions, as their correctness and performance hinge on the quality of the generated samples. However, even…
Equivalence Testing: The Power of Bounded Adaptivity
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar +1
Equivalence testing, a fundamental problem in the field of distribution testing, seeks to infer if two unknown distributions on are the same or far apart in the total variati…