Faculty/ Prasad Krishnan
Prasad Krishnan
Assistant Professor
place
A3 - 217, Vindhya Building, Signal Processing and Communications Research Centre, International Institute of Information Technology Hyderabad (IIIT-H), Prof C.R.Rao Road, Gachibowli, Hyderabad, Telangana - 500032
language
language
language
B.Tulasi Sowjanya - (Active)
tulasi.sowjanya@research.iiit.ac.in
Chandan Anand - (Active)
chandan.anand@research.iiit.ac.in
Pramod Singh - (Active)
pramod.singh@research.iiit.ac.in
HARI HARA SUTHAN C - (Graduated)
hari.hara@research.iiit.ac.in
Srikar Kale- (Active)
srikar.kale@research.iiit.ac.in
Aditya Siddheshwar- (Active)
aditya.siddheshwar@research.iiit.ac.in
Jayesh Seshadri- (Active)
jayesh.seshadri@research.iiit.ac.in
VIJAYA KUMAR MAREEDU- (Graduated)
vijaya.kumar@research.iiit.ac.in
G VAMSI KRISHNA- (Graduated)
vamsi.gummadi@research.iiit.ac.in
ASHOK CHOUDHARY- (Graduated)
ashok.choudhary@research.iiit.ac.in
MAMILLAPALLI VENKATA NAGA BHAVANA- (Graduated)
bhavana.mvn@research.iiit.ac.in
Shailja Agrawal- (Graduated)
shailja.agrawal@research.iiit.ac.in
K V Sushena Sree- (Graduated)
sushena.sree@research.iiit.ac.in
Vayur Shanbhag- (Active)
vayur.s@research.iiit.ac.in
ASHUTOSH SHARMA- (Graduated)
ashutosh.sharma@research.iiit.ac.in
ISHANI- (Graduated)
chugh.ishani@research.iiit.ac.in
Visvesh S Subramanian- (Graduated)
visvesh.subramanian@research.iiit.ac.in
Vaishya Abhinav Rajeshkumar- (Graduated)
abhinav.vaishya@research.iiit.ac.in
Thota Venkata Aishwarya- (Graduated)
aishwarya.thota@students.iiit.ac.in
VIRIYALA RAJA RADHA KRISHNA- (Graduated)
radhakrishna.v@students.iiit.ac.in
Kadiyala Abhiram- (Graduated)
abhiram.kadiyala@students.iiit.ac.in
Annam Sai Deva Harsha- (Graduated)
sai.deva@students.iiit.ac.in
Voora Venkata Susheel- (Graduated)
venkata.susheel@students.iiit.ac.in
Abhishek Mittal- (Graduated)
abhishek.m@students.iiit.ac.in
Keshav Agarwal- (Graduated)
keshav.agarwal@students.iiit.ac.in
Teaching Courses
EC5.101 - Networks Signals and Systems
2024-25 - Monsoon
EC5.411 - Modern Coding Theory
2024-25 - Monsoon
CS8.502 - Topics in Information-Theoretic Privacy
2024-25 - Spring
EC5.410 - Information Theory
2023-24 - Monsoon
EC5.102 - Information and Communication
2023-24 - Spring
EC5.205 - Introduction to Coding Theory
2023-24 - Spring
CS8.502 - Topics in Information-Theoretic Privacy
2023-24 - Spring
EC5.411 - Modern Coding Theory
2022-23 - Monsoon
EC5.102 - Information and Communication
2022-23 - Spring
EC2.202a - Electronics Workshop II
2022-23 - Spring
CS1.502 - Information-Theoretic Methods in Computer Science
2022-23 - Spring
EC5.205 - Introduction to Coding Theory
2021-22 - Spring
ECE537 - Topics in Coding Theory
2020-21 - Spring
EC5.102 - Information and Communication
2020-21 - Spring
MA6.102 - Probability and Random Processes
2019-20 - Monsoon
MA2.101 - Linear Algebra
2019-20 - Spring
EC5.205 - Introduction to Coding Theory
2019-20 - Spring
ECE230 - Probability and Random Processes
2018-19 - Monsoon
MA2.101 - Linear Algebra
2018-19 - Spring
ECE439 - Error Correcting Codes
2018-19 - Spring
ECE230 - Probability and Random Processes
2017-18 - Monsoon
ECE537 - Topics in Coding Theory
2017-18 - Monsoon
ECE439 - Error Correcting Codes
2017-18 - Spring
ECE438 - Wireless Communications
2016-17 - Monsoon
ECE439 - Error Correcting Codes
2016-17 - Spring
ECE335 - Communication Theory I
2015-16 - Spring
ECE439 - Error Correcting Codes
2015-16 - Spring
ECE437 - Information Theory and Coding
2015-16 - Monsoon
ECE230 - Probability and Random Processes
2015-16 - Monsoon
ECE439 - Error Correcting Codes
2014-15 - Spring
Areas of Expertise
Coding Theory and Information Theory
Selected Publications
Pliable Index Coding via Conflict-Free Colorings of Hypergraphs (Journal version)
Prasad Krishnan,Rogers Mathew,Subrahmanyam Kalyanasundaram
International Symposium on Information Theory, ISIT, 2024
@inproceedings{bib_Plia_2024, AUTHOR = {Prasad Krishnan, Rogers Mathew, Subrahmanyam Kalyanasundaram}, TITLE = {Pliable Index Coding via Conflict-Free Colorings of Hypergraphs (Journal version)}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2024}}
We present a hypergraph coloring based approach to pliable index coding (PICOD). We represent the given PICOD problem using a hypergraph consisting of m messages as vertices and the request-sets of the n clients as hyperedges. A conflict- free coloring of a hypergraph is an assignment of colors to its vertices so that each hyperedge contains a uniquely colored vertex. We show that various parameters arising out of conflict- free colorings (and some new variants) of the PICOD hypergraph result in new upper bounds for the optimal PICOD length. Using these new upper bounds, we show the existence of single-request PICOD schemes with length O(log2 Γ), where Γ is the maximum number of hyperedges overlapping with any hyperedge. For the t-request PICOD scenario, we show the existence of PICOD schemes of length max(O(log Γ log m), O(t log m)), under some mild conditions on the graph parameters. These results improve upon earlier work in general. We also show that our achievable lengths in the t-request case are asymptotically optimal, up to a multiplicative factor of log t. Our existence results are accompanied by randomized constructive algorithms, which have complexity polynomial in the parameters of the PICOD problem, in expectation or with high probability. Index Terms—Index Coding, Pliabl
Recursive Subproduct Codes with Reed-Muller-like Structure
Aditya Siddheshwar,Lakshmi Prasad Natarajan,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2024
@inproceedings{bib_Recu_2024, AUTHOR = {Aditya Siddheshwar, Lakshmi Prasad Natarajan, Prasad Krishnan}, TITLE = {Recursive Subproduct Codes with Reed-Muller-like Structure}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2024}}
We study a family of subcodes of the $m$-dimensional product code $mathscr{C}^{otimes m}$ (`subproduct codes') that have a recursive Plotkin-like structure, and which include Reed-Muller (RM) codes and Dual Berman codes as special cases. We denote the codes in this family as $mathscr{C}^{otimes [r,m]}$, where mbox{$0 leq r leq m$} is the `order' of the code. These codes allow a `projection' operation that can be exploited in iterative decoding, viz., the sum of two carefully chosen subvectors of any codeword in $mathscr{C}^{otimes [r,m]}$ belongs to $mathscr{C}^{otimes [r-1,m-1]}$. Recursive subproduct codes provide a wide range of rates and block lengths compared to RM codes while possessing several of their structural properties, such as the Plotkin-like design, the projection property, and fast ML decoding of first-order codes. Our simulation results for first-order and second-order codes, that are based on a belief propagation decoder and a local graph search algorithm, show instances of subproduct codes that perform either better than or within $0.5$~dB of comparable RM codes and CRC-aided Polar codes.
On Achievable Rates for the Shotgun Sequencing Channel with Erasures
Hrishi Narayanan,Prasad Krishnan,Nita Parekh
International Symposium on Information Theory, ISIT, 2024
@inproceedings{bib_On_A_2024, AUTHOR = {Hrishi Narayanan, Prasad Krishnan, Nita Parekh}, TITLE = {On Achievable Rates for the Shotgun Sequencing Channel with Erasures}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2024}}
In shotgun sequencing, the input string (typically, a long DNA sequence composed of nucleotide bases) is sequenced as multiple overlapping fragments of much shorter lengths (called textit{reads}). Modelling the shotgun sequencing pipeline as a communication channel for DNA data storage, the capacity of this channel was identified in a recent work, assuming that the reads themselves are noiseless substrings of the original sequence. Modern shotgun sequencers however also output quality scores for each base read, indicating the confidence in its identification. Bases with low quality scores can be considered to be erased. Motivated by this, we consider the textit{shotgun sequencing channel with erasures}, where each symbol in any read can be independently erased with some probability $delta$. We identify achievable rates for this channel, using a random code construction and a decoder that uses typicality-like arguments to merge the reads.
Computationally Efficient Codes for Adversarial Binary-Erasure Channels
Sijie Li,Prasad Krishnan,Sidharth Jaggi,Michael Langberg,Anand D. Sarwate
International Symposium on Information Theory, ISIT, 2023
@inproceedings{bib_Comp_2023, AUTHOR = {Sijie Li, Prasad Krishnan, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate}, TITLE = {Computationally Efficient Codes for Adversarial Binary-Erasure Channels}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2023}}
We study communication models for channels with erasures in which the erasure pattern can be controlled by an adversary with partial knowledge of the transmitted codeword. In particular, we design block codes for channels with binary inputs with an adversary who can erase a fraction p of the transmitted bits. We consider causal adversaries, who must choose to erase an input bit using knowledge of that bit and previously transmitted bits, and myopic adversaries, who can choose an erasure pattern based on observing the transmitted codeword through a binary erasure channel with random erasures. For both settings we design efficient (polynomial time) encoding and decoding algorithms that use randomization at the encoder only. Our constructions achieve capacity for the causal and "sufficiently myopic" models. For the "insufficiently myopic" adversary, the capacity is unknown, but existing converses show the capacity is zero for a range of parameters. For all parameters outside of that range, our construction achieves positive rates.
Berman Codes: A Generalization of Reed–Muller Codes That Achieve BEC Capacity,
Lakshmi Prasad Natarajan,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2023
@inproceedings{bib_Berm_2023, AUTHOR = {Lakshmi Prasad Natarajan, Prasad Krishnan}, TITLE = {Berman Codes: A Generalization of Reed–Muller Codes That Achieve BEC Capacity,}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2023}}
We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as Cn(r,m) , and their duals are denoted as Bn(r,m) . The length of these codes is nm , where n≥2 , and r is their ‘order’. When n=2 , Cn(r,m) is the RM code of order r and length 2m . The special case of these codes corresponding to n being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to Bn(r,m) as the Berman code and Cn(r,m) as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when n is odd, we identify a large class of abelian codes that includes Bn(r,m) and Cn(r,m) and which achieves BEC capacity.
Cache-Aided Communication Schemes via Combinatorial Designs and Their q-Analogs
Shailja Agrawal,K V Sushena Sree,Prasad Krishnan,Vaishya Abhinav Rajeshkumar,Srikar Kale
IEEE Journal on Selected Areas in Information Theory, JSAIT, 2023
@inproceedings{bib_Cach_2023, AUTHOR = {Shailja Agrawal, K V Sushena Sree, Prasad Krishnan, Vaishya Abhinav Rajeshkumar, Srikar Kale}, TITLE = {Cache-Aided Communication Schemes via Combinatorial Designs and Their q-Analogs}, BOOKTITLE = {IEEE Journal on Selected Areas in Information Theory}. YEAR = {2023}}
We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache ) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. One of the chief drawbacks of many of these existing constructions is the large subpacketization level, which denotes the number of times a file should be split for the schemes to provide coding gain. In this work, using a new binary matrix model, we present several novel constructions for coded caching based on the various types of combinatorial designs and their q -analogs, which are also called subspace designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement, they provide a rate that is either constant or decreasing, and moreover require competitively small levels of subpacketization, which is an extremely important feature in practical applications of coded caching. We also apply our constructions to the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. Using our binary matrix framework, we present a new simple generic coded data shuffling scheme. Employing our designs-based constructions in conjunction with this new shuffling scheme, we obtain new coded computing schemes which have low file complexity, with marginally higher communication load compared to the optimal scheme for equivalent parameters. We show that our schemes can neatly extend to the scenario with full and partial stragglers also.
t-PIR Schemes with Flexible Parameters via Star Products of Berman Codes
Srikar Kale,Keshav Agarwal,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2023
@inproceedings{bib_t-PI_2023, AUTHOR = {Srikar Kale, Keshav Agarwal, Prasad Krishnan}, TITLE = {t-PIR Schemes with Flexible Parameters via Star Products of Berman Codes}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2023}}
We present a new class of private information retrieval (PIR) schemes that keep the identity of the file requested private in the presence of at most t colluding servers, based on the recent framework developed for such t-PIR schemes using star products of transitive codes. These t-PIR schemes employ the class of Berman codes as the storage-retrieval code pairs. Berman codes, which are binary linear codes of length nm for any n ≥ 2 and m ≥ 1 being positive integers, were recently shown to achieve the capacity of the binary erasure channel. We provide a complete characterization of the star products of the Berman code pairs, enabling us to calculate the PIR rate of the star product-based schemes that employ these codes. The schemes we present have flexibility in the number of servers, the PIR rate, the storage rate, and the collusion parameter t, owing to numerous codes available in the class of Berman codes. Due to space restrictions, the full version of this paper containing proofs of claims, additional examples, and results,
On the Structure of Higher Order MDS Codes
Athi Harshithanjani,Chigullapally Rasagna,Prasad Krishnan,Lalitha Vadlamani
International Symposium on Information Theory, ISIT, 2023
@inproceedings{bib_On_t_2023, AUTHOR = {Athi Harshithanjani, Chigullapally Rasagna, Prasad Krishnan, Lalitha Vadlamani}, 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].
Cache-Aided Communication Schemes via Combinatorial Designs and their q-analogs
Shailja Agrawal,K V Sushena Sree,Prasad Krishnan,Vaishya Abhinav Rajeshkumar,Srikar Kale
Technical Report, arXiv, 2023
@inproceedings{bib_Cach_2023, AUTHOR = {Shailja Agrawal, K V Sushena Sree, Prasad Krishnan, Vaishya Abhinav Rajeshkumar, Srikar Kale}, TITLE = {Cache-Aided Communication Schemes via Combinatorial Designs and their q-analogs}, BOOKTITLE = {Technical Report}. YEAR = {2023}}
We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. One of the chief drawbacks of many of these existing constructions is the large subpacketization level, which denotes the number of times a file should be split for the schemes to provide coding gain. In this work, using a new binary matrix model, we present several novel constructions for coded caching based on the various types of combinatorial designs and their q-analogs, which are also called subspace designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement, they provide a rate that is either constant or decreasing, and moreover require competitively small levels of subpacketization, which is an extremely important feature in practical applications of coded caching. We also apply our constructions to the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. Using our binary matrix framework, we present a new simple generic coded data shuffling scheme. Employing our designs-based constructions in conjunction with this new shuffling scheme, we obtain new coded computing schemes which have low file complexity, with marginally higher communication load compared to the optimal scheme for equivalent parameters. We show that our schemes can neatly extend to the scenario with full and partial stragglers also.
Coded Data Rebalancing for Distributed Data Storage Systems with Cyclic Storage(arXiv)
C Athreya,Vaishya Abhinav Rajeshkumar,Prasad Krishnan
Technical Report, arXiv, 2022
@inproceedings{bib_Code_2022, AUTHOR = {C Athreya, Vaishya Abhinav Rajeshkumar, Prasad Krishnan}, TITLE = {Coded Data Rebalancing for Distributed Data Storage Systems with Cyclic Storage(arXiv)}, BOOKTITLE = {Technical Report}. YEAR = {2022}}
We consider replication-based distributed storage systems in which each node stores the same quantum of data and each data bit stored has the same replication factor across the nodes. Such systems are referred to as balanced distributed databases. When existing nodes leave or new nodes are added to this system, the balanced nature of the database is lost, either due to the reduction in the replication factor, or the non-uniformity of the storage at the nodes. This triggers a rebalancing algorithm, that exchanges data between the nodes so that the balance of the database is reinstated. The goal is then to design rebalancing schemes with minimal communication load. In a recent work by Krishnan et al., coded transmissions were used to rebalance a carefully designed distributed database from a node removal or addition. These coded rebalancing schemes have optimal communication load, however, require the file-size to be at least exponential in the system parameters. In this work, we consider a cyclic balanced database (where data is cyclically placed in the system nodes) and present coded rebalancing schemes for node removal and addition in such a database. These databases (and the associated rebalancing schemes) require the file-size to be only cubic in the number of nodes in the system. We bound the advantage of our node removal rebalancing scheme over the uncoded scheme, and show that our scheme has a smaller communication load. In the node addition scenario, the rebalancing scheme presented is a simple uncoded scheme, which we show has optimal load.
A Family of Capacity-Achieving Abelian Codes for the Binary Erasure Channel
Lakshmi Prasad Natarajan ,Prasad Krishnan
National Conference on Communications, NCC, 2022
@inproceedings{bib_A_Fa_2022, AUTHOR = {Lakshmi Prasad Natarajan , Prasad Krishnan}, TITLE = {A Family of Capacity-Achieving Abelian Codes for the Binary Erasure Channel}, BOOKTITLE = {National Conference on Communications}. YEAR = {2022}}
We identify a large family of abelian codes that achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. The codes in this family have rich automorphism groups, their lengths are odd integers, and they can asymptotically (in the block length) achieve any code rate. This family contains codes of prime power block lengths that were originally identified by Berman (1967) and later inves- tigated by Blackmore and Norton (2001), and also contains their generalization to any odd block length. We use Rajan and Siddiqi’s (1992) characterization of abelian codes using discrete Fourier transform (DFT) to identify our code family and study their automorphism groups. We then use a result of Kumar, Calderbank and Pfister (2016) that relates the automorphism group of a code to its performance in the BEC to show that this code family achieves BEC capacity. The full version of this paper, including the proofs of all claims and simulation results, is available online
Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity
Lakshmi Prasad Natarajan,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2022
@inproceedings{bib_Berm_2022, AUTHOR = {Lakshmi Prasad Natarajan, Prasad Krishnan}, TITLE = {Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2022}}
We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as Cn(r, m), and their duals are denoted as Bn(r, m). The length of these codes is n m, where n ≥ 2, and r is their ‘order’. When n = 2, Cn(r, m) is the RM code of order r and length 2 m. The special case of these codes corresponding to n being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to Bn(r, m) as the Berman code and Cn(r, m) as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when n is odd, we identify a large class of abelian codes that includes Bn(r, m) and Cn(r, m) and which achieves BEC capacity
Coded Data Rebalancing for Distributed Data Storage Systems with Cyclic Storage
C Athreya,Vaishya Abhinav Rajeshkumar,Prasad Krishnan
Information Theory Workshop, ITW, 2022
@inproceedings{bib_Code_2022, AUTHOR = {C Athreya, Vaishya Abhinav Rajeshkumar, Prasad Krishnan}, TITLE = {Coded Data Rebalancing for Distributed Data Storage Systems with Cyclic Storage}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2022}}
We consider replication-based distributed storage systems in which each node stores the same quantum of data and each data bit stored has the same replication factor across the nodes. Such systems are referred to as balanced distributed databases. When existing nodes leave or new nodes are added to this system, the balanced nature of the database is lost, either due to the reduction in the replication factor, or the non-uniformity of the storage at the nodes. This triggers a rebalancing algorithm, that exchanges data between the nodes so that the balance of the database is reinstated. The goal is then to design rebalancing schemes with minimal communication load. In a recent work by Krishnan et al., coded transmissions were used to rebalance a carefully designed distributed database from a node removal or addition. These coded rebalancing schemes have optimal communication load, however, require the file-size to be at least exponential in the system parameters. In this work, we consider a cyclic balanced database (where data is cyclically placed in the system nodes) and present coded rebalancing schemes for node removal and addition in such a database. These databases (and the associated rebalancing schemes) require the file-size to be only cubic in the number of nodes in the system. We bound the advantage of our node removal rebalancing scheme over the uncoded scheme, and show that our scheme has a smaller communication load. In the node addition scenario, the rebalancing scheme presented is a simple uncoded scheme, which we show has optimal load. Due to space restrictions, the current version of this paper contains only a subset of the results concerning the node removal scenario. The full version of this paper, including additional results and examples, is available online
Bounding the Optimal Length of Pliable Index Coding via a Hypergraph-based Approach
B.Tulasi Sowjanya,Visvesh S Subramanian,Prasad Krishnan
Information Theory Workshop, ITW, 2022
@inproceedings{bib_Boun_2022, AUTHOR = {B.Tulasi Sowjanya, Visvesh S Subramanian, Prasad Krishnan}, TITLE = {Bounding the Optimal Length of Pliable Index Coding via a Hypergraph-based Approach}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2022}}
In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we use a hypergraph-based approach to derive new achievability and converse results for PICOD. We present an algorithm which gives an achievable scheme for PICOD with length at most ∆(H), where ∆(H) is the maximum degree of any vertex in a hypergraph that represents the PICOD problem. We also give a lower bound for the optimal PICOD length using a new structural parameter associated with the PICOD hypergraph called the nesting number. Finally, we also identify a class of problems for which our converse is tight.
Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity
Lakshmi Prasad Natarajan,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2022
@inproceedings{bib_Berm_2022, AUTHOR = {Lakshmi Prasad Natarajan, Prasad Krishnan}, TITLE = {Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2022}}
We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as Cn(r,m), and their duals are denoted as Bn(r,m). The length of these codes is nm, where n≥2, and r is their `order'. When n=2, Cn(r,m) is the RM code of order r and length 2m. The special case of these codes corresponding to n being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to Bn(r,m) as the Berman code and Cn(r,m) as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when n is odd, we identify a large class of abelian codes that includes Bn(r,m) and Cn(r,m) and which achieves BEC capacity.
Subexponential and Linear Subpacketization Coded Caching via Projective Geometry
HARI HARA SUTHAN C,Prasad Krishnan,K. V. Sushena Sree,MAMILLAPALLI VENKATA NAGA BHAVANA
IEEE Transactions on Information Theory, T-IT, 2021
Abs | | bib Tex
@inproceedings{bib_Sube_2021, AUTHOR = {HARI HARA SUTHAN C, Prasad Krishnan, K. V. Sushena Sree, MAMILLAPALLI VENKATA NAGA BHAVANA}, TITLE = {Subexponential and Linear Subpacketization Coded Caching via Projective Geometry}, BOOKTITLE = {IEEE Transactions on Information Theory}. YEAR = {2021}}
Large gains in the rate of cache-aided broadcast communication are obtained using coded caching, but to obtain this most existing centralized coded caching schemes require that the files at the server be divisible into a large number of parts (this number is called subpacketization). In fact, most schemes require the subpacketization to be growing asymptotically as exponential in √[\leftroot -1\uproot 1r]K for some positive integer r and K being the number of users. On the other extreme, few schemes having subpacketization linear in K are known; however, they require large number of users to exist, or they offer only little gain in the rate. In this work, we propose two new centralized coded caching schemes with low subpacketization and moderate rate gains utilizing projective geometries over finite fields. Both the schemes achieve the same asymptotic subpacketization, which is exponential in O((logK) 2 ) (thus improving on the √[\leftroot -1\uproot 1r]K exponent). The first scheme has a larger cache requirement but has at most a constant rate (with increasing K), while the second has small cache requirement but has a larger rate. As a special case of our second scheme, we get a new linear subpacketization scheme, which has a more flexible range of parameters than the existing linear subpacketization schemes. Extending our techniques, we also obtain low subpacketization schemes for other multi-receiver settings such as distributed computing and the cache-aided interference channel. We validate the performance of all our schemes via extensive numerical comparisons. For a special class of symmetric caching schemes with a given subpacketization level, we propose two new information theoretic lower bounds on the optimal rate of coded caching.
An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling
Prasad Krishnan,Lakshmi Natarajan,Lalitha Vadlamani
Information Theory Workshop, ITW, 2021
@inproceedings{bib_An_U_2021, AUTHOR = {Prasad Krishnan, Lakshmi Natarajan, Lalitha Vadlamani}, 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.
Pliable Index Coding via Conflict-Free Colorings of Hypergraphs
Prasad Krishnan,Rogers Mathew,Subrahmanyam Kalyanasundaram
International Symposium on Information Theory, ISIT, 2021
@inproceedings{bib_Plia_2021, AUTHOR = {Prasad Krishnan, Rogers Mathew, Subrahmanyam Kalyanasundaram}, TITLE = {Pliable Index Coding via Conflict-Free Colorings of Hypergraphs}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2021}}
In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the PICOD problem. A textit{conflict-free coloring} of a hypergraph is known from literature as an assignment of colors to its vertices so that each edge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as edges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Our achievable schemes based on hypergraph coloring include scalar as well as vector linear PICOD schemes. For the scalar case, using the correspondence with conflict-free coloring, we show the existence of an achievable scheme which has length where refers to a parameter of the hypergraph that captures the maximum `incidence' number of other edges on any edge. This result improves upon known achievability results in PICOD literature, in some parameter regimes.
Blind updates in coded caching
Suman Ghosh,Prasad Krishnan,Lakshmi Prasad Natarajan
Information Theory Workshop, ITW, 2021
@inproceedings{bib_Blin_2021, AUTHOR = {Suman Ghosh, Prasad Krishnan, Lakshmi Prasad Natarajan}, TITLE = {Blind updates in coded caching}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2021}}
We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost ` among all linear strategies. For two well-known families of PDAs – the MaddahAli-Niesen scheme and a scheme by Tang & Ramamoorthy and Yan et al. – we show that our new scheme has cost `when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.
An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing
Prasad Krishnan,Lakshmi Natarajan,Lalitha Vadlamani
Information Theory Workshop, ITW, 2021
@inproceedings{bib_An_U_2021, AUTHOR = {Prasad Krishnan, Lakshmi Natarajan, Lalitha Vadlamani}, 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].
Coded data rebalancing for decentralized distributed databases
Sushena Sree,Prasad Krishnan
Information Theory Workshop, ITW, 2021
@inproceedings{bib_Code_2021, AUTHOR = {Sushena Sree, Prasad Krishnan}, TITLE = {Coded data rebalancing for decentralized distributed databases }, BOOKTITLE = {Information Theory Workshop}. YEAR = {2021}}
The performance of replication-based distributed databases is affected due to non-uniform storage across storage nodes (also called data skew) and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this work, we look at balanced distributed databases with random placement, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].
Blind Updates in Coded Caching
Suman Ghosh ,Prasad Krishnan,Lakshmi Prasad Natarajan
IEEE Journal on Selected Areas in Information Theory, JSAIT, 2021
@inproceedings{bib_Blin_2021, AUTHOR = {Suman Ghosh , Prasad Krishnan, Lakshmi Prasad Natarajan}, TITLE = {Blind Updates in Coded Caching}, BOOKTITLE = {IEEE Journal on Selected Areas in Information Theory}. YEAR = {2021}}
We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost among all linear strategies. Equipped with these results, we identify when the caching system uses a PDA of Yan et al. For two other families of PDAs--the Maddah-Ali-Niesen scheme and a scheme by Tang& Ramamoorthy and Yan et al.--we show that our new scheme has cost when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.
Subexponential and Linear Subpacketization Coded Caching via Line Graphs and Projective Geometry
HARI HARA SUTHAN C,Prasad Krishnan,K V Sushena Sree
IEEE Transactions on Information Theory, T-IT, 2021
@inproceedings{bib_Sube_2021, AUTHOR = {HARI HARA SUTHAN C, Prasad Krishnan, K V Sushena Sree}, TITLE = {Subexponential and Linear Subpacketization Coded Caching via Line Graphs and Projective Geometry}, BOOKTITLE = {IEEE Transactions on Information Theory}. YEAR = {2021}}
Large gains in the rate of cache-aided broadcast communication are obtained using coded caching, but to obtain this most existing centralized coded caching schemes require that the files at the server be divisible into a large number of parts (this number is called subpacketization). In fact, most schemes require the subpacketization to be growing asymptotically as exponential in some root of the number of users . On the other extreme, few schemes having subpacketization linear in are known; however they require large number of users to exist, or they offer only little gain in rate. In this work, we propose a new framework known astextit {caching line graphs} for centralized coded caching and utilize projective geometries over finite fields to construct two new coded caching schemes with low subpacketization and moderate rate gains. Both the schemes achieve the same asymptotic subpacketization, which is …
Locally Decodable Index Codes
Lakshmi Prasad Natarajan,Prasad Krishnan,Lalitha Vadlamani,Hoang Dau
IEEE Transactions on Information Theory, T-IT, 2020
@inproceedings{bib_Loca_2020, AUTHOR = {Lakshmi Prasad Natarajan, Prasad Krishnan, Lalitha Vadlamani, Hoang Dau}, 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.
An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing
Prasad Krishnan,Lakshmi Natarajan,Lalitha Vadlamani
Technical Report, arXiv, 2020
@inproceedings{bib_An_U_2020, AUTHOR = {Prasad Krishnan, Lakshmi Natarajan, Lalitha Vadlamani}, 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.
Coded Data Rebalancing for DecentralizedDistributed Databases
K V Sushena Sree,Prasad Krishnan
Technical Report, arXiv, 2020
@inproceedings{bib_Code_2020, AUTHOR = {K V Sushena Sree, Prasad Krishnan}, TITLE = {Coded Data Rebalancing for DecentralizedDistributed Databases}, BOOKTITLE = {Technical Report}. YEAR = {2020}}
The performance of replication-based distributed databases is affected due to non-uniform storage across storage nodes (also called \textit{data skew}) and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this work, we look at balanced distributed databases with \textit{random placement}, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.
Bringing semantics into word image representation
Prasad Krishnan,Jawahar C V
Pattern Recognition, PR, 2020
@inproceedings{bib_Brin_2020, AUTHOR = {Prasad Krishnan, Jawahar C V}, TITLE = {Bringing semantics into word image representation}, BOOKTITLE = {Pattern Recognition}. YEAR = {2020}}
The shift from one-hot to distributed representation, popularly referred to as word embedding has changed the landscape of natural language processing (nlp) and information retrieval (ir) communities. In the domain of document images, we have always appreciated the need for learning a holistic word image representation which is popularly used for the task of word spotting. The representations proposed for word spotting is different from word embedding in text since the later captures the semantic aspects of the word which is a crucial ingredient to numerous nlp and ir tasks. In this work, we attempt to encode the notion of semantics into word image representation by bringing the advancements from the textual domain. We propose two novel forms of representations where the first form is designed to be inflection invariant by focusing on the approximate linguistic root of the word, while the second form is built …
Coded Data Rebalancing: Fundamental Limits and Constructions
Prasad Krishnan,Lalitha Vadlamani,Lakshmi Natarajan
International Symposium on Information Theory, ISIT, 2020
@inproceedings{bib_Code_2020, AUTHOR = {Prasad Krishnan, Lalitha Vadlamani, Lakshmi Natarajan}, 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.
Low Complexity Distributed Computing via Binary Matrices with Extension to Stragglers
Shailja Agrawal,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2020
@inproceedings{bib_Low__2020, AUTHOR = {Shailja Agrawal, Prasad Krishnan}, TITLE = {Low Complexity Distributed Computing via Binary Matrices with Extension to Stragglers}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2020}}
We consider the distributed computing framework of Map-Reduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. For this framework, we propose the use of binary matrices (with entries) calledtextit {computing matrices} to describe the map phase and the shuffle phase. Similar binary matrices were recently proposed for the coded caching framework. The structure of ones and zeroes in the binary computing matrix captures the map phase of the Map-reduce framework. We present a new simple coded data shuffling scheme for this binary matrix model, based on atextit {identity submatrix cover} of the computing matrix. This new coded shuffling scheme has in general a larger communication load than existing schemes, but has the advantage of less complexity overhead than the well-known earlier schemes in literature in terms of the file-splitting and associated indexing and coordination required. We also show that there exists a binary matrix based distributed computing scheme with our new data-shuffling scheme which has strictly less than twice than the communication load of the known optimal scheme in literature. The structure of this new scheme enables it to be applied to the framework of Map-reduce with stragglers also, in a straightforward manner, borrowing its advantages and disadvantages from the no-straggler situation. Finally, using binary matrices derived from combinatorial designs, we show specific classes of computing schemes with very lowtextit {file complexity}(number of subfiles in the file), but with higher communication load compared to the optimal scheme for equivalent parameters.
On Index coding for Complementary Graphs with focus on Circular Perfect Graphs
Bhavana M,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2019
@inproceedings{bib_On_I_2019, AUTHOR = {Bhavana M, Prasad Krishnan}, TITLE = {On Index coding for Complementary Graphs with focus on Circular Perfect Graphs}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2019}}
Circular perfect graphs are those undirected graphs such that the circular clique number is equal to the circular chromatic number for each induced subgraph. They form a strict superclass of the perfect graphs, whose index coding broadcast rates are well known. We present the broadcast rate of index coding for side-information graphs whose complements are circular perfect, along with an optimal achievable scheme. We thus enlarge the known classes of graphs for which the broadcast rate is exactly characterized. In an attempt to understand the broadcast rate of a graph given that of its complement, we obtain upper and lower bounds for the product and sum of the vector linear broadcast rates of a graph and its complement. We show that these bounds are satisfied with equality even for some perfect graphs. Curating prior results, we show that there are circular perfect but imperfect graphs which satisfy the lower bound on the product of the broadcast rate of the complementary graphs with equality.
Low Subpacketization Coded Caching via Projective Geometry for Broadcast and D2D networks
HARI HARA SUTHAN C,Prasad Krishnan
Technical Report, arXiv, 2019
@inproceedings{bib_Low__2019, AUTHOR = {HARI HARA SUTHAN C, Prasad Krishnan}, TITLE = {Low Subpacketization Coded Caching via Projective Geometry for Broadcast and D2D networks}, BOOKTITLE = {Technical Report}. YEAR = {2019}}
Coded caching was introduced as a technique of systematically exploiting locally available storage at the clients to increase the channel throughput via coded transmissions. Most known coded caching schemes in literature enable large gains in terms of the rate, however at the cost of subpacketization that is exponential in ( being the number of clients, some positive integer). Building upon recent prior work for coded caching design via line graphs and finite-field projective geometries, we present a new scheme in this work which achieves a subexponential (in ) subpacketization of and rate , for large , and the cached fraction being upper bounded by a constant (for some prime power and constant ). Apart from this asymptotic improvement, we show that through some numerical comparisons that our present scheme has much lower subpacketization than previous comparable …
Cache-Aided Interference Management with Subexponential Subpacketization
HARI HARA SUTHAN C,K V Sushena Sree,Prasad Krishnan
Technical Report, arXiv, 2019
@inproceedings{bib_Cach_2019, AUTHOR = {HARI HARA SUTHAN C, K V Sushena Sree, Prasad Krishnan}, TITLE = {Cache-Aided Interference Management with Subexponential Subpacketization}, BOOKTITLE = {Technical Report}. YEAR = {2019}}
Consider an interference channel consisting of transmitters and receivers with AWGN noise and complex channel gains, and with files in the system. The one-shot for this channel is the maximum number of receivers which can be served simultaneously with vanishing probability of error as the grows large, under a class of schemes known as\textit {one-shot} schemes. Consider that there exists transmitter and receiver side caches which can store fractions and of the library respectively. Recent work for this cache-aided interference channel setup shows that, using a carefully designed prefetching (caching) phase, and a one-shot coded delivery scheme combined with a proper choice of beamforming coefficients at the transmitters, we can achieve a of , where and which was shown to be almost optimal. The existing scheme involves splitting the file into subfiles (the parameter is called the\textit {subpacketization}), where can be extremely large (in fact, with constant cache fractions, it becomes exponential in , for large ). In this work, our first contribution is a scheme which achieves the same of with a smaller subpacketization than prior schemes. Our second contribution is a new coded caching scheme for the interference channel based on projective geometries over finite fields which achieves a one-shot of , with a subpacketization (for some prime power ) that is\textit {subexponential} in , for small constant cache fraction at the receivers. To the best of our knowledge, this is the first coded caching scheme with subpacketization …
Locality in index coding for large min-rank
Lakshmi Natarajan,Hoang Dau,Prasad Krishnan,Lalitha Vadlamani
International Symposium on Information Theory, ISIT, 2019
@inproceedings{bib_Loca_2019, AUTHOR = {Lakshmi Natarajan, Hoang Dau, Prasad Krishnan, Lalitha Vadlamani}, 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 …
Coded caching based on combinatorial designs
Shailja Agrawal,K V Sushena Sree,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2019
@inproceedings{bib_Code_2019, AUTHOR = {Shailja Agrawal, K V Sushena Sree, Prasad Krishnan}, TITLE = {Coded caching based on combinatorial designs}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2019}}
We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. In this work, we propose a binary matrix model to construct the coded caching scheme. The ones in such a caching matrix indicate uncached subfiles at the users. Identity submatrices of the caching matrix represent transmissions in the delivery phase. Using this model, we then propose several novel constructions for coded caching based on the various types of combinatorial designs …
Coded caching via projective geometry: A new low subpacketization scheme
HARI HARA SUTHAN C,MAMILLAPALLI VENKATA NAGA BHAVANA,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2019
@inproceedings{bib_Code_2019, AUTHOR = {HARI HARA SUTHAN C, MAMILLAPALLI VENKATA NAGA BHAVANA, Prasad Krishnan}, TITLE = {Coded caching via projective geometry: A new low subpacketization scheme}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2019}}
Coded Caching is a promising solution to reduce the peak traffic in broadcast networks by prefetching the popular content close to end users and using coded transmissions. One of the chief issues of most coded caching schemes in literature is the issue of large subpacketization, i.e., they require each file to be divided into a large number of subfiles. In this work, we present a coded caching scheme using line graphs of bipartite graphs in conjunction with projective geometries over finite fields. The presented scheme achieves a rate Θ(K/log q K) (K being the number of users, q is some prime power) with subexponential subpacketization q O((logq K)^2) when cached fraction is upper bounded by a constant (M/N ≤ 1/q α , for some positive integer α). Compared to earlier schemes, the presented scheme has a lower subpacketization (albeit possessing a higher rate). We also present a new subpacketization …
Projective Geometry based Coded Caching Schemes with Subexponential and Linear Subpacketizations
HARI HARA SUTHAN C,Prasad Krishnan
International Symposium on Communications and Information Technologies, ISCIT, 2019
@inproceedings{bib_Proj_2019, AUTHOR = {HARI HARA SUTHAN C, Prasad Krishnan}, TITLE = {Projective Geometry based Coded Caching Schemes with Subexponential and Linear Subpacketizations}, BOOKTITLE = {International Symposium on Communications and Information Technologies}. YEAR = {2019}}
Coded Caching is a recent technique that optimizes the use of a multi-client broadcast channel by the use of local storage available at the clients and by using coded transmissions to serve multiple clients at once. While large gains in the rate of communication are obtained using coded caching, most existing schemes require that the files at the server be divisible into a large number of parts. In particular, most known coded caching schemes require subpacketization $ F={e^{Oleft ({{K^{frac {1}{r}}}}right)}} $, where K is the number of clients and r is some constant positive integer. While few schemes having subpacketization linear in K are known in literature, unfortunately such schemes require large number of users to exist or offer little gain in rate. In this work, we propose a class of coded caching schemes based on projective geometries over finite fields, generalizing recent results. Our construction achieves subexponential (in K) subpacketization, ie, $ F={q^{O …
Low subpacketization coded caching via projective geometry for broadcast and d2d networks
HARI HARA SUTHAN C,Prasad Krishnan
IEEE Global Communications Conference, GLOBECOM, 2019
@inproceedings{bib_Low__2019, AUTHOR = {HARI HARA SUTHAN C, Prasad Krishnan}, TITLE = {Low subpacketization coded caching via projective geometry for broadcast and d2d networks}, BOOKTITLE = {IEEE Global Communications Conference}. YEAR = {2019}}
Coded caching was introduced as a technique of systematically exploiting locally available storage at the clients to increase the channel throughput via coded transmissions. Most known coded caching schemes in literature enable large gains in terms of the rate, however at the cost of subpacketization that is exponential in ( being the number of clients, some positive integer). Building upon recent prior work for coded caching design via line graphs and finite-field projective geometries, we present a new scheme in this work which achieves a subexponential (in ) subpacketization of and rate , for large , and the cached fraction being upper bounded by a constant (for some prime power and constant ) . Apart from this asymptotic improvement, we show that through some numerical comparisons that our present scheme has much lower subpacketization than previous comparable …
Index coding: Rank-invariant extensions
G VAMSI KRISHNA,ASHOK CHOUDHARY,Prasad Krishnan
National Conference on Communications, NCC, 2018
@inproceedings{bib_Inde_2018, AUTHOR = {G VAMSI KRISHNA, ASHOK CHOUDHARY, Prasad Krishnan}, TITLE = {Index coding: Rank-invariant extensions}, BOOKTITLE = {National Conference on Communications}. YEAR = {2018}}
An index coding (IC) problem consisting of a server and multiple receivers with different side-information and demand sets can be equivalently represented using a fitting matrix. A scalar linear index code to a given IC problem is a matrix representing the transmitted linear combinations of the message symbols. The length of an index code is then the number of transmissions (or equivalently, the number of rows in the index code). An IC problem Iext is called an extension of another IC problem I if the fitting matrix of I is a submatrix of the fitting matrix of Iext. We first present a straightforward m-order extension Iext of an IC problem I for which an index code is obtained by concatenating m copies of an index code of I. The length of the codes is the same for both I and Iext, and if the index code for I has optimal length then so does the extended code for Iext. More generally, an extended IC problem of I having the same …
Optimal Index Codes via a Duality between Index Coding and Network Coding
ASHOK CHOUDHARY,G VAMSI KRISHNA,Prasad Krishnan
National Conference on Communications, NCC, 2018
@inproceedings{bib_Opti_2018, AUTHOR = {ASHOK CHOUDHARY, G VAMSI KRISHNA, Prasad Krishnan}, TITLE = {Optimal Index Codes via a Duality between Index Coding and Network Coding}, BOOKTITLE = {National Conference on Communications}. YEAR = {2018}}
n Index Coding, the goal is to use a broadcast channel as efficiently as possible to communicate information from a source to multiple receivers which can possess some of the information symbols at the source as side-information. In this work, we present a duality relationship between index coding (IC) and multiple-unicast network coding (NC). It is known that the IC problem can be represented using a side-information graph G (with number of vertices n equal to the number of source symbols). The size of the maximum acyclic induced subgraph, denoted by MAI S is a lower bound on the broadcast rate. For IC problems with MAIS = n - 1 and MAI S = n - 2, prior work has shown that binary (over F 2) linear index codes achieve the MAI S lower bound for the broadcast rate and thus are optimal. In this work, we use the the duality relationship between NC and IC to show that for a class of IC problems with MAIS = n - 3 …
On locally decodable index codes
Lakshmi Natarajan,Prasad Krishnan,Lalitha Vadlamani,Hoang Dau
International Symposium on Information Theory, ISIT, 2018
@inproceedings{bib_On_l_2018, AUTHOR = {Lakshmi Natarajan, Prasad Krishnan, Lalitha Vadlamani, Hoang Dau}, 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 …
Coded caching via line graphs of bipartite graphs
Prasad Krishnan
Information Theory Workshop, ITW, 2018
@inproceedings{bib_Code_2018, AUTHOR = {Prasad Krishnan}, TITLE = {Coded caching via line graphs of bipartite graphs}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2018}}
We present a coded caching framework using line graphs of bipartite graphs. A clique cover of the line graph describes the uncached subfiles at users. A clique cover of the complement of the square of the line graph gives a transmission scheme that satisfies user demands. We then define a specific class of such caching line graphs, for which the subpacketization, rate, and uncached fraction of the coded caching problem can be captured via its graph theoretic parameters. We present a construction of such caching line graphs using projective geometry. The presented scheme has a rate bounded from above by a constant with subpacketization level q O((IogqK)^2) and uncached fraction Θ(1/√K), where K is the number of users and q is a prime power. We also present a subpacketization-dependent lower bound on the rate of coded caching schemes for a given broadcast setup.
Index Coding: Rank-Invariant Extensions
Prasad Krishnan,G VAMSI KRISHNA,ASHOK CHOUDHARY
National Conference on Communications, NCC, 2017
@inproceedings{bib_Inde_2017, AUTHOR = {Prasad Krishnan, G VAMSI KRISHNA, ASHOK CHOUDHARY}, TITLE = {Index Coding: Rank-Invariant Extensions}, BOOKTITLE = {National Conference on Communications}. YEAR = {2017}}
An index coding (IC) problem consisting of a server and multiple receivers with different side-information and demand sets can be equivalently represented using a fitting matrix.A scalar linear index code to a given IC problem is a matrix representing the transmitted linear combinations of the message symbols. The length of an index code is then the number of transmissions (or equivalently, the number of rows in the index code). An IC problem I ext is called an extension of another IC problem I if the fitting matrix of Iis a sub matrix of the fitting matrix of I ext. We first present a straight forward mordern extension Iextof an IC problem I for which an index code is obtained by concatenating m copies of an index code of I. The length of the codes is the same for both I and Iext,and if the index code for I has optimal length then so does the extended code for I ext. More generally, an extended IC problem of I having the same optimal length as I is said to be a rank-invariant extension of I. We then focus on2-order rank-invariant extensions of I, and present constructions of such extensions based on in volutory permutation matrices.
Uniprior Index Coding
VIJAYA KUMAR MAREEDU,Prasad Krishnan
Information Theory Workshop, ITW, 2017
@inproceedings{bib_Unip_2017, AUTHOR = {VIJAYA KUMAR MAREEDU, Prasad Krishnan}, TITLE = {Uniprior Index Coding}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2017}}
The index coding problem is a problem of efficient broadcasting with side-information. In uniprior index coding,the sets of side-information symbols possessed by different receivers are disjoint. For single uniprior index coding, in which each receiver has a single unique side-information symbol, a polynomial complexity construction of an optimal index code is known from prior work. In this work, we model the uniprior index coding problem as a super graph, and focus on a class of uniprior problems defined on special supergraphs known as generalized cycles in which the sizes of the demand set andthe side-information set are equal at each receiver. For such problems, we prove upper and lower bounds on the optimal broadcast rate. Using a connection with Eulerian directed graphs,we also show that the upper and lower bounds are equal fora subclass of uniprior problems. We show the NP-hardness offinding the lower bound for uniprior problems on generalized cycles, hence contrasting such uniprior problems with single uniprior problems. Finally, we look at a simple extension of the generalized cycle uniprior class for which we give bounds on the optimal rate and show an explicit scheme which achieves the upper bound
An improved secretive coded caching scheme exploiting common demands
HARI HARA SUTHAN C,ISHANI,Prasad Krishnan
Information Theory Workshop, ITW, 2017
@inproceedings{bib_An_i_2017, AUTHOR = {HARI HARA SUTHAN C, ISHANI, Prasad Krishnan}, TITLE = {An improved secretive coded caching scheme exploiting common demands}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2017}}
Coded caching schemes on broadcast networks with user caches help to offload traffic from peak times to off-peak times by prefetching information from the server to the usersduring off-peak times and thus serving the users more efficiently during peak times using coded transmissions. We consider the problem of secretive coded caching which was proposed recently,in which a user should not be able to decode any information about any file that the user has not demanded. We propose a new secretive coded caching scheme which has a lower average rate compared to the existing state-of-the-art scheme, for the same memory available at the users. The proposed scheme is based one exploiting the presence of common demands between multiple users
Rate 1/3 index coding: Forbidden and feasible configurations
Lalitha Vadlamani,Prasad Krishnan
International Symposium on Information Theory, ISIT, 2017
@inproceedings{bib_Rate_2017, AUTHOR = {Lalitha Vadlamani, Prasad Krishnan}, 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
A class of index coding problems with rate1/3
Prasad Krishnan,Lalitha Vadlamani
International Symposium on Information Theory, ISIT, 2016
@inproceedings{bib_A_cl_2016, AUTHOR = {Prasad Krishnan, Lalitha Vadlamani}, 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.
A matroidal framework for network-error correcting codes
Prasad Krishnan,B. Sundar Rajan
IEEE Transactions on Information Theory, T-IT, 2015
@inproceedings{bib_A_ma_2015, AUTHOR = {Prasad Krishnan, B. Sundar Rajan}, TITLE = {A matroidal framework for network-error correcting codes}, BOOKTITLE = {IEEE Transactions on Information Theory}. YEAR = {2015}}
Matroidal networks were introduced by Doughert yet al.and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. A particularly interesting feature of this development is the ability to construct (scalar and vector)linearly solvable networks using certain classes of matroids.Furthermore, it was shown through the connection between network coding and matroid theory that linear network coding is not always sufficient for general network coding scenarios.The current work attempts to establish a connection between matroid theory and network-error correcting and detecting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of linear network-error detecting codes to arrive at the definition of a matroidal error detecting network(and similarly, a matroidal error correcting networkabstracting from network-error correcting codes). An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error detecting (correcting)network code if and only if it is a matroidal error detecting(correcting) network associated with a representable matroid.Therefore, constructing such network-error correcting and detecting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa.We then present algorithms that enable the construction of matroidal error detecting and correcting networks with a specified capability of network-error correction. Using these construction algorithms, a large class of hitherto unknown scalar linearly solvable networks with multi source, multicast,and multiple- unicast network-error correcting codes is made available for theoretical use and practical implementation,with parameters, such as number of information symbols,number of sinks, number of coding nodes, error correcting capability, and so on, being arbitrary but for computing power(for the execution of the algorithms). The complexity of the construction of these networks is shown to be comparable with the complexity of existing algorithms that design multi cast scalar linear network-error correcting codes. Finally, we also show that linear network coding is not sufficient for the general network-error correction (detection) problem with arbitrary demands. In particular, for the same number of network errors,we show a network for which there is a nonlinear network-error detecting code satisfying the demands at the sinks, where as there are no linear network-error detecting codes that do the same.
Copyright © 2023 All rights reserved