BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Navin Kashyap

Navin Kashyap contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITSocial and Information NetworksComputationGenomicsMachine Learningmath.PRquant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2026arXiv

Estimators for Substitution Rates in Genomes from Read Data

We study the problem of estimating the mutation rate between two sequences from noisy sequencing reads. Existing alignment-free methods typically assume direct access to the full sequences. We extend these methods to the sequencing framework, where only noisy reads from the sequences are observed. We use a simple model in which both mutations and sequencing errors are substitutions. We propose multiple estimators, provide theoretical guarantees for one of them, and evaluate the others through simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Entanglement-Assisted Quantum Error-Correcting Codes over Local Frobenius Rings

In this paper, we provide a framework for constructing entanglement-assisted quantum error-correcting codes (EAQECCs) from classical additive codes over a finite commutative local Frobenius ring $\mathcal{R}$. At the heart of the framework, and this is one of the main technical contributions of our paper, is a procedure to construct, for an additive code $\mathcal{C}$ over $\mathcal{R}$, a generating set for $\mathcal{C}$ that is in standard form, meaning that it consists purely of isotropic generators and hyperbolic pairs. Moreover, when $\mathcal{R}$ is a Galois ring, we give an exact expression for the minimum number of pairs of maximally entangled qudits required to construct an EAQECC from an additive code over $\mathcal{R}$, which significantly extends known results for EAQECCs over finite fields. We also demonstrate how adding extra coordinates to an additive code can give us a certain degree of flexibility in determining the parameters of the EAQECCs that result from our construction.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Feedback Capacity-Achieving Coding Scheme for the $(d,\infty)$-RLL Input-Constrained Binary Erasure Channel

This paper considers the memoryless input-constrained binary erasure channel (BEC). The channel input constraint is the $(d,\infty)$-runlength limited (RLL) constraint, which mandates that any pair of successive $1$s in the input sequence be separated by at least $d$ $0$s. We consider a scenario where there is causal, noiseless feedback from the decoder. We demonstrate a simple, labelling-based, zero-error feedback coding scheme, which we prove to be feedback capacity-achieving, and, as a by-product, obtain an explicit characterization of the feedback capacity. Our proof is based on showing that the rate of our feedback coding scheme equals an upper bound on the feedback capacity derived using the single-letter bounding techniques of Sabag et al. (2017). Further, we note using the tools of Thangaraj (2017) that there is a gap between the feedback and non-feedback capacities of the $(d,\infty)$-RLL input constrained BEC, at least for $d=1,2$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

An Analysis of Probabilistic Forwarding of Coded Packets on Random Geometric Graphs

We consider the problem of energy-efficient broadcasting on dense ad-hoc networks. Ad-hoc networks are generally modeled using random geometric graphs (RGGs). Here, nodes are deployed uniformly in a square area around the origin, and any two nodes which are within Euclidean distance of $1$ are assumed to be able to receive each other's broadcast. A source node at the origin encodes $k$ data packets of information into $n\ (>k)$ coded packets and transmits them to all its one-hop neighbors. The encoding is such that, any node that receives at least $k$ out of the $n$ coded packets can retrieve the original $k$ data packets. Every other node in the network follows a probabilistic forwarding protocol; upon reception of a previously unreceived packet, the node forwards it with probability $p$ and does nothing with probability $1-p$. We are interested in the minimum forwarding probability which ensures that a large fraction of nodes can decode the information from the source. We deem this a \emph{near-broadcast}. The performance metric of interest is the expected total number of transmissions at this minimum forwarding probability, where the expectation is over both the forwarding protocol as well as the realization of the RGG. In comparison to probabilistic forwarding with no coding, our treatment of the problem indicates that, with a judicious choice of $n$, it is possible to reduce the expected total number of transmissions while ensuring a near-broadcast.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Linear Runlength-Limited Subcodes of Reed-Muller Codes and Coding Schemes for Input-Constrained BMS Channels

In this work, we address the question of the largest rate of linear subcodes of Reed-Muller (RM) codes, all of whose codewords respect a runlength-limited (RLL) constraint. Our interest is in the $(d,\infty)$-RLL constraint, which mandates that every pair of successive $1$s be separated by at least $d$ $0$s. Consider any sequence $\{{\mathcal{C}_m}\}_{m\geq 1}$ of RM codes with increasing blocklength, whose rates approach $R$, in the limit as the blocklength goes to infinity. We show that for any linear $(d,\infty)$-RLL subcode, $\hat{\mathcal{C}}_m$, of the code $\mathcal{C}_m$, it holds that the rate of $\hat{\mathcal{C}}_m$ is at most $\frac{R}{d+1}$, in the limit as the blocklength goes to infinity. We also consider scenarios where the coordinates of the RM codes are not ordered according to the standard lexicographic ordering, and derive rate upper bounds for linear $(d,\infty)$-RLL subcodes, in those cases as well. Next, for the setting of a $(d,\infty)$-RLL input-constrained binary memoryless symmetric (BMS) channel, we devise a new coding scheme, based on cosets of RM codes. Again, in the limit of blocklength going to infinity, this code outperforms any linear subcode of an RM code, in terms of rate, for low noise regimes of the channel.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Performance of Reed-Muller Codes Over $(d,\infty)$-RLL Input-Constrained BMS Channels

This paper considers the input-constrained binary memoryless symmetric (BMS) channel, without feedback. The channel input sequence respects the $(d,\infty)$-runlength limited (RLL) constraint, which mandates that any pair of successive $1$s be separated by at least $d$ $0$s. We consider the problem of designing explicit codes for such channels. In particular, we work with the Reed-Muller (RM) family of codes, which were shown by Reeves and Pfister (2021) to achieve the capacity of any unconstrained BMS channel, under bit-MAP decoding. We show that it is possible to pick $(d,\infty)$-RLL subcodes of a capacity-achieving (over the unconstrained BMS channel) sequence of RM codes such that the subcodes achieve, under bit-MAP decoding, rates of $C\cdot{2^{-\left \lceil \log_2(d+1)\right \rceil}}$, where $C$ is the capacity of the BMS channel. Finally, we also introduce techniques for upper bounding the rate of any $(1,\infty)$-RLL subcode of a specific capacity-achieving sequence of RM codes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

An MCMC Method to Sample from Lattice Distributions

We introduce a Markov Chain Monte Carlo (MCMC) algorithm to generate samples from probability distributions supported on a $d$-dimensional lattice $Λ= \mathbf{B}\mathbb{Z}^d$, where $\mathbf{B}$ is a full-rank matrix. Specifically, we consider lattice distributions $P_Λ$ in which the probability at a lattice point is proportional to a given probability density function, $f$, evaluated at that point. To generate samples from $P_Λ$, it suffices to draw samples from a pull-back measure $P_{\mathbb{Z}^d}$ defined on the integer lattice. The probability of an integer lattice point under $P_{\mathbb{Z}^d}$ is proportional to the density function $π= |\det(\mathbf{B})|f\circ \mathbf{B}$. The algorithm we present in this paper for sampling from $P_{\mathbb{Z}^d}$ is based on the Metropolis-Hastings framework. In particular, we use $π$ as the proposal distribution and calculate the Metropolis-Hastings acceptance ratio for a well-chosen target distribution. We can use any method, denoted by ALG, that ideally draws samples from the probability density $π$, to generate a proposed state. The target distribution is a piecewise sigmoidal distribution, chosen such that the coordinate-wise rounding of a sample drawn from the target distribution gives a sample from $P_{\mathbb{Z}^d}$. When ALG is ideal, we show that our algorithm is uniformly ergodic if $-\log(π)$ satisfies a gradient Lipschitz condition.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Bounds on the Feedback Capacity of the $(d,\infty)$-RLL Input-Constrained Binary Erasure Channel

The paper considers the input-constrained binary erasure channel (BEC) with causal, noiseless feedback. The channel input sequence respects the $(d,\infty)$-runlength limited (RLL) constraint, i.e., any pair of successive $1$s must be separated by at least $d$ $0$s. We derive upper and lower bounds on the feedback capacity of this channel, for all $d\geq 1$, given by: $\max\limits_{δ\in [0,\frac{1}{d+1}]}R(δ) \leq C^{\text{fb}}_{(d\infty)}(ε) \leq \max\limits_{δ\in [0,\frac{1}{1+dε}]}R(δ)$, where the function $R(δ) = \frac{h_b(δ)}{dδ+ \frac{1}{1-ε}}$, with $ε\in [0,1]$ denoting the channel erasure probability, and $h_b(\cdot)$ being the binary entropy function. We note that our bounds are tight for the case when $d=1$ (see Sabag et al. (2016)), and, in addition, we demonstrate that for the case when $d=2$, the feedback capacity is equal to the capacity with non-causal knowledge of erasures, for $ε\in [0,1-\frac{1}{2\log(3/2)}]$. For $d>1$, our bounds differ from the non-causal capacities (which serve as upper bounds on the feedback capacity) derived in Peled et al. (2019) in only the domains of maximization. The approach in this paper follows Sabag et al. (2017), by deriving single-letter bounds on the feedback capacity, based on output distributions supported on a finite $Q$-graph, which is a directed graph with edges labelled by output symbols.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Secret Key Agreement and Secure Omniscience of Tree-PIN Source with Linear Wiretapper

While the wiretap secret key capacity remains unknown for general source models even in the two-user case, we obtained a single-letter characterization for a large class of multi-user source models with a linear wiretapper who can observe any linear combinations of the source. We introduced the idea of irreducible sources to show existence of an optimal communication scheme that achieves perfect omniscience with minimum leakage of information to the wiretapper. This implies a duality between the problems of wiretap secret key agreement and secure omniscience, and such duality potentially holds for more general sources.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Computable Lower Bounds for Capacities of Input-Driven Finite-State Channels

This paper studies the capacities of input-driven finite-state channels, i.e., channels whose current state is a time-invariant deterministic function of the previous state and the current input. We lower bound the capacity of such a channel using a dynamic programming formulation of a bound on the maximum reverse directed information rate. We show that the dynamic programming-based bounds can be simplified by solving the corresponding Bellman equation explicitly. In particular, we provide analytical lower bounds on the capacities of $(d, k)$-runlength-limited input-constrained binary symmetric and binary erasure channels. Furthermore, we provide a single-letter lower bound based on a class of input distributions with memory.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Probabilistic Forwarding of Coded Packets on Networks

We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has some data packets to broadcast. It encodes these data packets into $n$ coded packets in such a way that any node in the network that receives any $k$ out of the $n$ coded packets will be able to retrieve all the original data packets. The source transmits the $n$ coded packets to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability $p$. We say that the information from the source undergoes a ``near-broadcast'' if the expected fraction of nodes that receive at least $k$ of the $n$ coded packets is close to $1$. The forwarding probability $p$ is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. We study how, for a given $k$, this minimum forwarding probability and the associated expected total number of packet transmissions varies with $n$. We specifically analyze the probabilistic forwarding of coded packets on two network topologies: binary trees and square grids. For trees, our analysis shows that for fixed $k$, the expected total number of transmissions increases with $n$. On the other hand, on grids, a judicious choice of $n$ significantly reduces the expected total number of transmissions needed for a near-broadcast. Behaviour similar to that of the grid is also observed in other well-connected network topologies such as random geometric graphs and random regular graphs

0 citations0 reviewsNo code linkedOpen access