Avhishek Chatterjee

We consider transmission of packets over queue-length sensitive unreliable links, where packets are randomly corrupted through a noisy channel whose transition probabilities are modulated by the queue-length. The goal is to characterize the capacity of this channel. We particularly consider multiple-access systems, where transmitters dispatch encoded symbols over a system that is a superposition of continuous-time GI-GI 1 queues. A server receives and processes symbols in order of arrivals with queue-length dependent noise. We first determine the capacity of single-user queue-length dependent channels. Further, we characterize the best and worst dispatch processes for {GI} {M} 1 queues and the best and worst service processes for {M} {GI} 1 queues. Then, the multiple-access channel capacity is obtained using point processes. When the number of transmitters is large and each arrival process is sparse, the superposition of arrivals approaches a Poisson point process. In characterizing the Poisson approximation, we show that the capacity of the multiple-access system converges to that of a single-user {M} {GI}/1 queue-length dependent system, and an upper bound on the convergence rate is obtained. This implies that the best and worst server behaviors of single-user {M} {GI}/1 queues are preserved in the sparse multiple-access case.

We consider a setting where qubits are processed sequentially, and derive fundamental limits on the rate at which classical information can be transmitted using quantum states that decohere in time. Specifically, we model the sequential processing of qubits using a single server queue, and derive explicit expressions for the capacity of such a 'queue-channel.' We also demonstrate a sweet-spot phenomenon with respect to the arrival rate to the queue, i.e., we show that there exists a value of the arrival rate of the qubits at which the rate of information transmission (in bits/sec) through the queue-channel is maximised. Next, we consider a setting where the average rate of processing qubits is fixed, and show that the capacity of the queue-channel is maximised when the processing time is deterministic. We also discuss design implications of these results on quantum information processing systems.

Consider the information-theoretic limits of reliable communication in a multiuser setting of transmission through a system with queue-length dependent service quality. Multiple transmitters dispatch encoded symbols using renewal processes over a system that is a superposition of GI-{k}/GI/1 queues, and a noisy server processes symbols in order of arrival with error probability depending on the queue-length. First, the information capacities of the single-user and multiuser continuous-time queue-length dependent system are found. When the number of transmitters is large and each is sparse, the superposition of arrivals approaches a Poisson point process. In characterizing the Poisson approximation, we show that the individual and sum capacities of the multiuser system converges to the capacity of a single-user M/GI/1 queue-length dependent system. The speed of convergence in the number of users is explicitly given. Further, the best and worst server behaviors of M / G I /1 queues from the single-user case are preserved in the multiuser case.

We consider a setting where a stream of qubits is processed sequentially. We derive fundamental limits on the rate at which classical information can be transmitted using qubits that decohere as they wait to be processed. Specifically, we model the sequential processing of qubits using a single server queue, and derive expressions for the classical capacity of such a quantum 'queue-channel.' Focusing on quantum erasures, we obtain an explicit single-letter capacity formula in terms of the stationary waiting time of qubits in the queue. Our capacity proof also implies that a 'classical' coding/decoding strategy is optimal, i.e., an encoder which uses only orthogonal product states, and a decoder which measures in a fixed product basis, are sufficient to achieve the classical capacity of the quantum erasure queue-channel. More broadly, our work begins to quantitatively address the impact of decoherence on the performance limits of quantum information processing systems.

Crowdsourcing of jobs to online freelance platforms is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs e.g., image classification with no specific quality requirement since freelancers are functionally identical. For skilled jobs e.g., software development with specific quality requirements, however, this does not ensure that the maximum number of job requests is satisfied. In this paper, we determine the capacity of regulated freelance systems, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom for customers and freelancers, we propose simple schemes compatible with the operation of current crowdsourcing platforms that approximately achieve capacity. Furthermore, for settings where the number of job requests exceeds capacity, we propose a scheme that is agnostic of that information, but is optimal and fair in declining jobs without wait.

We propose a methodology to perform process variation-aware device and circuit design using fully physics-based simulations within limited computational resources, without developing a compact model. Machine learning (ML), specifically a support vector regression (SVR) model, has been used. The SVR model has been trained using a dataset of devices simulated a priori, and the accuracy of prediction by the trained SVR model has been demonstrated. To produce a switching time distribution from the trained ML model, we only had to generate the dataset to train and validate the model, which needed g1/4500 hours of computation. On the other hand, if 106 samples were to be simulated using the same computation resources to generate a switching time distribution from micromagnetic simulations, it would have taken g1/4250 days. Spin-transfer-torque random access memory (STTRAM) has been used to demonstrate the method. However, different physical systems may be considered, different ML models can be used for different physical systems and/or different device parameter sets, and similar ends could be achieved by training the ML model using measured device data.

Many companies now use crowdsourcing to leverage external as well as internal crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill sets and availabilities of agents with different skill sets. Considering these constraints together necessitate the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized, and offer customers (task requesters) the freedom to choose agents. In this paper, we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a nonprofit company and show significant improvements over current practice.

Motivated by the classical synchronization problem and emerging applications in bioinformatics, we study noisy deletion channels in a regime of practical interest: short code length, low decoding complexity and low SNR. Our work is inspired by an important insight from information theory and Markov chains: appropriately parametrized Markov codewords can correct deletions and errors (due to noise) simultaneously. We extend this idea to practice by developing a low complexity decoder for short Markov codes, which displays competitive performance in simulations at low SNRs. Our decoder design combines the sequence prediction capability of recurrent neural networks with the assured performance of maximum a posteriori (MAP) decoders like the BCJR decoder.

We model an epidemic where the per-person infectiousness in a network of geographic localities changes with the total number of active cases. This would happen as people adopt more stringent non-pharmaceutical precautions when the population has a larger number of active cases. We show that there exists a sharp threshold such that when the curing rate for the infection is above this threshold, the expected time for the epidemic to die out is logarithmic in the initial infection size, whereas when the curing rate is below this threshold, the expected time for epidemic extinction is infinite. We also show that when the per-person infectiousness goes to zero asymptotically as a function of the number of active cases, the expected extinction times all have the same asymptote independent of network structure. We make no mean-field assumption while deriving these results. Simulations on real-world network topologies bear out these results, while also demonstrating that if the per-person infectiousness is large when the epidemic size is small (i.e., the precautions are lax when the epidemic is small and only get stringent after the epidemic has become large), it might take a very long time for the epidemic to die out. We also provide some analytical insight into these observations.

In this era of fast and large-scale opinion formation, a mathematical understanding of opinion evolution, a.k.a. opinion dynamics, is especially important. Linear graph-based dynamics and bounded confidence dynamics are the two most popular models for opinion dynamics in social networks. Recently, stochastic bounded confidence opinion dynamics were proposed as a general framework that incorporates both these dynamics as special cases and also captures the inherent stochasticity and noise (errors) in real-life social exchanges. Although these dynamics are quite general and realistic, their analysis is particularly challenging compared to other opinion dynamics models. This is because these dynamics are nonlinear and stochastic, and belong to the class of Markov processes that have asymptotically zero drift and unbounded jumps. The asymptotic behavior of these dynamics was characterized in prior works. However, they do not shed light on their finite-time behavior, which is often of interest in practice. We take a stride in this direction by analyzing the finite time behavior of a two-agent system, which is fundamental to the understanding of multi-agent dynamics. In particular, we show that the opinion difference between the two agents is well concentrated around zero under the conditions that lead to asymptotic stability of the dynamics.