
This work investigates the fundamental limits of communication over a noisy
discrete memoryless channel that wears out, in the sense of signaldependent
catastrophic failure. In particular, we consider a channel that starts as a
memoryless binaryinput 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
leftconcave rightconvex inequality is then refined to obtain a converse bound
on the logvolume 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.

We propose a novel system which can transform a recipe into any selected
regional style (e.g., Japanese, Mediterranean, or Italian). This system has two
characteristics. First the system can identify the degree of regional cuisine
style mixture of any selected recipe and visualize such regional cuisine style
mixtures using barycentric Newton diagrams. Second, the system can suggest
ingredient substitutions through an extended word2vec model, such that a recipe
becomes more authentic for any selected regional cuisine style. Drawing on a
large number of recipes from Yummly, an example shows how the proposed system
can transform a traditional Japanese recipe, Sukiyaki, into French style.

Deep neural networks have shown incredible performance for inference tasks in
a variety of domains. Unfortunately, most current deep networks are enormous
cloudbased structures that require significant storage space, which limits
scaling of deep learning as a service (DLaaS) and use for ondevice augmented
intelligence. This paper is concerned with finding universal lossless
compressed representations of deep feedforward networks with synaptic weights
drawn from discrete sets, and directly performing inference without full
decompression. The basic insight that allows 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. We also provide experimental results of
our approach on the MNIST dataset.

Abstraction and realization are bilateral processes that are key in deriving
intelligence and creativity. In many domains, the two processes are approached
through rules: highlevel 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
biconvex 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).

Constrained coding is used widely in digital communication and storage
systems. In this paper, we study a generalized sliding window constraint called
the skipsliding window. A skipsliding 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 nonnegative integers $i$ such that $i \leq 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 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 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.

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 in the form of 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 the
ideas of secret key sharing, private key encryption, and distributed storage to
design a coding scheme such that each node stores only a part of the entire
transaction thereby reducing the storage cost to a fraction of its original
cost. When further using dynamic zone allocation, we show the coding scheme can
also improve the integrity of the transaction data in the network over current
schemes. Further, block validation (bitcoin mining) consumes a significant
amount of energy as it is necessary to determine a hash value satisfying a
specific set of constraints; we show that using dynamic distributed storage
reduces these energy costs.

Conventional lowpower static random access memories (SRAMs) reduce read
energy by decreasing the bitline voltage swings uniformly across the bitline
columns. This is because the read energy is proportional to the bitline
swings. On the other hand, bitline swings are limited by the need to avoid
decision errors especially in the most significant bits. We propose an
informationtheoretic approach to determine optimal nonuniform bitline swings
by formulating convex optimization problems. For a given constraint on mean
squared error of retrieved words, we consider criteria to minimize energy (for
lowpower SRAMs), maximize speed (for highspeed SRAMs), and minimize
energydelay product. These optimization problems can be interpreted as
classical waterfilling, groundflattening and waterfilling, and sandpouring
and waterfilling, respectively. By leveraging these interpretations, we also
propose greedy algorithms to obtain optimized discrete swings. Numerical
results show that energyoptimal swing assignment reduces energy consumption by
half at a peak signaltonoise ratio of 30dB for an 8bit accessed word. The
energy savings increase to four times for a 16bit accessed word.

Empirical studies of scientific discoverysocalled Eurekometricshave
indicated that the output of exploration proceeds as a logistic growth curve.
Although logistic functions are prevalent in explaining population growth that
is resourcelimited to a given carrying capacity, their derivation do not apply
to discovery processes. This paper develops a generative model for logistic
\emph{knowledge discovery} using a novel extension of coupon collection, where
an explorer interested in discovering all unknown elements of a set is
supported by technology that can respond to queries. This discovery process is
parameterized by the novelty and quality of the set of discovered elements at
every time step, and randomness is demonstrated to improve performance.
Simulation results provide further intuition on the discovery process.

We investigate fusing several unreliable computational units that perform the
same task. We model an unreliable computational outcome as an additive
perturbation to its errorfree result in terms of its fidelity and cost. We
analyze performance of repetitionbased strategies that distribute cost across
several unreliable units and fuse their outcomes. When the cost is a convex
function of fidelity, the optimal repetitionbased strategy in terms of
incurred cost while achieving a target meansquare error (MSE) performance may
fuse several computational units. For concave and linear costs, a single more
reliable unit incurs lower cost compared to fusion of several lower cost and
less reliable units while achieving the same MSE performance. We show how our
results give insight into problems from theoretical neuroscience, circuits, and
crowdsourcing.

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 multiimage registration, and design an asymptotically optimal
algorithm based on multiinformation. Finally, we define a novel multivariate
information functional to perform joint clustering and registration of images,
and prove consistency of the algorithm.

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 intrachip communications, equivalent
to transiently missing connections. In this work, we investigate the
performance of messagepassing 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
compare the decoding sensitivity with respect to channel noise and missing
wiring.

In the nanoscale regime, the behavior of both extant and emerging
semiconductor devices are often unreliable. Reliability of such devices often
tradesoff with their energy consumption, speed, and/or chip area. We study the
energyreliability limits for circuits designed using such devices. Using the
mutual information propagation in logic circuits technique developed by
Pippenger, together with optimization, we obtain lower bounds on the energy
consumption for computing ninput boolean functions. Most extant technologies
require all gates to have the same electrical operating point and in circuits
of such uniform gates, the minimum energy required to achieve any nontrivial
reliability scales superlinearly with the number of inputs. On the other hand,
in some emerging technologies such as spin electronics, where the gates in a
circuit can have different operating points, energy scaling can be linear in
the number of inputs. As part of our development we find a simple procedure for
energy allocation across gates in a boolean circuit with different operating
points.

Throughout music history, theorists have identified and documented
interpretable rules that capture the decisions of composers. This paper asks,
"Can a machine behave like a music theorist?" It presents MUSROVER, a
selflearning system for automatically discovering rules from symbolic music.
MUSROVER performs feature learning via $n$gram models to extract
compositional rules  statistical patterns over the resulting features. We
evaluate MUSROVER on Bach's (SATB) chorales, demonstrating that it can recover
known rules, as well as identify new, characteristic patterns for further
study. We discuss how the extracted rules can be used in both machine and human
composition.

Consider designing an effective crowdsourcing system for an $M$ary
classification task. Crowd workers complete simple binary microtasks whose
results are aggregated to give the final result. We consider the novel scenario
where workers have a reject option so they may skip microtasks when they are
unable or choose not to respond. For example, in mismatched speech
transcription, workers who do not know the language may not be able to respond
to microtasks focused on phonological dimensions outside their categorical
perception. We present an aggregation approach using a weighted majority voting
rule, where each worker's response is assigned an optimized weight to maximize
the crowd's classification performance. We evaluate system performance in both
exact and asymptotic forms. Further, we consider the setting where there may be
a set of greedy workers that complete microtasks even when they are unable to
perform it reliably. We consider an oblivious and an expurgation strategy to
deal with greedy workers, developing an algorithm to adaptively switch between
the two based on the estimated fraction of greedy workers in the anonymous
crowd. Simulation results show improved performance compared with conventional
majority voting.

In the information overload regime, human communication tasks such as
responding to email are wellmodeled 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 principalagent perspective, and characterize the effect of
prioritymisalignment and information asymmetry between task senders and task
receivers in both singleagent and multiagent settings. In the singleagent
setting, we find that discipline can override misalignment. Although variation
in human interests leads to performance loss in the singleagent 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.

We study the informationtheoretic limit of reliable information processing
by a server with queuelength 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 discretetime 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 queueing systems, and is
applicable in the contexts of crowdsourcing, multimedia communication, and
stream computing.

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 skillsets and
availabilities of different types of agents with different skillsets.
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 nonprofit company and show significant
improvements over current practice.

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 quality requirements, however, this does not ensure
that 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 crowdsourcing platforms
that approximately achieve capacity. Further, 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.

Olfaction, the sense of smell, has received scant attention from a signal
processing perspective in comparison to audition and vision. In this paper, we
develop a signal processing paradigm for olfactory signals based on new
scientific discoveries including the psychophysics concept of olfactory white.
We describe a framework for predicting the perception of odorant compounds from
their physicochemical features and use the prediction as a foundation for
several downstream processing tasks. We detail formulations for odor
cancellation and food steganography, and provide realworld empirical examples
for the two tasks. We also discuss adaptive filtering and other olfactory
signal processing tasks at a high level.

Consider an energyharvesting 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 consider a discrete memoryless channel and characterize
achievable information rates when the energy content in each codeword is
regularized by ensuring that sufficient energy is carried within every subblock
duration. In particular, we study constant subblockcomposition codes (CSCCs)
where all subblocks in every codeword have the same fixed composition, and this
subblockcomposition is chosen to maximize the rate of information transfer
while meeting the energy requirement. Compared to 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 show that CSCC capacity can be improved by allowing different
subblocks to have different composition while still meeting the subblock energy
constraint. We provide numerical examples highlighting the tradeoff between
delivery of sufficient energy to the receiver and achieving high information
transfer rates. It is observed that the ability to use energy in realtime
imposes less of penalty than the ability to use information in realtime.

The possibility of latency arbitrage in financial markets has led to the
deployment of highspeed communication links between distant financial centers.
These links are noisy and so there is a need for coding. In this paper, we
develop a gametheoretic 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.

We consider the CEO problem for nonregular source distributions (such as
uniform or truncated Gaussian). A group of agents observe independently
corrupted versions of data and transmit coded versions over ratelimited 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 (nonregular) 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/R^2$ convergence 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 ChazanZakaiZiv bound.

Formal coordination mechanisms are of growing importance as humanbased
service delivery becomes more globalized and informal mechanisms are no longer
effective. Further it is becoming apparent that business environments,
communication among distributed teams, and work performance are all subject to
endogenous and exogenous uncertainty.
This paper describes a stochastic model of service requests in global service
delivery and then puts forth a cognitive approach for coordination in the face
of uncertainty, based on a perceptionaction loop and receding horizon control.
Optimization algorithms used are a mix of myopic dynamic programming and
constraintbased programming. The coordination approach described has been
deployed by a globally integrated enterprise in a very largescale global
delivery system and has been demonstrated to improve work efficiency by 1015%
as compared to manual planning.

Recent advances in associative memory design through structured pattern sets
and graphbased 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 brain regions thought to operate associatively
such as 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 while the pattern retrieval
capacity remains intact, i.e., 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.

Crowdsourcing systems often have crowd workers that perform unreliable work
on the task they are assigned. In this paper, we propose the use of
errorcontrol codes and decoding algorithms to design crowdsourcing systems for
reliable classification despite unreliable crowd workers. Codingtheory based
techniques also allow us to pose easytoanswer binary questions to the crowd
workers. We consider three different crowdsourcing models: systems with
independent crowd workers, systems with peerdependent reward schemes, and
systems where workers have common sources of information. For each of these
models, we analyze classification performance with the proposed codingbased
scheme. We develop an ordering principle for the quality of crowds and describe
how system performance changes with the quality of the crowd. We also show that
pairing among workers and diversification of the questions help in improving
system performance. We demonstrate the effectiveness of the proposed
codingbased scheme using both simulated data and real datasets from Amazon
Mechanical Turk, a crowdsourcing microtask platform. Results suggest that use
of good codes may improve the performance of the crowdsourcing task over
typical majorityvoting approaches.