1. Generalization bounds in non-i.i.d. learning:
While generalization bounds for batch learning algorithms are well-studied for the case when datasets are drawn in an i.i.d. fashion, generalization performance of learning algorithms with non-i.i.d. datasets have received less attention. Mohri and Rostamizadeh were able to derive generalization bounds for stable learning algorithms when the dataset is drawn from mixing processes. We have been able to remove this stability assumption needed by Mohri and Rostamizadeh by suitable employing the online-to-batch framework. Currently, we are exploring applying our generalization bounds to various learning scenarios.
2. Coding for interactive communication:
This is the field that I am working on at present. The classic work of Schulman introduced the problem of coding for interactive communication in presence of noise. Schulman showed that interactive coding of positive rates was indeed possible, and later, along with Rajagopalan, he showed that positive rate coding is also possible for interactive communication over networks. Since then the field has grown with research in various directions such as interactive capacity of various channels, effect of network topology on communication rates, interactive coding under various noise models such as adversarial noise, erasures, insertion-deletion, etc. My present research investigates effect of network topology on coding for multiparty interactive communication, interactive capacity of different standard channels, coding for interactive function computation, etc.
[JSAIT 21] [ITW 21][ISIT24a] [ISIT24b] [ISIT24c]
3. Output distributions of neural networks:
Neural network based generative models are used to generate i.i.d. samples from some unknown distribution. A question of interest is thus as follows: Given a neural network with an input seed from a pre-specified distribution, what is the minimum number of neurons needed to approximate samples from a target set of distributions? We studied this question for the scenario where the input distribution is uniform and the target set of distributions consists of the n-tiled histogram distributions on the unit cube.
4. Energy efficient channel sensing:
Communication in wireless sensor networks is bursty and sporadic. Always-on receivers can thus lead to a significant energy drain. A proposed solution to reduce the energy consumption in reception is to divide the receiver into two parts, a low powered wake-up receiver, and a high powered main receiver. The wake-up receiver periodically senses the channel to check if there is an incoming transmission, and switches on the main receiver if it decides that there is indeed an incoming transmission. My research involved designing a new low-powered channel sensing algorithm for the wake-up receiver. This algorithm builds upon the key observation that the device noise is the main contributor to the noise power in wireless sensor networks. The device noise power is inversely related to the power consumption at the receiver, and therefore a higher power consumption results in a cleaner channel and vice versa. The proposed new algorithm begins with an initial low-powered mode. If it decides that there is a transmission, the algorithm enters a second high-powered mode for confirmation. Carefully tuning the lengths and the power consumption of these two modes results in reduction of energy consumption by 30%-60% over existing channel sensing algorithms in practically relevant scenarios.
5. Communication complexity for secret key generation:
The main problem I looked at for my PhD thesis is characterizing the minimum rate of public discussion required by a set of terminals to agree on a secret key (SK) of maximum possible rate. This quantity was called the communication complexity of achieving SK capacity. While communication complexity turns out to be upper bounded by the minimum rate of communication for omniscience, a new lower bound on it was obtained, based on a multiterminal characterization of a variant of Wyner common information. It turns out that this bound is difficult to compute in general. For a special class of sources, called the hypergraphical sources, this bound is easy to compute, and can be shown to be loose for certain examples. Upper bounds, better than the minimum rate of communication for omniscience, have also been studied for the hypergraphical sources. Moreover, the instances when communication complexity equates minimum rate of communication for omniscience have been exactly characterized for the hypergraphical source. The communication complexity has been exactly characterized for a special class of hypergraphical sources, called the pairwise independent network (PIN) model. An alternate thread to this problem is characterizing the maximum rate of secret key that can be obtained using zero-rate communication, and it has been shown to be equal to a multiterminal extension of the Gács-Körner common information.
[ISIT 2014] [ISIT 2015] [Trans. IT 2016] [ISIT 2016] [ITW 2016] [ISIT 2017] [ISIT 2018] [Trans. IT 2018] [Trans. IT 2019]
6. Omnivocality for SK capacity:
Another aspect of communication for SK generation is the need of omnivocality for achieving SK capacity, i.e., a maximum rate SK. Omnivocality refers to the condition where all the terminals need to discuss. While it is well known from earlier results that omnivocality is never required for a two-terminal scenario, the fact no longer holds when three or more terminals are involved. A sufficient condition for omnivocality has been obtained for three or more terminals. It has also been shown that the said sufficient conditions is necessary for the particular case of exactly three terminals.
7. Fault tolerant SK generation:
A third problem I looked at for my PhD dissertation involved robust SK generation. The goal is to characterize the fault tolerant SK (FTSK) capacity when any arbitrary subset of terminals can drop out of the key generation protocol. While this is a difficult question which remains open till date, a simpler version of this problem restricted to a class of sources called PIN models on Harary graphs was considered. Even for this restricted class of sources, FTSK capacity is hard to evaluate exactly. However, upper and lower bounds on the FTSK capacity have been obtained.