Controlled research on AI ideation typically compares independent agents, while field studies of human–AI collaboration sacrifice experimental control. We introduce a controlled, two-player extension of the Alternate Uses Test (AUT) that enables comparison of human–human and human–AI co-creation under matched interactive conditions, alongside calibrated non-interactive baselines. The platform supports decomposition of performance into three typically confounded factors: participant traits, partner perceptions, and content dynamics. An in-person pilot (N = 62) demonstrates its utility. Under matched time limits, originality with a GPT-4 partner is statistically equivalent to that with a human partner. Approach motivation (BAS Drive) moderates whether interactive partnership benefits originality, and self-reported cognitive outsourcing predicts lower originality specifically in human–human dyads. Prior exposure to highly creative ideas improves later performance, suggesting a “seeding” intervention. We release the platform, code, and dataset as a shared testbed for controlled studies of human–AI co-creation.

Fault-tolerant quantum computation demands extremely low logical error rates, yet superconducting qubit arrays are subject to radiation-induced correlated noise arising from cosmic-ray muon-generated quasiparticles. The quasiparticle density is unknown and time-varying, resulting in a mismatch between the true noise statistics and the priors assumed by standard decoders, and consequently, degraded logical performance. We formalize joint noise sensing and decoding using syndrome measurements by modeling the QP density as a latent variable, which governs correlation in physical errors and syndrome measurements. Starting from a variational expectation--maximization approach, we derive an iterative algorithm that alternates between QP density estimation and syndrome-based decoding under the updated noise model. Simulations of surface-code and bivariate bicycle quantum memory under radiation-induced correlated noise demonstrate a measurable reduction in logical error probability relative to baseline decoding with a uniform prior. Beyond improved decoding performance, the inferred QP density provides diagnostic information relevant to device characterization, shielding, and chip design. These results indicate that integrating physical noise estimation into decoding can mitigate correlated noise effects and relax effective error-rate requirements for fault-tolerant quantum computation.

Realizing the vision of using AI agents to automate critical IT tasks depends on the ability to measure and understand effectiveness of proposed solutions. We introduce ITBench, a framework that offers a systematic methodology for benchmarking AI agents to address real-world IT automation tasks. Our initial release targets three key areas: Site Reliability Engineering (SRE), Compliance and Security Operations (CISO), and Financial Operations (FinOps). The design enables AI researchers to understand the challenges and opportunities of AI agents for IT automation with push-button workflows and interpretable metrics. IT-Bench includes an initial set of 102 real-world scenarios, which can be easily extended by community contributions. Our results show that agents powered by state-of-the-art models resolve only 11.4% of SRE scenarios, 25.2% of CISO scenarios, and 25.8% of FinOps scenarios (excluding anomaly detection). For FinOps-specific anomaly detection (AD) scenarios, AI agents achieve an F1 score of 0.35. We expect ITBench to be a key enabler of AI-driven IT automation that is correct, safe, and fast. IT-Bench, along with a leaderboard and sample agent implementations, is available at https://github.com/ibm/itbench.

Moral judgment is integral to large language models' (LLMs) social reasoning. As multi-agent systems gain prominence, it becomes crucial to understand how LLMs function when collaborating compared to operating as individual agents. In human moral judgment, group deliberation leads to a Utilitarian Boost: a tendency to endorse norm violations that inflict harm but maximize benefits for the greatest number of people. We study whether a similar dynamic emerges in multi-agent LLM systems. We test six models on well-established sets of moral dilemmas across two conditions: (1) Solo, where models reason independently, and (2) Group, where they engage in multi-turn discussions in pairs or triads. In personal dilemmas, where agents decide whether to directly harm an individual for the benefit of others, all models rated moral violations as more acceptable when part of a group, demonstrating a Utilitarian Boost similar to that observed in humans. However, the mechanism for the boost in LLMs differed: While humans in groups become more utilitarian due to heightened sensitivity to decision outcomes, LLM groups showed diverse profiles, for example, reduced sensitivity to norms or enhanced impartiality. We report model differences in when and how strongly the boost manifests. We also discuss prompt and agent compositions that enhance or mitigate the effect. We end with a discussion of the implications for AI alignment, multi-agent design, and artificial moral reasoning. Code available at: https://github.com/baltaci-r/MoralAgents

While the public views the federal government as a monolith, in truth United States departments and agencies often function independently. Due to privacy regulations and statutory reasons, they often cannot share data about individuals with each other. Yet, such data collaboration would facilitate the development of artificial intelligence models to significantly improve the provision of social services. We argue that a particular privacy-enhancing technology (split learning operating over vertically partitioned data), together with data governance through metadata supply chains, can be part of larger sociotechnical systems that can improve life for the most vulnerable among us.

We consider the fractional influence maximization problem, i.e., identifying users on a social network to be incentivized with potentially partial discounts to maximize the influence on the network. The larger the discount given to a user, the higher the likelihood of its activation (adopting a new product or innovation), who then attempts to activate its neighboring users, causing a cascade effect of influence through the network. Our goal is to devise efficient algorithms that assign initial discounts to the network's users to maximize the total number of activated users at the end of the cascade, subject to a constraint on the total sum of discounts given. In general, the activation likelihood could be any non-decreasing function of the discount, whereas, our focus lies on the case when the activation likelihood is an affine function of the discount, potentially varying across different users. As this problem is shown to be NP-hard, we propose and analyze an efficient (1-1/e)-approximation algorithm. Furthermore, we run experiments on real-world social networks to show the performance and scalability of our method.

This paper introduces a universal federated learning framework that enables over-the-air computation via digital communications, using a new joint source-channel coding scheme. Without relying on channel state information at devices, this scheme employs lattice codes to both quantize model parameters and exploit interference from the devices. A novel two-layer receiver structure at the server is designed to reliably decode an integer combination of the quantized model parameters as a lattice point for the purpose of aggregation. Numerical experiments validate the effectiveness of the proposed scheme. Even with the challenges posed by channel conditions and device heterogeneity, the proposed scheme markedly surpasses other over-the-air FL strategies.

This paper presents a queuing-theoretic framework to analyze the business of business-to-customer carsharing services with electric vehicle (EV) fleets. When grid-connected, EVs can use their batteries for vehicle-to-grid (V2G) interactions. In this work, we allow a carsharing platform to conceptually split its EV batteries into two parts: one part to provide transportation to carsharing customers and another for energy trading. We characterize the optimal storage control policy for price arbitrage during transportation-idle times and leverage equilibrium analysis of$M/G/N/N$queues with$N$cars to calculate the platform’s average revenue rate from dual service provision. For the single-EV case, we explicitly characterize the optimal price, both with patient and impatient customers. For the general$N$-car case, we provide an algorithm to maximize revenue rate over price and battery split, and utilize the algorithm to numerically study the variation of the optimal solutions with problem parameters.

We introduce equi-tuning, a novel fine-tuning method that transforms (potentially non-equivariant) pretrained models into group equivariant models while incurring minimum L_2 loss between the feature representations of the pretrained and the equivariant models. Large pretrained models can be equi-tuned for different groups to satisfy the needs of various downstream tasks. Equi-tuned models benefit from both group equivariance as an inductive bias and semantic priors from pretrained models. We provide applications of equi-tuning on three different tasks: image classification, compositional generalization in language, and fairness in natural language generation (NLG). We also provide a novel group-theoretic definition for fairness in NLG. The effectiveness of this definition is shown by testing it against a standard empirical method of fairness in NLG. We provide experimental results for equi-tuning using a variety of pretrained models: Alexnet, Resnet, VGG, and Densenet for image classification; RNNs, GRUs, and LSTMs for compositional generalization; and GPT2 for fairness in NLG. We test these models on benchmark datasets across all considered tasks to show the generality and effectiveness of the proposed method.

Learning models that are robust to distribution shifts is a key concern in the context of their real-life applicability. Invariant Risk Minimization (IRM) is a popular framework that aims to learn robust models from multiple environments. The success of IRM requires an important assumption: the underlying causal mechanisms/features remain invariant across environments. When not satisfied, we show that IRM can over-constrain the predictor and to remedy this, we propose a relaxation via partial invariance. In this work, we theoretically highlight the sub-optimality of IRM and then demonstrate how learning from a partition of training domains can help improve invariant models. Several experiments, conducted both in linear settings as well as with deep neural networks on tasks over both language and image data, allow us to verify our conclusions.

While smell is arguably the most visceral of senses, olfactory computing has been barely explored in the mainstream. We argue that this is a good time to explore olfactory computing since a) a large number of driver applications are emerging, b) odor sensors are now dramatically better, and c) non-traditional form factors such as sensor, wearable, and xR devices that would be required to support olfactory computing are already getting widespread acceptance. Through a comprehensive review of literature, we identify the key algorithms needed to support a wide variety of olfactory computing tasks. We profiled these algorithms on existing hardware and identified several characteristics, including the preponderance of fixed-point computation, and linear operations, and real arithmetic; a variety of data memory requirements; and opportunities for data-level parallelism. We propose Ahromaa, a heterogeneous architecture for olfactory computing targeting extremely power and energy constrained olfactory computing workloads and evaluate it against baseline architectures of an MCU, a state-of-art CGRA, and an MCU with packed SIMD. Across our algorithms, Ahromaa's operating modes outperform the baseline architectures by 1.36, 1.22, and 1.1× in energy efficiency when operating at MEOP. We also show how careful design of data memory organization can lead to significant energy savings in olfactory computing, due to the limited amount of data memory many olfactory computing kernels require. These improvements to the data memory organization lead to additional 4.21, 4.37, and 2.85× improvements in energy efficiency on average.

Efficient transfer learning algorithms are key to the success of foundation models on diverse downstream tasks even with limited data. Recent works of Basu et al. (2023) and Kaba et al. (2022) propose group averaging (equitune) and optimization-based methods, respectively, over features from group-transformed inputs to obtain equivariant outputs from non-equivariant neural networks. While Kaba et al. (2022) are only concerned with training from scratch, we find that equitune performs poorly on equivariant zero-shot tasks despite good finetuning results. We hypothesize that this is because pretrained models provide better quality features for certain transformations than others and simply averaging them is deleterious. Hence, we propose λ-equitune that averages the features using importance weights, λs. These weights are learned directly from the data using a small neural network, leading to excellent zero-shot and finetuned results that outperform equitune. Further, we prove that λ-equitune is equivariant and a universal approximator of equivariant functions. Additionally, we show that the method of Kaba et al. (2022) used with appropriate loss functions, which we call equizero, also gives excellent zero-shot and finetuned performance. Both equitune and equizero are special cases of λ- equitune. To show the simplicity and generality of our method, we validate on a wide range of diverse applications and models such as 1) image classification using CLIP, 2) deep Q-learning, 3) fairness in natural language generation (NLG), 4) compositional generalization in languages, and 5) image classification using pretrained CNNs such as Resnet and Alexnet.

We propose Information Lattice Learning (ILL) as a general framework to learn rules of a signal (e.g., an image or a probability distribution). In our definition, a rule is a coarsened signal used to help us gain one interpretable insight about the original signal. To make full sense of what might govern the signal’s intrinsic structure, we seek multiple disentangled rules arranged in a hierarchy, called a lattice. Compared to representation/rule-learning models optimized for a specific task (e.g., classification), ILL focuses on explainability: it is designed to mimic human experiential learning and discover rules akin to those humans can distill and comprehend. This paper details the math and algorithms of ILL, and illustrates how it addresses the fundamental question “what makes X an X” by creating rule-based explanations designed to help humans understand. Our focus is on explaining X rather than (re)generating it. We present applications in knowledge discovery, using ILL to distill music theory from scores and chemical laws from molecules and further revealing connections between them. We show ILL’s efficacy and interpretability on benchmarks and assessments, as well as a demonstration of ILL-enhanced classifiers achieving human-level digit recognition using only one or a few MNIST training examples (1–10 per class).

Humans' abstraction ability plays a key role in concept learning and knowledge discovery. This theory paper presents the mathematical formulation for computationally emulating human-like abstractions---computational abstraction---and abstraction processes developed hierarchically from innate priors like symmetries. We study the nature of abstraction via a group-theoretic approach, formalizing and practically computing abstractions as symmetry-driven hierarchical clustering. Compared to data-driven clustering like k-means or agglomerative clustering (a chain), our abstraction model is data-free, feature-free, similarity-free, and globally hierarchical (a lattice). This paper also serves as a theoretical generalization of several existing works. These include generalizing Shannon's information lattice, specialized algorithms for certain symmetry-induced clusterings, as well as formalizing knowledge discovery applications such as learning music theory from scores and chemistry laws from molecules. We consider computational abstraction as a first step towards a principled and cognitive way of achieving human-level concept learning and knowledge discovery.

We address the design of inference-oriented communication systems where multiple transmitters send partial inference values through noisy communication channels, and the receiver aggregates these channel outputs to obtain a reliable final inference. Since large data items are replaced by compact inference values, these systems lead to significant savings of communication resources. In particular, we present a principled framework to optimize communication-resource allocation for distributed boosting classifiers. Boosting classification algorithms make a final decision via a weighted vote from the outputs of multiple base classifiers. Since these base classifiers transmit their partial inference values over noisy channels, communication errors would degrade the final classification accuracy. We formulate communication resource allocation problems to maximize the final classification accuracy by taking into account the importance of base classifiers and the resource budget. To solve these problems rigorously, we formulate convex optimization problems to optimize: 1) transmit-power allocations and 2) transmit-rate allocations. This framework departs from classical communication-systems optimizations in seeking to maximize the classification accuracy rather than the reliability of the individual communicated bits. Results from numerical experiments demonstrate the benefits of our approach.

Concrete is the most widely used engineered material in the world with more than 10 billion tons produced annually. Unfortunately, with that scale comes a significant burden in terms of energy, water, and release of greenhouse gases and other pollutants; indeed 8% of worldwide carbon emissions are attributed to the production of cement, a key ingredient in concrete. As such, there is interest in creating concrete formulas that minimize this environmental burden, while satisfying engineering performance requirements including compressive strength. Specifically for computing, concrete is a major ingredient in the construction of data centers.

Group testing has been successful in minimizing the cost of testing a large batch of samples by pooling them together. In this work, we study the setting where samples arrive over time. Since not all samples are available at the same time, we incur a waiting cost in letting many samples accumulate. However, testing too soon leads to a large testing cost by missing the benefits of pooling a larger number of samples. We consider the problem of minimizing the combined objective of average wait time plus testing cost, and develop online algorithms that are provably competitive for a broad range of testing-cost functions. We also give a lower bound on the competitive ratio that no online algorithm can beat.

This paper studies the adversarial graphical contextual bandits, a variant of adversarial multi-armed bandits that leverage two categories of the most common side information: contexts and side observations. In this setting, a learning agent repeatedly chooses from a set of K actions after being presented with a d-dimensional context vector. The agent not only incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures, which are encoded as a series of feedback graphs. This setting models a variety of applications in social networks, where both contexts and graph-structured side observations are available. Two efficient algorithms are developed based on EXP3. Under mild conditions, our analysis shows that for undirected feedback graphs the first algorithm, EXP3-LGC-U, achieves a sub-linear regret with respect to the time horizon and the average independence number of the feedback graphs. A slightly weaker result is presented for the directed graph setting as well. The second algorithm, EXP3-LGC-IX, is developed for a special class of problems, for which the regret is the same for both directed as well as undirected feedback graphs. Numerical tests corroborate the efficiency of proposed algorithms.

Disparate access to resources by different subpopulations is a prevalent issue in societal and sociotechnical networks. For example, urban infrastructure networks may enable certain racial groups to more easily access resources such as high-quality schools, grocery stores, and polling places. Similarly, social networks within universities and organizations may enable certain groups to more easily access people with valuable information or influence. Here we introduce a new class of problems, Graph Augmentation for Equitable Access (GAEA), to enhance equity in networked systems by editing graph edges under budget constraints. We prove such problems are NP-hard, and cannot be approximated within a factor of (1-1/3e). We develop a principled, sample- and time- efficient Markov Reward Process (MRP)-based mechanism design framework for GAEA. Our algorithm outperforms baselines on a diverse set of synthetic graphs. We further demonstrate the method on real-world networks, by merging public census, school, and transportation datasets for the city of Chicago and applying our algorithm to find human-interpretable edits to the bus network that enhance equitable access to high-quality schools across racial groups. Further experiments on Facebook networks of universities yield sets of new social connections that would increase equitable access to certain attributed nodes across gender groups.

Many information sources are not just sequences of distinguishable symbols but rather have invariances governed by alternative counting paradigms such as permutations, combinations, and partitions. We consider an entire classification of these invariances called the twelvefold way in enumerative combinatorics and develop a method to characterize lossless compression limits. Explicit computations for all twelve settings are carried out for i.i.d. uniform and Bernoulli distributions. Comparisons among settings provide quantitative insight.

Cascading bandit (CB) is a popular model for web search and online advertising. However, the stationary CB model may be too simple to cope with real-world problems, where user preferences may change over time. Considering piecewise-stationary environments, two efficient algorithms, GLRT-CascadeUCB and GLRT-CascadeKL-UCB, are developed. Comparing with existing works, the proposed algorithms: i) are free of change-point-dependent information for choosing parameters; ii) have fewer tuning parameters; iii) improve regret upper bounds. We also show that the proposed algorithms are optimal up to logarithm terms by deriving a minimax lower bound $\Omega (\sqrt {NLT} )$ for piecewise-stationary CB. The efficiency of the proposed algorithms is validated through numerical tests on a real-world benchmark dataset.

This paper considers Deep Neural Network (DNN) linear-nonlinear computations implemented on memristor cross-bar substrates. To address the case where true memristor conductance values may differ from their target values, it introduces a theoretical framework that characterizes the effect of conductance value variations on the final inference computation. With only second-order moment assumptions, theoretical results on tracking the mean, variance, and covariance of the layer-by-layer noisy computations are given. By allowing the possibility of amplifying certain signals within the DNN, power consumption is characterized and then optimized via KKT conditions. Simulation results verify the accuracy of the proposed analysis and demonstrate the significant power efficiency gains that are possible via optimization for a target mean squared error.

Evaluating the inherent difficulty of a given data-driven classification problem is important for establishing absolute benchmarks and evaluating progress in the field. To this end, a natural quantity to consider is the \emph{Bayes error}, which measures the optimal classification error theoretically achievable for a given data distribution. While generally an intractable quantity, we show that we can compute the exact Bayes error of generative models learned using normalizing flows. Our technique relies on a fundamental result, which states that the Bayes error is invariant under invertible transformation. Therefore, we can compute the exact Bayes error of the learned flow models by computing it for Gaussian base distributions, which can be done efficiently using Holmes-Diaconis-Ross integration. Moreover, we show that by varying the temperature of the learned flow models, we can generate synthetic datasets that closely resemble standard benchmark datasets, but with almost any desired Bayes error. We use our approach to conduct a thorough investigation of state-of-the-art classification models, and find that in some --- but not all --- cases, these models are capable of obtaining accuracy very near optimal. Finally, we use our method to evaluate the intrinsic "hardness" of standard benchmark datasets.

Constrained coding is used widely in digital communication and storage systems. In this article, we study a generalized sliding window constraint called the skip-sliding window. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L + kJ is determined by k+1 windows of length L where window i starts at (iJ + 1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. SSW coding constraints naturally arise in applications such as simultaneous energy and information transfer, and SSW codes are also potential candidates for visible light communications. In this work, two methods are given to enumerate the size of SSW codes and further refinements are made to reduce the enumeration complexity. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and some useful observations are made, such as the fact that SSW codes provide greater capacity than certain related classes of constrained codes. Moreover, we provide noisy capacity bounds for SSW codes.

The CEO problem has received much attention since first introduced by Berger et al., but there are limited results on non-Gaussian models with non-quadratic distortion measures. In this work, we extend the quadratic Gaussian CEO problem to two non-Gaussian settings with general rth power of difference distortion. Assuming an identical observation channel across agents, we study the asymptotics of distortion decay as the number of agents and sum-rate, Rsum, grow without bound, while individual rates vanish. The first setting is a regular source-observation model with rth power of difference distortion, which subsumes the quadratic Gaussian CEO problem, and we establish that the distortion decays atO(Rsum-r/2) when r ≥ 2. We use sample median estimation after the Berger-Tung scheme for achievability. The other setting is a non-regular source-observation model, including uniform additive noise models, with rth power of difference distortion for which estimation-theoretic regularity conditions do not hold. The distortion decayO(Rsum-r) when r ≥ 1 is obtained for the non-regular model by midrange estimator following the Berger-Tung scheme. We also provide converses based on the Shannon lower bound for the regular model and the Chazan-Zakai-Ziv bound for the non-regular model, respectively. Lastly, we provide a sufficient condition for the regular model, under which quadratic and logarithmic distortions are asymptotically equivalent by an entropy power relationship as the number of agents grows. This proof relies on the Bernstein-von Mises theorem.

Blockchains store transaction data in the form of a distributed ledger where each node in the network stores a current copy of the sequence of transactions as a hash chain. This requirement of storing the entire ledger incurs a high storage cost that grows undesirably large for high transaction rates and large networks. In this work we use secret key sharing, private key encryption, and distributed storage to design a coding scheme such that each node stores only a part of each transaction, thereby reducing the cold storage cost to a fraction of its original cost. In addition, the storage code ensures the security of the storage from active adversaries that may aim to corrupt prior transactions by altering copies of the ledger. We further employ a dynamic zone allocation algorithm that spreads the node allocation and data distribution across transactions. Under this coding scheme we show that we can also improve the integrity of the transaction data in the network over current schemes.

We investigate the piecewise-stationary combinatorial semi-bandit problem. Compared to the original combinatorial semi-bandit problem, our setting assumes the reward distributions of base arms may change in a piecewise-stationary manner at unknown time steps. We propose an algorithm, GLR-CUCB, which incorporates an efficient combinatorial semi-bandit algorithm, CUCB, with an almost parameter-free change-point detector, the Generalized Likelihood Ratio Test (GLRT). Our analysis shows that the regret of GLR-CUCB is upper bounded by O(√NKT log T), where N is the number of piecewise-stationary segments, K is the number of base arms, and T is the number of time steps. As a complement, we also derive a nearly matching regret lower bound on the order of Ω(√NKT), for both piecewise-stationary multi-armed bandits and combinatorial semi-bandits, using information-theoretic techniques and judiciously constructed piecewise-stationary bandit instances. Our lower bound is tighter than the best available regret lower bound, which is Ω(√T). Numerical experiments on both synthetic and real-world datasets demonstrate the superiority of GLR-CUCB compared to other state-of-the-art algorithms.

We consider the problem of coding for computing with maximal distortion, where the sender communicates with a receiver, which has its own private data and wants to compute a function of their combined data with some fidelity constraint known to both agents. We show that the minimum rate for this problem is equal to the conditional entropy of a hypergraph and design practical codes for the problem. Further, the minimum rate of this problem may be a discontinuous function of the fidelity constraint. We also consider the case when the exact function is not known to the sender, but some approximate function or a class to which the function belongs is known and provide efficient achievable schemes.

Inflectional variation is a common feature of World Englishes such as Colloquial Singapore English and African American Vernacular English.Although comprehension by human readers is usually unimpaired by nonstandard inflections, current NLP systems are not yet robust.We propose Base-Inflection Encoding (BITE), a method to tokenize English text by reducing inflected words to their base forms before reinjecting the grammatical information as special symbols.Fine-tuning pretrained NLP models for downstream tasks using our encoding defends against inflectional adversaries while maintaining performance on clean data.Models using BITE generalize better to dialects with non-standard inflections without explicit training and translation models converge faster when trained with BITE.Finally, we show that our encoding improves the vocabulary efficiency of popular data-driven subword tokenizers.Since there has been no prior work on quantitatively evaluating vocabulary efficiency, we propose metrics to do so. 1

We consider two problems in multiterminal source coding under maximal distortion: distributed coding for computing and successive refinement. In distributed coding for computing, we propose a hypergraph-based coding scheme which matches the sum-rate bound of the Berger-Tung inner bound. Further, this scheme matches the entire Berger-Tung inner region when the sources are independent and it outperforms existing graph-based coding schemes. For successive refinement, we propose a hypergraph-based scheme that attains the entire rate region.

International audience

We study the problem of image registration in the finite-resolution regime and characterize the error probability of algorithms as a function of properties of the transformation and the image capture noise. Specifically, we define a channel-aware Feinstein decoder to obtain upper bounds on the minimum achievable error probability under finite resolution. We specifically focus on the higher-order terms and use Berry-Esseen type CLTs to obtain a stronger characterization of the achievability condition for the problem. Then, we derive a strong type-counting result to characterize the performance of the MMI decoder in terms of the maximum likelihood decoder, in a simplified setting of the problem. We then describe how this analysis, when related to the results from the channel-aware context provide stronger characterization of the finite-sample performance of universal image registration.

Consider a social learning problem in a parallel network, where N distributed agents make independent selfish binary decisions, and a central agent aggregates them together with a private signal to make a final decision. In particular, all agents have private beliefs for the true prior, based on which they perform binary hypothesis testing. We focus on the Bayes risk of the central agent, and counterintuitively find that a collection of agents with incorrect beliefs could outperform a set of agents with correct beliefs. We also consider many-agent asymptotics (i.e., N is large) when distributed agents all have identical beliefs, for which it is found that the central agent's decision is polarized and beliefs determine the limit value of the central agent's risk. Moreover, it is surprising that when all agents believe a certain prior-agnostic constant belief, it achieves globally optimal risk as N → ∞.

The "bee-identification problem" was formally defined by Tandon, Tan and Varshney [IEEE Trans. Commun., vol. 67, 2019], and the error exponent was studied. This work extends the results for the "absentee bees" scenario, where a small fraction of the bees are absent in the beehive image used for identification. For this setting, we present an exact characterization of the bee-identification error exponent, and show that independent barcode decoding is optimal, i.e., joint decoding of the bee barcodes does not result in a better error exponent relative to independent decoding of each noisy barcode. This is in contrast to the result without absentee bees, where joint barcode decoding results in a significantly higher error exponent than independent barcode decoding. We also define and characterize the `capacity' for the bee-identification problem with absentee bees, and prove the strong converse for the same.

Full-duplex communication allows a terminal to transmit and receive signals simultaneously, and hence, it is helpful in general to adapt transmissions to received signals. However, this often requires unaffordable complexity. This work focuses on simple non-adaptive transmission, and provides two classes of channels for which Shannon's information capacity regions are achieved without adaptation. The first is the injective semi-deterministic two-way channel that includes additive channels with various types of noises modeling wireless, coaxial cable, and other settings. The other is the Poisson two-way channel, for which we show that non-adaptive transmission is asymptotically optimal in the high dark current regime.

Most current machine learning algorithms make highly confident yet incorrect classifications when faced with unexpected test samples from an unknown distribution different from training; such epistemic uncertainty (unknown unknowns) can have catastrophic safety implications. In this conceptual paper, we propose a method to leverage engineering science knowledge to control epistemic uncertainty and maintain decision safety. The basic idea is an algorithm fusion approach that combines data-driven learned models with physical system knowledge, to operate between the extremes of purely data-driven classifiers and purely engineering science rules. This facilitates the safe operation of data-driven engineering systems, such as wastewater treatment plants.

Recursive estimation is a basic operation in statistical inference that may be implemented and deployed on faulty hardware with error rates governed by energy consumption. We analyze the loss in estimation performance due to noise in recursive probability computation for the binary case, and develop an optimal energy allocation strategy. Simulations show the validity of analytical bounds.

This paper considers the problem of simultaneous information and energy transmission (SIET), where the energy harvesting function is only known experimentally at sample points. We investigate the performance loss due to this partial knowledge of the harvesting function in terms of transmitted energy and information. In particular, we assume harvesting functions are a class of Sobolev space and consider two cases, where experimental samples are either taken noiselessly or in the presence of noise. Using constructive function approximation and regression methods for noiseless and noisy samples respectively, we show that the worst loss in energy transmission vanishes asymptotically as the number of samples increases. Similarly, the loss in information rate vanishes in the interior of the energy domain, however, does not always vanish at maximal energy.

The CEO problem has received a lot of attention since Berger et al. first investigated it, however, there are limited results on non-Gaussian models with non-quadratic distortion measures. In this work, we extend the CEO problem to two continuous-alphabet settings with general rth power of difference distortion, and study asymptotics of distortion as the number of agents and sum rate grow without bound. The first setting is a regular source-observation model, such as jointly Gaussian, with difference distortion and we show that the distortion decays at Rsum-r/2up to a multiplicative constant. The other setting is a non-regular source-observation model, such as copula or uniform additive noise models, for which estimation-theoretic regularity conditions do not hold. The optimal decay Rsum-ris obtained for the non-regular model.

Communication systems for multicasting information and energy simultaneously to more than one user are investigated. In the system under study, a transmitter sends the same message and signal to multiple receivers over distinct and independent channels. The fundamental communication limit under a received energy constraint, called the multicast capacity-energy function, is studied and a single-letter expression is derived. This is based on coding theorems for compound channels. The problem of receiver segmentation, where receivers are divided into related groups, is also considered.

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We introduce this “bee-identification problem characterize the random coding exponent, and derive efficiently computable bounds for this exponent. We demonstrate that joint decoding of barcodes has much better exponent than separate decoding followed by permutation inference.

We consider binary skip-sliding window (SSW) codes which satisfy certain weight constraints over a skip-sliding window. When on-off keying is employed, these weight constraints ensure real-time energy content in the transmitted signal. For a given energy requirement and battery size at an energy harvesting receiver, we investigate the maximum achievable rate using SSW codes which avoid energy outage at the receiver. The SSW codes generalize sliding window constrained (SWC) codes and subblock energy constrained (SEC) codes; we show that SSW codes with window length equal to twice the skip-length can outperform both SWC and SEC codes in terms of outage-constrained rate.

Modern day computing systems are based on the von Neumann architecture proposed in 1945 but face dual challenges of: 1) unique data-centric requirements of emerging applications and 2) increased nondeterminism of nanoscale technologies caused by process variations and failures. This paper presents a Shannon-inspired statistical model of computation (statistical computing) that addresses the statistical attributes of both emerging cognitive workloads and nanoscale fabrics within a common framework. Statistical computing is a principled approach to the design of non-von Neumann architectures. It emphasizes the use of information-based metrics; enables the determination of fundamental limits on energy, latency, and accuracy; guides the exploration of statistical design principles for low signal-to-noise ratio (SNR) circuit fabrics and architectures such as deep in-memory architecture (DIMA) and deep in-sensor architecture (DISA); and thereby provides a framework for the design of computing systems that approach the limits of energy efficiency, latency, and accuracy. From its early origins, Shannon-inspired statistical computing has grown into a concrete design framework validated extensively via both theory and laboratory prototypes in both CMOS and beyond. The framework continues to grow at both of these levels, yielding new ways of connecting systems through architectures, circuits, and devices, for the semiconductor roadmap to march into the nanoscale era.

This paper considers the problem of simultaneous information and energy transmission, where the energy harvesting function is only known experimentally at sample points, e.g., due to nonlinearities and parameter uncertainties in harvesting circuits. We investigate the performance loss due to this partial knowledge of the harvesting function in terms of transmitted energy and information. In particular, we assume that the harvesting function is a subclass of the Sobolev space and consider two cases, where the experimental samples are either taken noiselessly or in the presence of noise. Using constructive function approximation and regression methods for noiseless and noisy samples, respectively, we show that the worst loss in energy transmission vanishes asymptotically as the number of samples increase. Similarly, the loss in information rate vanishes in the interior of the energy domain; however, it does not always vanish at maximal energy. We further show that the same principle applies in multicast settings, such as medium access in the Wi-Fi protocol. We also consider the end-to-end source-channel communication problem under source distortion constraint and channel energy requirement, where both distortion and harvesting functions are known only at samples.

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We formally introduce this “bee-identification problem”, define its error exponent, and derive efficiently computable upper and lower bounds for this exponent. We show that joint decoding of barcodes provides a significantly better exponent compared to separate decoding followed by permutation inference. For low rates, we prove that the lower bound on the bee-identification exponent obtained using typical random codes (TRC) is strictly better than the corresponding bound obtained using a random code ensemble (RCE). Further, as the rate approaches zero, we prove that the upper bound on the bee-identification exponent meets the lower bound obtained using TRC with joint barcode decoding.

This paper investigates the fundamental limits of communication over a noisy discrete memoryless channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. Constant composition codes are adopted to obtain an achievability bound, and the left-concave right-convex inequality is then refined to obtain a converse bound on the log-volume throughput for channels that wear out. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure, and therefore cannot convey information at positive rates, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. Numerical results demonstrate that a sequence of block codes is preferred to a single block code for streaming sources.

Computational creativity is an emerging branch of artificial intelligence (AI) concerned with algorithms that can create novel and high-quality ideas or artifacts, either autonomously or semi-autonomously in collaboration with people. Quite simply, such algorithms may be described as artificial innovation engines. These technologies raise questions of authorship/inventorship and of agency, which become further muddled by the social context induced by AI that may be physically-embodied or anthropomorphized. These questions are fundamentally intertwined with the provision of appropriate incentives for conducting and commercializing computational creativity research through intellectual property regimes. This paper reviews current understanding of intellectual property rights for AI, and explores possible framings for intellectual property policy in social context.

This work explores sequential Bayesian binary hypothesis testing in the social learning setup under expertise diversity. We consider a two-agent (say advisor-learner) sequential binary hypothesis test where the learner infers the hypothesis based on the decision of the advisor, a prior private signal, and individual belief. In addition, the agents have varying expertise, in terms of the noise variance in the private signal. Under such a setting, we first investigate the behavior of optimal agent beliefs and observe that the nature of optimal agents could be inverted depending on expertise levels. We also discuss suboptimality of the Prelec reweighting function under diverse expertise. Next, we consider an advisor selection problem wherein the belief of the learner is fixed and the advisor is to be chosen for a given prior. We characterize the decision region for choosing such an advisor and argue that a learner with beliefs varying from the true prior often ends up selecting a suboptimal advisor.

We propose an information-theoretic approach to optimize non-uniform bit-line swings for static random access memories (SRAMs). We formulate convex optimization problems whose objectives are to minimize energy (for low-power SRAMs), maximize speed (for high-speed SRAMs), and minimize energy-delay product for a given constraint on mean squared error of retrieved words. We show that these optimization problems can be interpreted as generalized water-filling including classical waterfilling, ground-flattening and water-filling, and sand-pouring and water-filling, respectively. Numerical results show that energy-optimal swing assignment reduces energy consumption by half at a peak signal-to-noise ratio of 30dB for an 8-bit accessed word.

Blockchain uses the idea of storing transaction data in the form of a distributed ledger wherein each node in the network stores a current copy of the sequence of transactions (ledger) in the form of a hash chain. Storing the entire ledger incurs a high storage cost that grows undesirably large for high transaction rates and large networks. In this work we use secret key sharing, private key encryption, and distributed storage to design a coding scheme such that each node stores only a part of each transaction thereby reducing storage cost to a fraction of the original. When further using dynamic zone allocation, we show the coding scheme can also improve the data integrity.

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 GIk/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.

Constrained coding is used widely in digital communication and storage systems. In this paper, we study a generalized sliding window constraint called the skip-sliding window constraint. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L+kJ is determined by k+1 windows of length L where window i starts at (iJ+1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. In this work, two methods are given to enumerate the size of SSW codes. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and observations such as greater capacity than other classes of codes are made. Moreover, some noisy capacity bounds are given. SSW coding constraints arise in various applications including simultaneous energy and information transfer.

Conventional low-power static random access memories (SRAMs) reduce read energy by decreasing the bit-line voltage swings uniformly across the bit-line columns. This is because the read energy is proportional to the bit-line swings. On the other hand, bit-line swings are limited by the need to avoid decision errors especially in the most significant bits. We propose a principled approach to determine optimal non-uniform bit-line swings by formulating convex optimization problems. For a given constraint on mean squared error of retrieved words, we consider criteria to minimize energy (for low-power SRAMs), maximize speed (for high-speed SRAMs), and minimize energy-delay product. These optimization problems can be interpreted as classical water-filling, ground-flattening and water-filling, and sand-pouring and water-filling, respectively. By leveraging these interpretations, we also propose greedy algorithms to obtain optimized discrete swings. Numerical results show that energy-optimal swing assignment reduces energy consumption by half at a peak signal-to-noise ratio of 30 dB for an 8-bit accessed word. The energy savings increase to four times for a 16-bit accessed word.

No abstract available.

Deep neural networks have shown incredible performance for inference tasks in a variety of domains. Unfortunately, most current deep networks are enormous cloud-based structures that require significant storage space, which limits scaling of deep learning as a service (DLaaS). This paper is concerned with finding universal lossless compressed representations of deep feedforward networkswith synaptic weights drawn from discrete sets. The basic insight that allows much less rate than naive approaches is the recognition that the bipartite graph layers of feedforward networks have a kind of permutation invariance to the labeling of nodes, in terms of inferential operation. We provide efficient algorithms to dissipate this irrelevant uncertainty and then use arithmetic coding to nearly achieve the entropy bound in a universal manner.

The College of Engineering at the University of Illinois at Urbana-Champaign has recently launched a new B. S. dual degree in Innovation, Leadership, and Engineering Entrepreneurship (ILEE), a second bachelor's degree option for those completing their degree in a traditional engineering discipline. This is unlike many universities where similar degree programs are situated in colleges of business rather than engineering. The first cohort of sixteen students has joined the program in January 2017. In this paper we first report on the stated goals of the new degree, which is meant to combine the technical expertise in the traditional engineering science-focused disciplines with a deeper set of skills in problem-finding, creativity, innovation, leadership, and externalization. The idea is to ensure training in the dual physical and human dimensions and triple aspects of science, design, and leadership that are present in engineering practice. Next we report on the curriculum design as well as the experiential learning pedagogy that is present in most of the courses therein. Core courses include “Design Thinking/Need-Finding”, “Creativity, Innovation, Vision”, “Emotional Intelligence”, “Innovation and Engineering Design”, and “Technology Entrepreneurship”. Further, we provide a characterization of the students in the first cohort of undergraduate students to be accepted into the degree program. Drawing on their application materials, we perform text analytics using techniques such as topic modeling under Latent Dirichlet Allocation (LDA) and geometric embedding using the word2vec family of methods, to understand the key motivations for students to pursue this degree. Finally we use these text analytics techniques to make a formal assessment of alignment between the stated goals of the degree program and the key motivations of the students. One particular question is to understand the students' relative level of interest in the three legs of the degree, namely innovation, leadership, and entrepreneurship, so as to predict how level of engagement may vary across courses.

The capacity region of the class of injective semi-deterministic two-way channels (TWCs) is investigated in this paper. To characterize this capacity, two conditions under which Shannon's bounds on the capacity region of TWCs are tight are first given. Using those conditions, it is shown that the capacity of this class of TWCs is characterized by the rectangle formed by the one-way capacities. This proves that adaptation is not needed for this class. This class encompasses, among others, all memoryless additive channels with input-independent noise, and hence, adaptation is useless for all such channels. This also shows that there exist continuous additive TWCs not of the exponential family type for which adaptation is not necessary. An example of a Cauchy TWC is given, and its capacity is characterized in closed form under a logarithmic constraint. Finally, the impact of the dependence of the noise on the inputs is discussed, and it is shown that adaptation may still be useless in such cases.

Due to the unprecedented success of deep neural networks in inference tasks like speech and image recognition, there has been increasing interest in using them in mobile and in-sensor applications. As most current deep neural networks are very large in size, a major challenge lies in storing the network in devices with limited memory. Consequently there is growing interest in compressing deep networks by quantizing synaptic weights, but most prior work is heuristic and lacking theoretical foundations. Here we develop an approach to quantizing deep networks using functional high-rate quantization theory. Under certain technical conditions, this approach leads to an optimal quantizer that is computed using the celebrated backpropagation algorithm. In all other cases, a heuristic quantizer with certain regularization guarantees can be computed.

This paper defines and studies the problem of universal clustering using responses of crowd workers, without knowledge of worker reliability or task difficulty. We model stochastic worker response distributions by incorporating traits of memory for similar objects and traits of distance among differing objects. We are particularly interested in two limiting worker types - temporary and long-term workers, without and with memory respectively. We first define clustering algorithms for these limiting cases and then integrate them into an algorithm for the unified worker model. We prove asymptotic consistency of the algorithms and establish sufficient conditions on the sample complexity of the algorithm. Converse arguments establish necessary conditions on sample complexity, proving that the defined algorithms are asymptotically order-optimal in cost.

The problem of joint clustering and registration of images is studied in a universal setting. We define universal joint clustering and registration algorithms using multivariate information functionals. We first study the problem of registering two images using maximum mutual information and prove its asymptotic optimality. We then show the shortcomings of pairwise registration in multi-image registration, and design an asymptotically optimal algorithm based on multi-information. Finally, we define a novel multivariate information functional to perform joint clustering and registration of images, and prove consistency of the algorithm.

This work investigates the limits of communication over a noisy channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. We restrict attention to constant composition codes. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure and therefore convey no information, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. A discussion of damage state feedback in channels that wear out is also provided. Numerical results show that a sequence of block codes is preferred to a single block code for streaming sources.

Abstraction and realization are bilateral processes that are key in deriving intelligence and creativity. In many domains, the two processes are approached through \emph{rules}: high-level principles that reveal invariances within similar yet diverse examples. Under a probabilistic setting for discrete input spaces, we focus on the rule realization problem which generates input sample distributions that follow the given rules. More ambitiously, we go beyond a mechanical realization that takes whatever is given, but instead ask for proactively selecting reasonable rules to realize. This goal is demanding in practice, since the initial rule set may not always be consistent and thus intelligent compromises are needed. We formulate both rule realization and selection as two strongly connected components within a single and symmetric bi-convex problem, and derive an efficient algorithm that works at large scale. Taking music compositional rules as the main example throughout the paper, we demonstrate our model's efficiency in not only music realization (composition) but also music interpretation and understanding (analysis).

Racial discrimination in decision-making scenarios such as police arrests appears to be a violation of expected utility theory. Drawing on results from the science of information, we discuss an information-based model of signal detection over a population that generates such behavior as an alternative explanation to taste-based discrimination by the decision maker or differences among the racial populations. This model uses the decision rule that maximizes expected utility-the likelihood ratio test-but constrains the precision of the threshold to a small discrete set. The precision constraint follows from both bounded rationality in human recollection and finite training data for estimating priors. When combined with social aspects of human decision making and precautionary cost settings, the model predicts the own-race bias that has been observed in several econometric studies.

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this paper, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible with missing connections, but we find suitably defined decoding thresholds for communication systems with binary erasure channels under peeling decoding, as well as binary symmetric channels under Gallager A and B decoding. We see that decoding is robust to missing wires, as decoding thresholds degrade smoothly. Moreover, there is a stochastic facilitation effect in Gallager B decoders with missing connections. We also conduct finite-length simulations, compare the decoding sensitivity to channel noise and to missing wiring, and perform preliminary error-tolerant manufacturing yield analysis.

We study the information-theoretic limit of reliable information processing by a server with queue-length dependent quality of service. We define the capacity for such a system as the number of bits reliably processed per unit time, and characterize it in terms of queuing system parameters. We also characterize the distributions of the arrival and service processes that maximize and minimize the capacity of such systems in a discrete-time setting. For arrival processes with at most one arrival per time slot, we observed a minimum around the memoryless distribution. We also studied the case of multiple arrivals per time slot, and observed that burstiness in arrival has adverse effects on the system. The problem is theoretically motivated by an effort to incorporate the notion of reliability in queuing systems, and is applicable in the contexts of crowdsourcing, multimedia communication, and stream computing.

In the information overload regime, human communication tasks such as responding to email are well-modeled as priority queues, where priority is determined by a mix of intrinsic motivation and extrinsic motivation corresponding to the task's importance to the sender. We view priority queuing from a principal-agent perspective, and characterize the effect of priority-misalignment and information asymmetry between task senders and task receivers in both single-agent and multi-agent settings. In the single-agent setting, we find that discipline can override misalignment. Although variation in human interests leads to performance loss in the single-agent setting, the same variability is useful to the principal with optimal routing of tasks, if the principal has suitable information about agents' priorities. Our approach starts to quantitatively address the effect of human dynamics in routine communication tasks.

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.

Consider a distributed estimation problem to be carried out by paid crowdworkers, where results are to be returned quickly and accurately. Estimation accuracy is a function of the number of workers completing the job and of the quality of the workers, both of which may be influenced by the payment offered. With limited budget, payment allocation should consider both effects to obtain best results. Since people are not deterministic, payment offers will lead to a random number of variable-quality workers, as governed by choice models. We consider average performance and focus on estimating a parameter from measurements through uniform noise. Since we have shown the optimality of the midrange estimator in specific settings of the general problem, we focus on the best linear unbiased estimator based on order statistics (BLUE-OS) under the mean-squared error (MSE) criterion. Best payment allocations are determined for single crowd platforms, joint population models and separated platform models. Illustrative numerical examples are provided.

With developments in experimental connectomics producing wiring diagrams of many neuronal networks, there is emerging interest in theories to understand the relationship between structure and function. Efficiency of information flow in networks has been proposed as a key functional in characterizing cognition, and we have previously shown that information-theoretic limits on information flow are predictive of behavioral speed in the nematode Caenorhabditis elegans. In particular, we defined and computed a notion called effective bottleneck capacity that emerged from a pipelining model of information flow. It was unclear, however, whether the particular C. elegans connectome had unique capacity properties or whether similar properties would hold for random networks. Here, we determine the effective bottleneck capacity for several random graph ensembles to understand the range of possible variation and compare to the C. elegans network.

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 different types of agents with different skill-sets. Considering these constraints together necessitates 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 work 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 non-profit company and show significant improvements over current practice.

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible under miswiring, but we find suitably defined decoding thresholds for communication systems with binary erasure channels and peeling decoders, as well as binary symmetric channels and Gallager A decoders. We see that decoding is robust to missing connections, as decoding thresholds degrade smoothly.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver since the battery will drain during intervals with low signal energy. The energy content in the signal may be regularized by partitioning each codeword into smaller subblocks and requiring that sufficient energy is carried in every subblock duration. In this paper, we study subblock energy-constrained codes (SECCs) which, by definition, are codes satisfying the subblock energy constraint. For SECCs, we provide a sufficient condition on the subblock length to avoid power outage at the receiver. We consider discrete memoryless channels and characterize the SECC capacity, and also provide different bounds on the SECC capacity. Further, we characterize and bound the random coding error exponent for SECCs.

In software-as-a-service applications provisioned through cloud computing, locally cached data are often modified with updates from new versions. In some cases, with each edit, one may want to preserve both the original and new versions. In this paper, we focus on cases in which only the latest version must be preserved. Furthermore, it is desirable for the data to not only be compressed but to also be easily modified during updates, since representing information and modifying the representation both incur cost. We examine whether it is possible to have both compression efficiency and ease of alteration, in order to promote codeword reuse. In other words, we study the feasibility of a malleable and efficient coding scheme. The tradeoff between compression efficiency and malleability cost-the difficulty of synchronizing compressed versions-is measured as the length of a reused prefix portion. The region of achievable rates and malleability is found. Drawing from prior work on common information problems, we show that efficient data compression may not be the best engineering design principle when storing software-as-a-service data. In the general case, goals of efficiency and malleability are fundamentally in conflict.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver, since the battery will drain during intervals with low signal energy. In this paper, we analyze subblock energy-constrained codes (SECCs), which ensure that sufficient energy is carried within every subblock duration. We consider discrete memoryless channels and characterize the SECC capacity and the SECC error exponent, and provide useful bounds for these values. We also study constant subblock-composition codes (CSCCs), which are a subclass of SECCs where all the subblocks in every codeword have the same fixed composition, and this subblock composition is chosen to maximize the rate of information transfer while meeting the energy requirement. Compared with constant composition codes (CCCs), we show that CSCCs incur a rate loss and that the error exponent for CSCCs is also related to the error exponent for CCCs by the same rate loss term. We exploit the symmetry in CSCCs to obtain a necessary and sufficient condition on the subblock length for avoiding power outage at the receiver. Furthermore, for CSCC sequences, we present a tight lower bound on the average energy per symbol within a sliding time window. We provide numerical examples highlighting the tradeoff between the delivery of sufficient energy to the receiver and achieving high information transfer rates. It is observed that the ability to use energy in real-time imposes less of penalty compared with the ability to use information in real-time.

Crowdsourcing of jobs to online freelance markets 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 requirements, however, this does not ensure the maximum number of job requests is satisfied. In this work we determine the capacity of freelance markets, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom of choice for customers and freelancers, we propose simple schemes compatible with the operation of current crowd-sourcing platforms that approximately achieve capacity. Further, for settings where job requests exceed capacity, we propose an optimal and fair scheme for declining jobs without wait.

The possibility of latency arbitrage in financial markets has led to the deployment of high-speed communication links between distant financial centers. These links are noisy and so there is a need for coding. In this paper, we develop a game-theoretic model of trading behavior where two traders compete to capture latency arbitrage opportunities using binary signalling. Different coding schemes are strategies that trade off between reliability and latency. When one trader has a better channel, the second trader should not compete. With statistically identical channels, we find there are two different regimes of channel noise for which: there is a unique Nash equilibrium yielding ties; and there are two Nash equilibria with different winners.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy to power its circuitry. When the receiver has limited battery size, a signal with bursty energy content may cause power outage since the battery will drain during intervals with low signal energy. The energy content in the signal may be regularized by requiring that sufficient energy is carried in every subblock duration. In this paper, we study constant subblock-composition codes (CSCCs) where all subblocks in every codeword have the same composition, and this composition is chosen such that the real-time energy requirement at the receiver is met. For a given energy storage capacity at the receiver, we give a necessary and sufficient condition on the subblock length for avoiding outage. We show that CSCC capacity on a discrete memoryless channel can be efficiently computed by exploiting certain symmetry conditions, and compare it with the capacity of constant composition codes. We provide numerical examples highlighting the tradeoff between delivery of sufficient energy to the receiver and achieving high information transfer rates.

We consider the CEO problem for belief sharing. Multiple subordinates observe independently corrupted versions of uniformly distributed data and transmit coded versions over rate-limited links to a CEO who then estimates the underlying data. Agents are not allowed to convene before transmitting their observations. This formulation is motivated by the practical problem of a firm's CEO estimating uniformly distributed beliefs about a sequence of events, before acting on them. Agents' observations are modeled as jointly distributed with the underlying data through a given conditional probability density function. We study the asymptotic behavior of the minimum achievable mean squared error distortion at the CEO in the limit when the number of agents L and the sum rate R tend to infinity. We establish a 1/R2convergence of the distortion, an intermediate regime of performance between the exponential behavior in discrete CEO problems [Berger, Zhang, and Viswanathan (1996)], and the 1/R behavior in Gaussian CEO problems [Viswanathan and Berger (1997)]. Achievability is proved by a layered architecture with scalar quantization, distributed entropy coding, and midrange estimation. The converse is proved using the Bayesian Chazan-Zakai-Ziv bound.

No abstract available.

We consider the CEO problem for non-regular source distributions (such as uniform or truncated Gaussian). A group of agents observe independently corrupted versions of data and transmit coded versions over rate-limited links to a CEO. The CEO then estimates the underlying data based on the received coded observations. Agents are not allowed to convene before transmitting their observations. This formulation is motivated by the practical problem of a firm's CEO estimating (non-regular) beliefs about a sequence of events, before acting on them. Agents' observations are modeled as jointly distributed with the underlying data through a given conditional probability density function. We study the asymptotic behavior of the minimum achievable mean squared error distortion at the CEO in the limit when the number of agents L and the sum rate R tend to infinity. We establish a 1/R2convergence of the distortion, an intermediate regime of performance between the exponential behavior in discrete CEO problems [Berger, Zhang, and Viswanathan (1996)], and the 1/R behavior in Gaussian CEO problems [Viswanathan and Berger (1997)]. Achievability is proved by a layered architecture with scalar quantization, distributed entropy coding, and midrange estimation. The converse is proved using the Bayesian Chazan-Zakai-Ziv bound.

Analytics-as-a-service is emerging as a key offering for cloud systems, however in the petascale regime, data transfer bottlenecks are a limiting factor. Often information has to be transmitted to the cloud by physical transportation. Efficient information representations that leverage the functional purpose of data for the analytics service to be offered can serve to ameliorate many of these information flow bottlenecks. In this paper, we provide an information-theoretic view on optimal information representations for big data analytics in the cloud. We also provide some structural design principles for building a petascale analytics appliance.

In today's regime of information overload, it is reasonable to model a human executing routine tasks such as responding to emails as a priority queue. Humans typically prioritize task execution based on intrinsic motivators such as interest in the task, as well as extrinsic motivation stemming from the importance of the task to the sender. We view the human priority queue from the perspective of a principal-agent problem and characterize the effect of misalignment between the task sender's and task receiver's priorities. Our model provides insights into how different levels of misalignment affect delays of tasks of varying importance. Further, our approach starts to quantitatively address the effect of human dynamics in routine communication tasks, such as responding to emails.

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns that satisfy certain subspace constraints. Although these designs correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable neurons in brain regions thought to operate associatively, such as hippocampus and olfactory cortex. Here we consider associative memories with boundedly noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase can be made exceedingly small. More surprising, we show that internal noise improves the performance of the recall phase while the pattern retrieval capacity remains intact: the number of stored patterns does not reduce with noise (up to a threshold). Computational experiments lend additional support to our theoretical analysis. This work suggests a functional benefit to noisy neurons in biological neuronal networks.

Noise, traditionally defined as an unwanted signal or disturbance, has been shown to play an important constructive role in many information processing systems and algorithms. This noise enhancement has been observed and employed in many physical, biological, and engineered systems. Indeed stochastic facilitation (SF) has been found critical for certain biological information functions such as detection of weak, subthreshold stimuli or suprathreshold signals through both experimental verification and analytical model simulations. In this paper, we present a systematic noise-enhanced information processing framework to analyze and optimize the performance of engineered systems. System performance is evaluated not only in terms of signal-to-noise ratio but also in terms of other more relevant metrics such as probability of error for signal detection or mean square error for parameter estimation. As an important new instance of SF, we also discuss the constructive effect of noise in associative memory recall. Potential enhancement of image processing systems via the addition of noise is discussed with important applications in biomedical image enhancement, image denoising, and classification.

Bayesian hypothesis testing and minimax hypothesis testing represent extreme instances of detection in which the prior probabilities of the hypotheses are either completely and precisely known, or are completely unknown. Group minimax, also known as Gamma -minimax, is a robust intermediary between Bayesian and minimax hypothesis testing that allows for coarse or partial advance knowledge of the hypothesis priors by using information on sets in which the prior lies. Existing work on group minimax, however, does not consider the question of how to define the sets or groups of priors; it is assumed that the groups are given. In this paper, we propose a novel intermediate detection scheme formulated through the quantization of the space of prior probabilities that optimally determines groups and also representative priors within the groups. We show that when viewed from a quantization perspective, group minimax amounts to determining centroids with a minimax Bayes risk error divergence distortion criterion: the appropriate Bregman divergence for this task. In addition, the optimal partitioning of the space of prior probabilities is a Bregman Voronoi diagram. Together, the optimal grouping and representation points are an epsilon -net with respect to Bayes risk error divergence, and permit a rate-distortion type asymptotic analysis of detection performance with the number of groups. Examples of detecting signals corrupted by additive white Gaussian noise and of distinguishing exponentially-distributed signals are presented.

We consider a network quantizer design setting where agents must balance fidelity in representing their local source distributions against their ability to successfully communicate with other connected agents. By casting the problem as a network game, we show existence of Nash equilibrium quantizer designs. For any agent, under Nash equilibrium, the word representing a given partition region is the conditional expectation of the mixture of local and social source probability distributions within the region. Further, the network may converge to equilibrium through a distributed version of the Lloyd-Max algorithm. In contrast to traditional results in the evolution of language, we find several vocabularies may coexist in the Nash equilibrium, with each individual having exactly one of these vocabularies. The overlap between vocabularies is high for individuals that communicate frequently and have similar local sources. Finally, we argue error in translation along a chain of communication does not grow if and only if the chain consists of agents with shared vocabulary.

Built on top of human resources management databases within the enterprise, we present a decision support system for managing and optimizing screening activities during the hiring process in a large organization. The basic idea is to prioritize the efforts of human resource practitioners to focus on candidates that are likely of high quality, that are likely to accept a job offer if made one, and that are likely to remain with the organization for the long term. To do so, the system first individually ranks candidates along several dimensions using a keyword matching algorithm and several bipartite ranking algorithms with univariate loss trained on historical actions. Next, individual rankings are aggregated to derive a single list that is presented to the recruitment team through an interactive portal. The portal supports multiple filters that facilitate effective identification of candidates. We demonstrate the usefulness of our system on data collected from a large organization over several years with business value metrics showing greater hiring yield with less interviews. Similarly, using historical pre-hire data we demonstrate accurate identification of candidates that will have quickly left the organization. The system has been deployed as described in a large globally integrated enterprise.

We consider the use of error-control codes and decoding algorithms to perform reliable classification using unreliable and anonymous human crowd workers by adapting coding-theoretic techniques for the specific crowdsourcing application. We develop an ordering principle for the quality of crowds and describe how system perfor-mance changes with the quality of the crowd. We demonstrate the effectiveness of the proposed coding scheme using both simulated data and real datasets from Amazon Mechanical Turk, a crowd-sourcing microtask platform. Results suggest that good codes may improve the performance of the crowdsourcing task over typical majority-vote approaches. Index Terms — crowdsourcing, classification, error-control codes

The capacity region of the additive exponential noise two-way channel is established. Adaptation is not necessary for optimal communication, and the rate region is simply a function of the one-way capacity. The result is extended to two-way channels of exponential family type, using a saddle point theorem.

In information overload regimes, it is necessary for messages to not only provide information but also to attract attention in the first place. Bayesian surprise is an information-theoretic functional that has been experimentally shown to measure the attraction of human attention. This paper studies the limits of reliable communication under a constraint on surprise so as to limit distraction: surprise-constrained capacity. It also considers attention-seeking capacity, where the goal is to maximize both information rate and surprise to attract attention. Properties of these functions are proven. There are no nontrivial tradeoffs for surprise-constrained capacity, but an interesting tradeoff arises for attention-seeking capacity; reversing the direction of constraint does not yield essentially equivalent problems.

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns. Although these designs correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable neurons in hippocampus and olfactory cortex. Here we consider associative memories with noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase can be made exceedingly small. More surprisingly, we show that internal noise actually improves the performance of the recall phase. Computational experiments lend additional support to our theoretical analysis. This work suggests a functional benefit to noisy neurons in biological neuronal networks.

The wiring economy principle in neuroscience has explained many experimentally observed properties of neuronal networks by asserting the need to keep the axons and dendrites that connect neurons small in length. Just like neuronal networks, many distributed systems are physical constructs that incur deployment and maintenance costs for their communication infrastructure. Taking wiring economy as a design goal for engineering systems that perform distributed coordination and inference, this paper formulates and studies the tradeoff between performance and wiring cost. It is shown that separated communication topology design and physical node placement yields optimal design. Designing optimal networks is shown to be NP-complete. The natural relaxation to the integer network design problem is shown to be a reverse convex program. Small optimal networks are computed. Optimally placed random network topologies are demonstrated to have good performance.

The importance of architectural principles in the design of engineering systems is well-recognized. This paper argues that the traditional separation between energy delivery and information delivery leads to suboptimal systems. To demonstrate this for wireline systems that may use DC powerline communication, a capacity-power-wiring cost function is defined. Signaling strategies that optimize this function deliver patterned energy: a commodity measured in bits and joules such that energy and information are intermixed. Cross-layer design leads to improved performance.

Given the possibility of communication systems failing catastrophically, we investigate limits to communicating over channels that fail at random times. These channels are finite-state semi-Markov channels. We show that communication with arbitrarily small probability of error is not possible. Making use of results in finite blocklength channel coding, we determine sequences of blocklengths that optimize transmission volume communicated at fixed maximum message error probabilities. We provide a partial ordering of communication channels. A dynamic programming formulation is used to show the structural result that channel state feedback does not improve performance.

The effect of quantization of prior probabilities in a collection of distributed Bayesian binary hypothesis testing problems over which the priors themselves vary is studied. In a setting with fusion of local binary decisions by majority rule, optimal local decision rules are discussed. Quantization is first considered under the constraint that agents employ identical quantizers. A method for design is presented that exploits an equivalence to a single-agent problem with a different likelihood function, the optimal quantizers are thus different than in the single-agent case. Removing the constraint of identical quantizers is demonstrated to improve performance. A method for design is presented that exploits an equivalence between agents having diverse K-level quantizers and agents having identical (3K-2)-level quantizers.

The effect of quantization of prior probabilities in a collection of distributed Bayesian binary hypothesis testing problems over which the priors themselves vary is studied, with focus on conflicting agents. Conflict arises from differences in Bayes costs, even when all agents desire correct decisions and agree on the meaning of correct. In a setting with fusion of local binary decisions by majority rule, Nash equilibrium local decision strategies are found. Assuming that agents follow Nash equilibrium decision strategies, designing quantizers for prior probabilities becomes a strategic form game, we discuss its Nash equilibria. We also propose two different constrained quantizer design games, find Nash equilibrium quantizer designs, and compare performance. The system has deadweight loss: equilibrium decisions are not Pareto optimal.

In cloud computing, storage area networks, and remote backup storage, stored data is modified with updates from new versions. It is desirable for the data to not only be compressed but to also be easily modified during updates, since representing information and modifying the representation are both expensive. A malleable coding scheme considers both compression efficiency and ease of alteration, promoting codeword reuse. We examine the trade-off between compression efficiency and malleability cost-the difficulty of synchronizing compressed versions-measured as the length of a reused prefix portion. Through a coding theorem, the region of achievable rates and malleability is expressed as a single-letter optimization. Relationships to common information problems are also described.

Many functional descriptions of spiking neurons assume a cascade structure where inputs are passed through an initial linear filtering stage that produces a low-dimensional signal that drives subsequent nonlinear stages. This paper presents a novel and systematic parameter estimation procedure for such models and applies the method to two neural estimation problems: (i) compressed-sensing based neural mapping from multi-neuron excitation, and (ii) estimation of neural receptive yields in sensory neurons. The proposed estimation algorithm models the neurons via a graphical model and then estimates the parameters in the model using a recently-developed generalized approximate message passing (GAMP) method. The GAMP method is based on Gaussian approximations of loopy belief propagation. In the neural connectivity problem, the GAMP-based method is shown to be computational efficient, provides a more exact modeling of the sparsity, can incorporate nonlinearities in the output and significantly outperforms previous compressed-sensing methods. For the receptive field estimation, the GAMP method can also exploit inherent structured sparsity in the linear weights. The method is validated on estimation of linear nonlinear Poisson (LNP) cascade models for receptive fields of salamander retinal ganglion cells.

Despite recent interest in reconstructing neuronal networks, complete wiring diagrams on the level of individual synapses remain scarce and the insights into function they can provide remain unclear. Even for Caenorhabditis elegans, whose neuronal network is relatively small and stereotypical from animal to animal, published wiring diagrams are neither accurate nor complete and self-consistent. Using materials from White et al. and new electron micrographs we assemble whole, self-consistent gap junction and chemical synapse networks of hermaphrodite C. elegans. We propose a method to visualize the wiring diagram, which reflects network signal flow. We calculate statistical and topological properties of the network, such as degree distributions, synaptic multiplicities, and small-world properties, that help in understanding network signal propagation. We identify neurons that may play central roles in information processing, and network motifs that could serve as functional modules of the network. We explore propagation of neuronal activity in response to sensory or artificial stimulation using linear systems theory and find several activity patterns that could serve as substrates of previously described behaviors. Finally, we analyze the interaction between the gap junction and the chemical synapse networks. Since several statistical properties of the C. elegans network, such as multiplicity and motif distributions are similar to those found in mammalian neocortex, they likely point to general principles of neuronal networks. The wiring diagram reported here can help in understanding the mechanistic basis of behavior by generating predictions about future experiments involving genetic perturbations, laser ablations, or monitoring propagation of neuronal activity in response to stimulation.

Communication of quantized information is frequently followed by a computation. We consider situations of distributed functional scalar quantization: distributed scalar quantization of (possibly correlated) sources followed by centralized computation of a function. Under smoothness conditions on the sources and function, companding scalar quantizer designs are developed to minimize mean-squared error (MSE) of the computed function as the quantizer resolution is allowed to grow. Striking improvements over quantizers designed without consideration of the function are possible and are larger in the entropy-constrained setting than in the fixed-rate setting. As extensions to the basic analysis, we characterize a large class of functions for which regular quantization suffices, consider certain functions for which asymptotic optimality is achieved without arbitrarily fine quantization, and allow limited collaboration between source encoders. In the entropy-constrained setting, a single bit per sample communicated between encoders can have an arbitrarily large effect on functional distortion. In contrast, such communication has very little effect in the fixed-rate setting.

Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided.

Permutation codes are a class of structured vector quantizers with a computationally-simple encoding procedure based on sorting the scalar components. Using a codebook comprising several permutation codes as subcodes preserves the simplicity of encoding while increasing the number of rate-distortion operating points, improving the convex hull of operating points, and increasing design complexity. We show that when the subcodes are designed with the same composition, optimization of the codebook reduces to a lower-dimensional vector quantizer design within a single cone. Heuristics for reducing design complexity are presented, including an optimization of the rate allocation in a shape-gain vector quantizer with gain-dependent wrapped spherical shape codebook.

Permutation codes are a class of structured vector quantizers with a computationally-simple encoding procedure. In this paper, we provide an extension that preserves the computational simplicity but yields improved operational rate-distortion performance. The new class of vector quantizers has a codebook comprising several permutation codes as subcodes. Methods for designing good code parameters are given. One method depends on optimizing the rate allocation in a shape-gain vector quantizer with gain-dependent wrapped spherical shape codebook.

A malleable coding scheme considers not only representation length but also ease of representation update, thereby encouraging some form of recycling to convert an old codeword into a new one. We examine the trade-off between compression efficiency and malleability cost, measured with a string edit distance that introduces a metric topology to the representation domain. We characterize the achievable rates and malleability as the solution of a subgraph isomorphism problem.

Suppose a function of N real source variables X1N= (X1, X2, ..., XN) is desired at a destination constrained to receive a limited number of bits. If the result of evaluating the function, Y = G(X1N), can be itself encoded, this is the optimal strategy-the origin of Y becomes irrelevant to the communication problem. We consider two alternative scenarios: distributed quantization, in which each Ximust be separately encoded; and linear transform coding of X1N. Optimal fixed- and variable-rate scalar quantizers are derived under the conventional assumptions of high-resolution quantization theory, and we find optimal transforms for transform coding. For certain classes of functions, examples demonstrate large improvements over using quantizers designed to minimize distortion of the Xis.

Bayesian hypothesis testing is investigated when the prior probabilities of the hypotheses, taken as a random vector, must be quantized. Nearest neighbor and centroid conditions for quantizer optimality are derived using mean Bayes risk error as a distortion measure. An example of optimal quantization for hypothesis testing is provided. Human decision making is briefly studied assuming quantized prior Bayesian hypothesis testing; this model explains several experimental findings.

The fundamental tradeoff between the rates at which energy and reliable information can be transmitted over a single noisy line is studied. Engineering inspiration for this problem is provided by powerline communication, RFID systems, and covert packet timing systems as well as communication systems that scavenge received energy. A capacity-energy function is defined and a coding theorem is given. The capacity-energy function is a non-increasing concave cap function. Capacity-energy functions for several channels are computed.

Figure 1 of Shannonpsilas 1948 paper, a schematic diagram of a general communication system, captures the entire essence of communication. Such a block diagram defines a closed universe for deducing fundamental limits, influences the cognitive processes of information theorists, and shapes the design of technology. The power and fundamental nature of the diagram and the theory within it are the prime reasons I have been drawn to information theory. Taking a personal and anthropological approach rather than a strictly historical one, I argue that block diagrams are metonyms for theorems in information theory and moreover that these powerful abstractions are applicable beyond the classical communication problem. I will briefly describe a few of my projects that use diagrammatic thinking for studies in neuroscience, energy transmission, and decoding.

The problem of communicating (unordered) sets, rather than (ordered) sequences is formulated. Elementary results in all major branches of source coding theory, including lossless coding, high-rate and low-rate quantization, and rate distortion theory are presented. In certain scenarios, rate savings of log n! bits for sets of size n are obtained. Asymptotically in the set size, the entropy rate is zero and for sources with an ordered parent alphabet, the (0,0) point is the rate distortion function.