**
Communication, Control**
**
and Signal Processing Seminar****
**

**Abstracts
of talks**

*Spring 2013*

** 02/07 Marcelo Firer (U. Campinas, Brazil)****,
Coding in the Presence of Semantic Value of Information **

ABSTRACT:
This talk will explore possibilities for coding when errors have different
(semantic) values. The main idea is to exchange the usual question of
"minimizing the quantity of errors" by "minimizing the importance of errors".
We introduce the basic mathematical formulation of the problem, presents
some existential results that justifies this approach and then explore initial
strategies for the encoding-decoding process.

** 02/21 Itzhak Tamo (UMD)****,
What I heard at the ITA **

ABSTRACT:
A short informal discussion of a few talks I heard in CA
last week.

http://ita.ucsd.edu/index.php

** 03/20 Vijay Subramanian (Northwestern University)****,
Network Games: Spotting Trendsetters and Bargaining With Middlemen **

ABSTRACT:
Network games provide a basic framework for studying the
diffusion of new ideas or behaviors through a population. In these models,
agents decide to adopt a new idea based on optimizing pay-off that depends
on the adoption decisions of their neighbors in an underlying network. After
introducing the model, we present results for two problems.

The first considers the problem of inferring early adopters or first
movers given a snap shot of the adoption state at a given time. We present
some results on solving this problem in what is known as the low temperature
regime. We conclude the first part with a discussion on reducing the
complexity of such inference problems for large networks.

The second considers a dynamic and decentralized market modeled by a
non-cooperative networked bargaining game. Our goal is to study how the
network structure of the market and the role of middlemen influence the
market's eciency and fairness. We introduce the concept of limit stationary
equilibrium in a general trading network and use it to analyze how
endogenous delay emerges in trade and how surplus is shared between sellers
and buyers.

** 03/26 Sidharth Jaggi (CUHK)****,
Robust sparse recovery and applications: order-optimal measurements and complexity **

ABSTRACT:
Sparse recovery problems are usually in the setting in which a vector x with ambient dimension n
has only k "significant" entries. This vector x is "compressively measured" (with possibly "noisy"
measurements) as y, where y has just m << n components, and the goal is to reconstruct (a good
approximation to) x.

We consider three sparse recovery problems:

* Compressive Sensing: A linear problem in which y is a (possibly noisy) linear transform of x,
a vector in R^n.

* Group Testing: A non-linear problem in which y is a binary vector comprising of (possibly noisy)
disjunctive measurements of a binary x vector.

* Network tomography: A linear problem in which x, a vector in R^n, denotes network parameters
(such as edge/node delays) to be estimated via constrained, end-to-end measurements
(such as path delays).

In each of these cases we present sparse recovery algorithms that have good reconstruction
performance, and have information-theoretically order-optimal decoding complexity and number of
measurements (O(k) measurements and decoding complexity for compressive sensing and network
tomography, and O(k log(n)) measurements and decoding complexity for group testing.)

** 03/28, 04/04 Sikai Qu (UMD)****,
Introduction to Hamersley-Clifford Theorem **

ABSTRACT:
Markov random field (or Markov network) is a set of random variables having Markov property
described by an undirected graph. i.e. Dependency induces neighborhood structures of the graph.
According to Hamersley-Clifford Theorem, Markov random field can be represented by Gibb measure,
which allows us to factorize the probability distribution of the Markov random field according to the
cliques of the graph. In the seminar, I will give definition of Markov random field and Gibb distribution
and then prove the Hamersley-Clifford Theorem. The application of this theorem is that the realization
of some of the network model therefore can be characterized by the number triangles and stars.

** 04/11 Praneeth Boda (UMD)****,
A Decomposition theorem for Binary Markov Random Fields **

ABSTRACT:
In this talk, Hajek-Berger [1987] paper on decomposition
theorem for Binary Markov Random Fields will be discussed.

A Markov random field is a set of random variables having Markov property described
by an undirected graph. The random field considered here is a stationary binary Markov
random field whose neighborhood structure is specified by a countable graph with nodes of
uniformly bounded degree. Under a minimal assumption, Hajek-Berger [1987] have
shown that such a Markov random field can be represented as the node-wise modulo 2 sum
of two independent binary random fields, one of which is white binary noise of positive
weight. This decomposition can be used to compute an exact expression for the per-site
rate-distortion function of the random field over an interval of distortions not exceeding
this weight.

** 04/18 Isaak Mayergoyz (UMD)****,
Riemann Hypothesis and Plasmon Resonances **

ABSTRACT:
Some very basic facts concerning the Riemann hypothesis for the zeta function will be first
outlined. Then, the possible connection between the Riemann hypothesis and the spectral
analysis of plasmon resonances in nano-wires will be explored. Finally, the approach to
the Riemann hypothesis based on the J.Grommer theorem will be presented.

** 04/23 Venu Veeravalli (UIUC)****,
Data-Efficient Quickest Change Detection **

ABSTRACT:
The problem of detecting abrupt changes or anomalies in
stochastic systems and time series, often referred to as the
quickest change detection (QCD) problem, arises in various
branches of science and engineering. Applications
include infrastructure monitoring, quality control engineering,
intrusion detection in computer networks and security systems,
detection of the onset of an epidemic, biomedical signal and
image processing, and financial markets. The classical QCD
problem is formulated as one where there is a sequence
of observations whose distribution changes at an unknown
time, and the goal is to detect the change as quickly as
possible, subject to a false alarm constraint. In the first half
of this talk, we provide a brief overview of the classical
QCD problem and its solutions. In many engineering applications
of QCD, there may be a cost (e.g., energy) associated
with acquiring the observations. In the second half of
the talk, we consider the QCD problem with an additional
constraint on the cost of the observations used in the
detection process, and we develop QCD algorithms
that are data-efficient or energy-efficient. We demonstrate
the working of one of these algorithms on a mote with a light sensor.

** 05/02 Daniel Cullina(UIUC)****,
Upper Bounds on the Size of Deletion Correcting Codes **

ABSTRACT:
We consider the combinatorial (as opposed to probabilistic) variant of the
deletion/insertion channel. It is well known that a code capable of correcting
s deletions can also correct any combination of s total deletions and insertions.
Somewhat surprisingly, channels performing different mixtures of deletions
and insertions lead to different upper bounds on code size. This observation
allows an improvement upon Levenshtein’s asymptotic upper bound on
the size of an s-deletion correcting code. Levenshtein’s bound comes from
the channel performing only deletions, but whenever the number of errors
is larger than the alphabet size it is better to consider a mixture of insertions
and deletions.

This talk will cover some basics of deletion/insertion channels, the technique,
which can be applied to any combinatorial channel,that leads to both the new
and old upper bounds, and some the intermediate results required for
the new upper bound.

** 05/08 Rajesh Sundaresan (IISC)****,
Recursive Distributional Equations, Endogeny, and Belief Propagation via Three Examples **

ABSTRACT:
In this talk, I will introduce the notion of a recursive distributional
equation (RDE) via three combinatorial optimization problems -- matching,
edge-cover, and traveling salesman -- in the random mean field setting. I
will then highlight a property called endogeny, introduced by Aldous and
Bandyopadhyay, for capturing the notion of correlation decay. On the three
examples, I will then indicate how the RDE and endogeny could be useful in
coming up with and establishing validity of belief propagation equations.
The approach works for the matching and edge-cover problems, but endogeny
and validity of belief propagation remain open for the traveling salesman
problem. The talk will be based on joint work with Mustafa Khandwawala on
the edge-cover problem.

** 05/23 Ufuk Topcu (UPENN)****,
Networked, Information-Based Systems: Synthesis of
Correct-By-Construction Control Protocols **

ABSTRACT:
How can we affordably build trustworthy networked,
information-based systems? The talk begins with an interpretation of
this question in the context of autonomous systems and more-electric
air vehicles. Partly motivated by the difficulty and cost of
establishing trust in these applications, I describe a shift from the
traditional "design+verify" approach to "specify+synthesize." I then
discuss our recent advances in automated, correct-by-construction
synthesis of embedded control protocols. I present two results on
receding horizon temporal logic planning and distributed synthesis.
These results combine ideas from control theory with those from
computer science, and exploit underlying system-theoretic
interpretations to alleviate the resulting computational complexity. I
conclude with an outlook on future research opportunities in autonomy,
advanced vehicular systems, and energy networks.