4 papers
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…
Perfect Secret Key Generation for a class of Hypergraphical Sources
Manuj Mukherjee, Sagnik Chatterjee, Alhad Sethi
Nitinawarat and Narayan proposed a perfect secret key generation scheme for the so-called \emph{pairwise independent network (PIN) model} by exploiting the combinatorial properties…
Generalization Bounds for Dependent Data using Online-to-Batch Conversion
Sagnik Chatterjee, Manuj Mukherjee, Alhad Sethi
In this work, we upper bound the generalization error of batch learning algorithms trained on samples drawn from a mixing stochastic process (i.e., a dependent data source) both in…
Improved bounds on the interactive capacity via error pattern analysis
Mudit Aggarwal, Manuj Mukherjee
Any interactive protocol between a pair of parties can be reliably simulated in the presence of noise with a multiplicative overhead on the number of rounds (Schulman 1996). The re…