Faculty - Dashboard

@inproceedings{bib_On_t_2025, AUTHOR = {Ly, Hoang and Soljanin, Emina and Vadlamani, Lalitha }, TITLE = {On the Service Rate Region of Reed-Muller Codes}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2025}}

We study the Service Rate Region (SRR) of distributed storage systems that store data using Reed-Muller (RM) codes. We focus on systems where each server stores an RM codeword symbol, and each user aims to decode a single data symbol by accessing the servers storing one of the data symbol's recovery groups. The cumulative access rate to each server cannot exceed its given service rate. The SRR is a convex polytope comprising all achievable data access request rates. It represents a critical metric for evaluating system efficiency and scalability. We characterize recovery sets for data objects using the geometric properties of RM codes. This analysis reveals a connection between the RM code's recovery sets and minimumweight codewords in the dual RM code. Using these results, we derive explicit and tight bounds for the maximal achievable demand for individual data objects, which define the maximal simplex polytope within the service rate region.

@inproceedings{bib_An_U_2025, AUTHOR = {Rameshwar, V. Arvind and Vadlamani, Lalitha }, TITLE = {An Upper Bound on the Error Probability of Rpa Decoding of Reed-Muller Codes Over the Bsc}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2025}}

In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Key components of our analysis are explicit estimates of the error probability of maximum likelihood (ML) decoding of first-order RM codes and of the error probabilities during the aggregation phase of the RPA decoder. Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Our results allow us to show that for RM codes with blocklength N=2m, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in m.

@inproceedings{bib_On_Q_2025, AUTHOR = {Roy, Debadrito and Kolhe, Aryaman Manish and Vadlamani, Lalitha and Kashyap, Navin }, TITLE = {On Quantum Computation Using Bias-Preserving Gates}, BOOKTITLE = {Quantum Information Processing}. YEAR = {2025}}

Certain types of quantum computing platforms, such as those realized using Rydberg atoms or Kerr-cat qubits, are natively more susceptible to Pauli-Z noise than Pauli-X noise, or vice versa. On such hardware, it is useful to ensure that computations use only gates that maintain the Z-bias (or X-bias) in the noise. This is so that quantum error-correcting codes tailored for biased-noise models can be used to provide fault-tolerance on these platforms. In this paper, we follow up on the recent work of Fellous-Asiani et al. (npj Quantum Inf., 2025) in studying the structure and properties of bias-preserving gates. Our main contributions are threefold: (1) We give a novel characterization of Z-bias-preserving gates based on their decomposition as a linear combination of Pauli operators. (2) We show that any Z-bias-preserving gate can be approximated arbitrarily well using only gates from the set {X,R_z(theta),CNOT,CCNOT}, where theta is any irrational multiple of 2pi. (3) We prove, by drawing a connection with coherence resource theory, that any Z-bias-preserving logical operator acting on the logical qubits of a Calderbank-Shor-Steane (CSS) code can be realized by applying Z-bias-preserving gates on the physical qubits. Along the way, we also demonstrate that Z-bias-preserving gates are far from being universal for quantum computation.

@inproceedings{bib_On_t_2025, AUTHOR = {Prabhu, Jefrin Sharmitha and Vaishya, Abhinav and Bhatnagar, Shobhit and Kolhe, Aryaman Manish and Vadlamani, Lalitha and Kumar, P. Vijay }, TITLE = {On the Efficacy of the Peeling Decoder for the Quantum Expander Code}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2025}}

The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their errorcorrecting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.

@inproceedings{bib_Gene_2025, AUTHOR = {Chandana, Penukonda Naga and Srivastava, Tejas and Kurri, Gowtham Raghunath and Vadlamani, Lalitha }, TITLE = {Generalized Dual Discriminator GANs}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2025}}

Dual discriminator generative adversarial networks (D2 GANs) were introduced to mitigate the problem of mode collapse in generative adversarial networks. In D2 GANs, two discriminators are employed alongside a generator: one discriminator rewards high scores for samples from the true data distribution, while the other favors samples from the generator. In this work, we first introduce {dual discriminator α-GANs (D2 α-GANs)}, which combines the strengths of dual discriminators with the flexibility of a tunable loss function, α-loss. We further generalize this approach to arbitrary functions defined on positive reals, leading to a broader class of models we refer to as generalized dual discriminator generative adversarial networks. For each of these proposed models, we provide theoretical analysis and show that the associated min-max optimization reduces to the minimization of a linear combination of an f-divergence and a {reverse} f-divergence. This generalizes the known simplification for D2-GANs, where the objective reduces to a linear combination of the KL-divergence and the reverse KL-divergence. Finally, we perform experiments on 2D synthetic data and use multiple performance metrics to capture various advantages of our GANs.

@inproceedings{bib_On_D_2024, AUTHOR = {Rasagna, Chigullapally and Harshithanjani, Athi and Vadlamani, Lalitha and Karamchandani, Nikhil }, TITLE = {On Distributed Multi-User Secret Sharing with Multiple Secrets per User}, BOOKTITLE = {National Conference on Communications}. YEAR = {2024}}

We consider a distributed multi-user secret sharing setting consisting of a dealer, n storage nodes and m secrets where each user demands a t-subset of m secrets. The user downloads shares from the storage nodes based on the designed access structure and reconstructs its secrets. Earlier work in this setting dealt with the case of t = 1; in this work, we generalize it to natural numbers. We identify a necessary condition on the access structures to ensure weak secrecy. We also make a connection between the access structures for this problem and t-disjunct matrices. We apply various t-disjunct matrix constructions in this setting and compare their performance in terms of the number of storage nodes and communication complexity. We also derive bounds on the optimal communication complexity of a distributed secret sharing protocol. Finally, we characterize the capacity region of the DMUSS problem when the access structure is specified

@inproceedings{bib_On_t_2023, AUTHOR = {Harshithanjani, Athi and Rasagna, Chigullapally and Krishnan, Prasad and Vadlamani, Lalitha }, TITLE = {On the Structure of Higher Order MDS Codes}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2023}}

A code of length n is said to be (combinatorially) (ρ, L)-list decodable if the Hamming ball of radius ρn around any vector in the ambient space does not contain more than L codewords. We study a recently introduced class of higher order MDS codes, which are closely related (via duality) to codes that achieve a generalized Singleton bound for list decodability. For some ℓ ≥ 1, higher order MDS codes of length n, dimension k, and order ℓ are denoted as (n, k)-MDS(ℓ) codes. We present a number of results on the structure of these codes, identifying the ‘extend-ability’ of their parameters in various scenarios. Specifically, for some parameter regimes, we identify conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes, via various techniques. We believe that these results will aid in efficient constructions of higher order MDS codes. We also obtain a new field size upper bound for the existence of such codes, which arguably improves over the best known existing bound, in some parameter regimes. Due to space restrictions, the full version of this paper containing proofs of claims is made available in [1].

@inproceedings{bib_An_O_2023, AUTHOR = {Gadiraju, Divija Swetha and Vadlamani, Lalitha and Aggarwal, vaneet }, TITLE = {An Optimization Framework based on Deep Reinforcement Learning Approaches for Prism Blockchain}, BOOKTITLE = {IEEE Transactions Services Computing}. YEAR = {2023}}

Blockchains have proven to provide a high level of performance in terms of security and reliability for various applications like cryptocurrencies and Internet-of-Things (IoT). Prism is a recent blockchain algorithm that achieves the physical limit on throughput and latency without compromising security. In recent days, reinforcement learning approaches are investi- gated in traditional blockchains, to improve performance. In this work, we apply Deep Reinforcement Learning (DRL) to one of the promising blockchain protocols, Prism, to optimize its performance. We propose a Deep Reinforcement Learning- based Prism Blockchain (DRLPB) scheme which dynamically optimizes the parameters of the Prism blockchain and helps in achieving a better performance. In DRLPB, we apply two widely used DRL algorithms, Dueling Deep Q Networks (DDQN) and Proximal Policy Optimization (PPO). This work presents a novel approach to applying DDQN and PPO to a blockchain protocol and comparing the performance. The DRLPB scheme adapts the Prism blockchain parameters to enhance the number of votes upto 84% more than Prism, while still preserving the security and latency performance guarantees of Prism.

@inproceedings{bib_Maxi_2023, AUTHOR = {Shivakrishna, D and NAIR, AADITYA M and Vadlamani, Lalitha }, TITLE = {Maximally Recoverable Codes with Hierarchical Locality: Constructions and Field-Size Bounds}, BOOKTITLE = {IEEE Transactions on Information Theory}. YEAR = {2023}}

Maximally recoverable codes are a class of codes which recover from all potentially recoverable erasure patterns given the locality constraints of the code. In earlier works, these codes have been studied in the context of codes with locality. The notion of locality has been extended to hierarchical locality, which allows for locality to gradually increase in levels with the increase in the number of erasures. We consider the locality constraints imposed by codes with two-level hierarchical locality and define maximally recoverable codes with data-local and local hierarchical locality. We derive certain properties related to their punctured codes and minimum distance. We give a procedure to construct hierarchical data-local MRCs from hierarchical local MRCs. We provide a construction of hierarchical local MRCs for all parameters. We also give constructions of MRC with hierarchical locality for some parameters, whose field size is smaller than that of known constructions for general parameters. We also derive a field size lower bound on MRC with hierarchical locality.

@inproceedings{bib_On_G_2023, AUTHOR = {Sarmasarkar, Sahasrajit and Vadlamani, Lalitha and Karamchandani, Nikhil }, TITLE = {On Gradient Coding with Partial Recovery}, BOOKTITLE = {EEE Transactions on Communications}. YEAR = {2023}}

We consider a generalization of the recently proposed gradient coding framework where a large dataset is divided across n workers and each worker transmits to a master node one or more linear combinations of the gradients over the data subsets assigned to it. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of s straggler workers, we relax the goal of the master node to computing the sum of at least some α fraction of the gradients. The broad goal of our work is to study the optimal computation and communication load per worker for this approximate gradient coding framework. We begin by deriving a lower bound on the computation load of any feasible scheme and also propose a strategy which achieves this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in the number of workers n. We then restrict attention to schemes which utilize a number of data partitions equal to n and propose schemes based on cyclic assignment which have a lower communication load. When each worker transmits a single linear combination, we also prove lower bounds on the computation load of any scheme using n data partitions.

@inproceedings{bib_Some_2022, AUTHOR = {Shivakrishna, D and Vadlamani, Lalitha }, TITLE = {Some Results on Maximally Recoverable Codes with Locality and Hierarchical Locality}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2022}}

Codes with locality allow for efficient recovery from single node failures by minimizing the number of nodes accessed to repair a failed node. These codes can also be extended to handle multiple erasures. Codes with hierarchical locality are another extension of codes with locality, which offer multiple levels of locality as the number of erasures increase. Maximally recoverable codes (MRC) are a class of codes, which satisfy the locality property and in addition also recover from all information theoretically recoverable erasure patterns. In this work, we construct MRC with hierarchical locality based on generator matrices of linearized Reed-Solomon codes and the field size is better than the earlier known construction. We also give a random construction of MRC with hierarchical locality and characterize the field size required. Finally, we present sparse generator matrices for MRC with locality and also sparse and balanced generator matrices for MRC with locality parameter 2 for large set of parameters.

@inproceedings{bib_Prop_2022, AUTHOR = {Shivakrishna, D and Vadlamani, Lalitha }, TITLE = {Properties of Maximally Recoverable Product Codes and Higher Order MDS Codes}, BOOKTITLE = {National Conference on Communications}. YEAR = {2022}}

Product codes are a class of codes which have generator matrices as the tensor product of the component codes and the codeword itself can be represented as an (m × n) array, where the component codes themselves are referred to as the row and column codes. Maximally recoverable product codes (MRPCs) are a class of codes which can recover from all information theoretically recoverable erasure patterns, given the a column and b row constraints imposed by the code. In this work, we derive puncturing and shortening properties of maximally recoverable product codes. We give a sufficient condition to characterize a certain subclass of erasure patterns as correctable and another necessary condition to characterize another subclass of erasure patterns as not correctable. In an earlier work, higher order MDS codes denoted by MDS(l) have been defined in terms of generic matrices and these codes have been shown to be constituent row codes for maximally recoverable product codes for the case of a = 1. We derive a certain inclusion-exclusion type principle for characterizing the dimension of intersection spaces of generic matrices. Applying this, we formally derive a relation between MDS(3) codes and points/lines of the associated projective space.

@inproceedings{bib_On_R_2022, AUTHOR = {Gupta, Shreya and DEVI, BHOOPATIRAJU REKHA and Vadlamani, Lalitha }, TITLE = {On Rack-Aware Cooperative Regenerating Codes and Epsilon-MSCR Codes}, BOOKTITLE = {IEEE Journal on Selected Areas in Information Theory}. YEAR = {2022}}

In distributed storage systems, cooperative regener- ating codes tradeoff storage for repair bandwidth in the case of multiple node failures. In rack-aware distributed storage systems, there is no cost associated with transferring symbols within a rack. Hence, the repair bandwidth will only take into account cross-rack transfer. Rack-aware regenerating codes for the case of single node failures have been studied and their repair bandwidth tradeoff characterized. In this paper, we consider the frame- work of rack-aware cooperative regenerating codes for the case of multiple node failures where the node failures are uniformly distributed among a certain number of racks. We characterize the storage repair-bandwidth tradeoff as well as derive the minimum storage and minimum repair bandwidth points of the tradeoff. We also provide explicit constructions of minimum bandwidth rack-aware cooperative regenerating codes and minimum storage rack-aware cooperative regenerating codes for a large range of parameters. We also consider another extension of minimum stor- age cooperative regenerating codes, in which we design slightly sub-optimal cooperative regenerating codes with much lower sub- packetization. -MSR codes are a class of codes introduced to tradeoff sub-packetization level for a slight increase in the repair bandwidth for the case of single node failures. We introduce the framework of -MSCR codes which allow for a similar tradeoff for the case of multiple node failures. We present a construction of -MSCR codes, which can recover from two node failures, by concatenating a class of MSCR codes and scalar linear codes. We give a repair procedure to repair the -MSCR codes in the event of two node failures and calculate the repair bandwidth for the same. We characterize the increase in repair bandwidth incurred by the method in comparison with the optimal repair bandwidth. Finally, we show the subpacketization level of -MSCR codes scales logarithmically in the number of nodes.

@inproceedings{bib_Tamo_2022, AUTHOR = {Sasanka, Uppuluri Sri Surya and Vadlamani, Lalitha }, TITLE = {Tamo-Barg Codes with Efficient Local Repair}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2022}}

Reed-Solomon codes are polynomial evaluation codes and it has been shown that these can be efficiently repaired in the case of single node failures by considering the code symbols as vectors over a subfield and the helper nodes transfer multiple symbols over the subfield for repair. Tamo-Barg codes are a class of optimal LRCs which are also polynomial evaluation codes. These codes have Reed-Solomon codes as their local codes. In the case of single node failures, the repair takes place only within the local groups. In this paper, we address the question of whether the repair bandwidth within the local group can be further reduced by using the technique of Reed-Solomon repair. We give a construction based on cosets where the scheme requires lesser repair bandwidth than naive Reed-Solomon repair. We also give another construction based on optimal Reed-Solomon codes which achieve the cutset bound, where the Tamo-Barg codes are designed such that the local Reed-Solomon codes can be optimally repaired. We make the connection between these class of codes and the codes with local regeneration.

@inproceedings{bib_Clas_2021, AUTHOR = {Bhatia, Jyoti and Koorapati, Sagar and Cenkeramadd, Linga Reddy and Dayal, Aveen and Jha, Ajit and Vishvakarma, Santosh Kumar and Joshi, Soumya and Srinivas, M. B. and Yalavarthy, Phaneendra K. and Kumar, Abhinav and Vadlamani, Lalitha }, TITLE = {Classification of targets using statistical features from range fft of mmwave fmcw radars}, BOOKTITLE = {Electronics}. YEAR = {2021}}

Radars with mmWave frequency modulated continuous wave (FMCW) technology accu- rately estimate the range and velocity of targets in their field of view (FoV). The targeted angle of arrival (AoA) estimation can be improved by increasing receiving antennas or by using multiple- input multiple-output (MIMO). However, obtaining target features such as target type remains challenging. In this paper, we present a novel target classification method based on machine learning and features extracted from a range fast Fourier transform (FFT) profile by using mmWave FMCW Radars operating in the frequency range of 77–81 GHz. The measurements are carried out in a variety of realistic situations, including pedestrian, automotive, and unmanned aerial vehicle (UAV) (also known as drone). Peak, width, area, variance, and range are collected from range FFT profile peaks and fed into a machine learning model. In order to evaluate the performance, various light weight classification machine learning models such as logistic regression, Naive Bayes, support vector machine (SVM), and lightweight gradient boosting machine (GBM) are used. We demonstrate our findings by using outdoor measurements and achieve a classification accuracy of 95.6% by using LightGBM. The proposed method will be extremely useful in a wide range of applications, including cost-effective and dependable ground station traffic management and control systems for autonomous operations, and advanced driver-assistance systems (ADAS). The presented classifi- cation technique extends the potential of mmWave FMCW Radar beyond the detection of range, velocity, and AoA to classification. mmWave FMCW Radars will be more robust in computer vision, visual perception, and fully autonomous ground control and traffic management cyber-physical systems as a result of the added new feature.

@inproceedings{bib_Obje_2021, AUTHOR = {Bhatia, Jyoti and Dayal, Aveen and Jha, Ajit and Vishvakarma, Santosh K. and J, Soumya and Srinivas, M. B. and Yalavarthy, Phaneendra K. and Yalavarthy, Phaneendra K. and Vadlamani, Lalitha }, TITLE = {Object Classification Technique for mmWave FMCW Radars using Range-FFT Features}, BOOKTITLE = {International Conference on Communication Systems & Networks}. YEAR = {2021}}

In this article, we present a novel target classification technique by mmWave frequency modulated continuous wave (FMCW) Radars using the Machine Learning on raw data features obtained from range fast Fourier transform (FFT) plot. FFT plots are extracted from the measured raw data obtained with a Radar operating in the frequency range of 77 - 81 GHz. The features such as peak, width, area, standard deviation, and range on range FFT plot peaks are extracted and fed to a machine learning model. Two light weight classification models such as Logistic Regression, Naive Bayes are explored to assess the performance. Based on the results, we demonstrate and achieve an accuracy of 86.9% using Logistic Regression. The proposed technique will be highly useful for several applications in cost-effective and reliable ground station traffic management systems for autonomous systems. The end-to-end framework presented here, expands the capabilities of mmWave Radar beyond range detection to classification. The implications of this added functionalities will facilitate utilization of mmWave Radars in computer vision, object recognition, and towards fully autonomous traffic control and management systems.

@inproceedings{bib_A_Fi_2021, AUTHOR = {Shivakrishna, D. and NAIR, AADITYA M and Vadlamani, Lalitha }, TITLE = {A Field Size Bound and Constructions of Maximally Recoverable Codes with Hierarchical Locality}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2021}}

Codes with locality are a class of codes which minimize the number of nodes accessed to repair a failed node. These codes can be used to handle single and multiple erasures. In an extension, codes with hierarchical locality have been proposed, which offer multiple levels of locality as the number of erasure increase. Given the constraints imposed by locality, maximally recoverable codes (MRC) are a class of codes which allow for recoverability from all information theoretically recoverable erasure patterns. In this work, we consider MRC for the case of codes with hierarchical locality. We derive a field size lower bound on MRC with hierarchical locality. We also give constructions of MRC with hierarchical locality for some parameters, whose field size is smaller than that of earlier known constructions.

@inproceedings{bib_An_U_2021, AUTHOR = {Krishnan, Prasad and Natarajan, Lakshmi and Vadlamani, Lalitha }, TITLE = {An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2021}}

The problem of data exchange between multiple nodes with storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data Shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, and Coded Distributed Computing, can be seen as instances of this generic data exchange problem. Applying our generic converse, we can efficiently recover known important converses in these formulations. Further, for a generic coded caching problem with heterogeneous cache sizes at the clients with or without a central server, we obtain a new general converse, which subsumes some existing results. Finally we relate a “centralized” version of our bound to the known generalized independence number bound in index coding and discuss our bound’s tightness in this context.

@inproceedings{bib_Lear_2021, AUTHOR = {SHARMA, JAYANT and Vadlamani, Lalitha }, TITLE = {Learning to Decode Trellis Coded Modulation}, BOOKTITLE = {National Conference on Communications}. YEAR = {2021}}

Trellis coded modulation (TCM) is a technique combining modulation with coding using trellises designed with heuristic techniques that maximize the minimum Euclidean distance of a codebook. We propose a neural networks based decoder for decoding TCM. We show experiments with our decoder that suggest the use of Convolutional Neural Network (CNN) with Recurrent Neural Network (RNN) can improve decoding performance and provide justification for the same. We show the generalization capability of the decoder by training it with small block length and testing for larger block length. We also test our decoder for its performance on noise model unseen in the training. Index Terms—Trellis Coded Modulation, Neural Networks, Decoding

@inproceedings{bib_Secu_2021, AUTHOR = {Tiwari, Aayush and Vadlamani, Lalitha }, TITLE = {Secure Raptor Encoder and Decoder for Low Storage Blockchain}, BOOKTITLE = {International Conference on Communication Systems & Networks}. YEAR = {2021}}

In a blockchain network, full nodes aid in decentralization by validating incoming transactions and also by assisting new nodes who want to join the network. However, due to the high storage cost incurred by full nodes, the total number of full nodes in a system is falling. In order to curb this problem and maintain decentralization, a secure fountain code (SeF) approach has been proposed earlier, where a class of fountain codes known as LT codes have been used. In this paper, we present Secure Raptor Encoder and Decoder (S-RED) built on Raptor Codes, which in addition to reducing storage costs, also has constant decoding time with respect to k (number of input blocks). We also present error-resilient double-peeling decoder that can recover original blocks with a high probability, even under the presence of adversaries

@inproceedings{bib_An_U_2021, AUTHOR = {Krishnan, Prasad and Natarajan, Lakshmi and Vadlamani, Lalitha }, TITLE = {An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2021}}

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to ‘rebalance’ a storage cluster after some node failures occur.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

@inproceedings{bib_Loca_2020, AUTHOR = {Natarajan, Lakshmi Prasad and Krishnan, Prasad and Vadlamani, Lalitha and Dau, Hoang }, TITLE = {Locally Decodable Index Codes}, BOOKTITLE = {IEEE Transactions on Information Theory}. YEAR = {2020}}

An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality. Index Terms— Broadcast rate, directed cycle, index coding, linear codes, locally decodable codes, minrank.

@inproceedings{bib_Secu_2020, AUTHOR = {Gadiraju, Divija Swetha and Vadlamani, Lalitha and Aggarwal, Vaneet }, TITLE = {Secure Regenerating Codes for Reducing Storage and Bootstrap Costs in ShardedBlockchains}, BOOKTITLE = {International Conference on Blockchain}. YEAR = {2020}}

—Blockchain is a distributed ledger with wide applications. Due to the increasing storage requirement for blockchains, the computation can be afforded by only a few miners. Sharding has been proposed to scale blockchains so that storage and transaction efficiency of the blockchain improves at the cost of security guarantee. This paper aims to consider a new protocol, Secure-Repair-Blockchain (SRB), which aims to decrease the storage cost at the miners. In addition, SRB also decreases the bootstrapping cost, which allows for new miners to easily join a sharded blockchain. In order to reduce storage, coding-theoretic techniques are used in SRB. In order to decrease the amount of data that is transferred to the new node joining a shard, the concept of exact repair secure regenerating codes is used. The proposed blockchain protocol achieves lower storage than those that do not use coding, and achieves lower bootstrapping cost as compared to the different baselines

@inproceedings{bib_Code_2020, AUTHOR = {Krishnan, M. Nikhil and Vadlamani, Lalitha and Didugu, Sreeranjani }, TITLE = {Codes With Minimum Bandwidth Cooperative Local Regeneration}, BOOKTITLE = {IEEE Communications Letters}. YEAR = {2020}}

Locally recoverable codes (LRCs) are known to reduce the repair locality, i.e., the number of nodes accessed during node repair, in distributed storage systems. Regenerating codes, on the other hand, offer a decreased repair bandwidth, which is the repair traffic incurred during node repairs. Locally regenerating codes (LRGCs), which are constructed via intertwining regenerating codes of smaller block lengths, simultaneously offer a small repair locality and repair bandwidth. In this letter, we construct a family of LRGCs where the constituent codes are bandwidth-efficient, minimum bandwidth cooperative regenerating codes. The newly constructed LRGCs are optimal with respect to both minimum distance and rate.

@inproceedings{bib_Rack_2020, AUTHOR = {Gupta, Shreya and Vadlamani, Lalitha }, TITLE = {Rack-Aware Cooperative Regenerating Codes}, BOOKTITLE = {International Symposium on Information Theory and Its Applications}. YEAR = {2020}}

In distributed storage systems, cooperative regenerating codes tradeoff storage for repair bandwidth in the case of multiple node failures. In rack-aware distributed storage systems, there is no cost associated with transferring symbols within a rack. Hence, the repair bandwidth will only take into account cross-rack transfer. Rack-aware regenerating codes for the case of single node failures have been studied and their repair bandwidth tradeoff characterized. In this paper, we consider the framework of rack-aware cooperative regenerating codes for the case of multiple node failures where the node failures are uniformly distributed among a certain number of racks. We characterize the storage repair-bandwidth tradeoff as well as derive the minimum storage and minimum repair bandwidth points of the tradeoff. We also provide constructions of minimum bandwidth rack-aware cooperative regenerating codes for all parameters.

@inproceedings{bib_An_U_2020, AUTHOR = {Krishnan, Prasad and Natarajan, Lakshmi and Vadlamani, Lalitha }, TITLE = {An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing}, BOOKTITLE = {Technical Report}. YEAR = {2020}}

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to `rebalance' a storage cluster after some node failures occur. Finally we relate a `centralized' version of our bound to the known generalized independence number bound in index coding, and discuss our bound's tightness in this context.

@inproceedings{bib_Stra_2020, AUTHOR = {Sasi, Shanuja and Vadlamani, Lalitha and Aggarwal, Vaneet and Rajan, B. Sundar }, TITLE = {Straggler Mitigation with Tiered Gradient Codes }, BOOKTITLE = {EEE Transactions on Communications}. YEAR = {2020}}

Coding theoretic techniques have been proposed for synchronous Gradient Descent (GD) on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any k out of n servers finish their assigned tasks. The task size on each server is found based on the values of k and n. However, it is assumed that all the n jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with n1 ≥ k tasks, and on completion of c tasks, we start n2 – n1 more tasks. The aim is that as long as k servers can execute their tasks, the job gets completed. This paper exploits the flexibility that not all servers are started at the request time to obtain the achievable task sizes on each server. The task sizes are in general lower than starting all n2 tasks at the request times thus helping achieve lower task sizes which helps to reduce both the job completion time and the total server utilization.

@inproceedings{bib_On_t_2020, AUTHOR = {BHANDARI, MANAN and Bansal, Ishan and Vadlamani, Lalitha }, TITLE = {On the Polarizing Behavior and Scaling Exponent of Polar Codes with Product Kernels}, BOOKTITLE = {National Conference on Communications}. YEAR = {2020}}

Polar codes, introduced by Arikan, achieve the capacity of arbitrary binary-input discrete memoryless channel W under successive cancellation decoding. Any such channel having capacity I(W) and for any coding scheme allowing transmission at rate R, scaling exponent is a parameter which characterizes how fast gap to capacity decreases as a function of code length N for a fixed probability of error. The relation between them is given by N ≥ α/(I(W)-R) μ . Scaling exponent for kernels of small size up to L=8 have been exhaustively found. In this paper, we consider product kernels TL obtained by taking Kronecker product of component kernels. We derive the properties of polarizing product kernels relating to number of product kernels, self duality and partial distances in terms of the respective properties of the smaller component kernels. Subsequently, polarization behavior of component kernel Tl is used to calculate scaling exponent of TL=T2⊗Tl. Using this method, we show that μ(T2⊗T5)= 3.942. Further, we employ a heuristic approach to construct good kernel of L=14 from kernel having size l=8 having best μ and find μ(T2⊗T7)=3.485.

@inproceedings{bib_Code_2020, AUTHOR = {Krishnan, Prasad and Vadlamani, Lalitha and Natarajan, Lakshmi }, TITLE = {Coded Data Rebalancing: Fundamental Limits and Constructions}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2020}}

Distributed databases often suffer unequal distribution of data among storage nodes, which is known asdata skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and necessitatesrebalancing'at regular intervals to reduce the amount of skew. We define an -balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the -balanced property under node removal and addition operations. We present a class of -balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, ie, the databases designed for different number of storage nodes have the same structure. For this class of -balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, ie, it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

@inproceedings{bib_On_t_2019, AUTHOR = {BHANDARI, MANAN and Bansal, Ishan and Vadlamani, Lalitha }, TITLE = {On the Scaling Exponent of Polar Codes with Product Kernels}, BOOKTITLE = {Technical Report}. YEAR = {2019}}

Polar codes, introduced by Arikan, achieve the capacity of arbitrary binary-input discrete memoryless channel W under successive cancellation decoding. Any such channel having capacity I(W) and for any coding scheme allowing transmission at rate R, scaling exponent is a parameter which characterizes how fast gap to capacity decreases as a function of code length N for a fixed probability of error. The relation between them is given by N⩾α/(I(W)−R)μ. Scaling exponent for kernels of small size up to L=8 have been exhaustively found. In this paper, we consider product kernels TL obtained by taking Kronecker product of component kernels. We derive the properties of polarizing product kernels relating to number of product kernels, self duality and partial distances in terms of the respective properties of the smaller component kernels. Subsequently, polarization behavior of component kernel Tl is used to calculate scaling exponent of TL=T2⊗Tl. Using this method, we show that μ(T2⊗T5)=3.942. Further, we employ a heuristic approach to construct good kernel of L=14 from kernel having size l=8 having best μ and find μ(T2⊗T7)=3.485.

@inproceedings{bib_Maxi_2019, AUTHOR = {NAIR, AADITYA M and Vadlamani, Lalitha }, TITLE = {Maximally Recoverable Codes with Hierarchical Locality}, BOOKTITLE = {National Conference on Communications}. YEAR = {2019}}

Maximally recoverable codes are a class of codes which recover from all potentially recoverable erasure patterns given the locality constraints of the code. In earlier works, these codes have been studied in the context of codes with locality. The notion of locality has been extended to hierarchical locality, which allows for locality to gradually increase in levels with the increase in the number of erasures. We consider the locality constraints imposed by codes with two-level hierarchical locality and define maximally recoverable codes with data-local and local hierarchical locality. We derive certain properties related to their punctured codes and minimum distance. We give a procedure to construct hierarchical data-local MRCs from hierarchical local MRCs. We provide a construction of hierarchical local MRCs for all parameters. For the case of one global parity, we provide a different construction of hierarchical local MRC over a lower field size

@inproceedings{bib_On_E_2019, AUTHOR = {DEVI, BHOOPATIRAJU REKHA and Vadlamani, Lalitha }, TITLE = {On Epsilon-MSCR Codes for Two Erasures}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2019}}

Cooperative regenerating codes are regenerating codes designed to tradeoff storage for repair bandwidth in case of multiple node failures. Minimum storage cooperative regenerating (MSCR) codes are a class of cooperative regenerating codes which achieve the minimum storage point of the tradeoff. Recently, these codes have been constructed for all possible parameters (n, k, d, h), where h erasures are repaired by contacting any d surviving nodes. However, these constructions have very large sub-packetization. ε-MSR codes are a class of codes introduced to tradeoff subpacketization level for a slight increase in the repair bandwidth for the case of single node failures. We introduce the framework of ε-MSCR codes which allow for a similar tradeoff for the case of multiple node failures. We present a construction of ε-MSCR codes, which can recover from two node failures, by concatenating a class of MSCR codes and scalar linear codes. We give a repair procedure to repair the ε-MSCR codes in the event of two node failures and calculate the repair bandwidth for the same. We characterize the increase in repair bandwidth incurred by the method in comparison with the optimal repair bandwidth given by the cut-set bound. Finally, we show the subpacketization level of ε-MSCR codes scales logarithmically in the number of nodes

@inproceedings{bib_Loca_2019, AUTHOR = {Natarajan, Lakshmi and Dau, Hoang and Krishnan, Prasad and Vadlamani, Lalitha }, TITLE = {Locality in index coding for large min-rank}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2019}}

An index code is said to be locally decodable if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The locality of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off …

@inproceedings{bib_On_M_2018, AUTHOR = {Shivakrishna, D and Rameshwar, V. Arvind and Vadlamani, Lalitha and Sasidharan, Birenjith }, TITLE = {On Maximally Recoverable Codes for Product Topologies.}, BOOKTITLE = {National Conference on Communications}. YEAR = {2018}}

Given a topology of local parity-check constraints, a maximally recoverable code (MRC) can correct all erasure patterns that are information-theoretically correctable. In a grid-like topology, there are a local constraints in every column forming a column code, b local constraints in every row forming a row code, and h global constraints in an (m × n) grid of codeword. Recently, Gopalan et al. initiated the study of MRCs under grid-like topology, and derived a necessary and sufficient condition, termed as the regularity condition, for an erasure pattern to be recoverable when a = 1, h = 0. In this paper, we consider MRCs for product topology ( h = 0). First, we construct a certain bipartite graph based on the erasure pattern satisfying the regularity condition for product topology (any a, b, h = 0) and show that there exists a complete matching in this graph. We then present an alternate direct proof of the sufficient condition when a = 1, h = 0. We later extend our technique to study the topology for a = 2, h = 0, and characterize a subset of recoverable erasure patterns in that case. For both a = 1, 2, our method of proof is uniform, i.e., by constructing tensor product G col ⊗ G row of generator matrices of column and row codes such that certain square sub-matrices retain full rank. The full-rank condition is proved by resorting to the matching identified earlier and also another set of matchings in erasure sub-patterns.

@inproceedings{bib_On_l_2018, AUTHOR = {Natarajan, Lakshmi and Krishnan, Prasad and Vadlamani, Lalitha and Dau, Hoang }, TITLE = {On locally decodable index codes}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2018}}

Index coding for broadcast channels allows each receiver or client to retrieve its demanded message from its side information and the transmitted codeword. In general, a client may have to observe the entire codeword to decode its demanded message. However, downloading or querying the codeword symbols might involve costs at a client - such as network utilization costs and storage. Traditional index coding does not consider this client perspective, and as a result, for these codes the number of codeword symbols queried by a client per decoded message symbol, which we refer to as locality, could be large. In this paper we study a `client aware' approach to index coding by viewing the problem as a trade-off between the achievable broadcast rate and locality, where the objective is to minimize the rate for a given value of locality and vice versa. We first consider the minimum possible locality 1 and show that the …

@inproceedings{bib_Rate_2017, AUTHOR = {Vadlamani, Lalitha and Krishnan, Prasad }, TITLE = {Rate 1/3 index coding: Forbidden and feasible configurations }, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2017}}

Linear index coding can be formulated as an inter-ference alignment problem, in which precoding vectors of theminimum possible length are to be assigned to the messagesin such a way that the precoding vector of a demand (at somereceiver) is independent of the space of the interference (non side-information) precoding vectors. An index code has rate1lif theassigned vectors are of lengthl. In this paper, we introduce thenotion of strictly rate1Lmessage subsets which must necessarilybe allocated precoding vectors from a strictlyL-dimensionalspace (L=1,2,3) in any rate13code. We develop a generalnecessary condition for rate13feasibility using intersections ofstrictly rate1Lmessage subsets. We apply the necessary conditionto show that the presence of certain interference configurationsmakes the index coding problem rate13infeasible. We alsoobtain a class of index coding problems, containing certaininterference configurations, which are rate13feasible based on theidea ofcontractionsof an index coding problem. Our necessaryconditions for rate13feasibility and the class of rate13feasibleproblems obtained subsume all such known results for rate13index coding

@inproceedings{bib_Loca_2017, AUTHOR = {GUPTA, SNEH and Vadlamani, Lalitha }, TITLE = {Locality-Aware Hybrid Coded Map Reduce for Server-Rack Architecture}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2017}}

MapReduce is a widely used framework for distributed computing. Data shuffling between the Map phase and Reduce phase of a job involves a large amount of data transfer across servers, which in turn accounts for increase in job completion time. Recently, Coded MapReduce has been proposed to offer savings with respect to the communication cost incurred in data shuffling. This is achieved by creating coded multicast opportunities for shuffling through repeating Map tasks at multiple servers. We consider a server-rack architecture for MapReduce and in this architecture, propose to divide the total communication cost into two: intrarack communication cost and cross-rack communication cost. Having noted that cross-rack data transfer operates at lower speed as compared to intrarack data transfer, we present a scheme termed as Hybrid Coded MapReduce which results in lower cross-rack communication than Coded MapReduce at the cost of increase in intra-rack communication. In addition, we pose the problem of assigning Map tasks to servers to maximize data locality in the framework of Hybrid Coded MapReduce as a constrained integer optimization problem. We show through simulations that data locality can be improved considerably by using the solution of optimization to assign Map tasks to servers.

@inproceedings{bib_A_cl_2016, AUTHOR = {Krishnan, Prasad and Vadlamani, Lalitha }, TITLE = {A class of index coding problems with rate1/3}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2016}}

An index coding problem withn messages has symmetric rate R if all n messages can be conveyed at rate R. In a recent work, a class of index coding problems for which symmetric rate13is achievable was characterised using special properties of the side-information available at the receivers. In this paper, we show a larger class of index coding problems(which includes the previous class of problems) for which symmetric rate13is achievable. In the process, we also obtain a stricter necessary condition for rate13feasibility than what is known in literature.

@inproceedings{bib_Weig_2015, AUTHOR = {Vadlamani, Lalitha and Lokam, Satyanarayana V. }, TITLE = {Weight Enumerators and Higher Support Weights of Maximally Recoverable Codes}, BOOKTITLE = {Allerton Conference on Communication, Control, and Computing}. YEAR = {2015}}

A code is said to be data-local maximally recoverable if (i) all the information symbols have locality and (ii) any erasure pattern which can be potentially recovered (i.e., the number of equations is equal to the number of unknowns) is recovered by the code. A code is said to be local maximally recoverable if(i) all the symbols of the code have locality and (ii) from the above holds. In this paper, we establish the matroid structures corresponding to data-local and local maximally recoverable codes (MRC). The matroid structures of these codes can be used to determine the associated Tutte polynomial. Greene proved that the weight enumerators of any code can be determined from its associated Tutte polynomial. We will use this result to derive explicit expressions for the weight enumerators of data-local MRC. Also, Britz proved that the higher support weights of any code can be determined from its associated Tutte polynomial.We will use this result to derive expressions for the higher support weights of data-local and local MRC with two local codes.