You are here
 Home >
 Previous Workshop >
 Program of IMaCCS 2017 >
 Abstract of IMaCCS 2017
Abstract of IMaCCS 2017
Venkat Anantharam University of California at Berkeley 
Universal lossless compression of graphindexed data
Many data sources arising from social networks, communication networks, and networks describing biological processes are best viewed as indexed by the underlying graphs. These graphs are often sparse, i.e. the number of edges is on the same scale as the number of vertices. The local weak limit theory for sparse graphs provides a framework in which to make sense of what one might mean by a stationary process indexed by graphs when the graph is sparse. Just as the theory of stochastic processes indexed by time has been the engine driving the development of control theory, communications, information theory and signal processing, one might expect that a theory of stationary stochastic processes indexed by graphs, would eventually have a similarly wide ranging impact.
(joint work with Payam Delgosha) 
Tamer Basar University of Illinois at UrbanaChampaign 
Strategic Information Transmission
Strategic information transmission refers to a variation (and a substantial one) of the standard paradigm of information transmission in communication (design of an encoder and a decoder in unison to minimize some distortion measure), where now the encoder and the decoder have (intentionally) misaligned objectives. This leads to a noncooperative game with a dynamic (nonclassical) information structure, where one can adopt as a solution concept either the Nash or the Stackelberg equilibrium. This talk will introduce this class of problems, which have been of interest to multiple communities, including economics, information theory, communication, signal processing, and control, since the early 1980s, having picked up considerable steam very recently. As an overview of the topic, both old and new results will be presented, with one of the highlights (and perhaps a surprising element) being that there appears to be a major difference between the structures of the encoders and the decoders under Nash and Stackelberg equilibria, even when the channel is Gaussian and the (misaligned) distortion measures are quadratic. Extensions to multistage scenarios, information transmission problems with an element of deception, and SIT problems with privacy constraints will also be discussed. 
Charles Bouman Purdue University 
Consensus Equilibrium: Regularized Inversion without Optimization
Regularized inversion is widely used in image reconstruction due to its tractability and its ability to combine complex physical sensor models with useful regularity criteria. However, the need to formulate regularized inversion as the solution to an optimization problem severely limits the expressiveness of regularity conditions and constrains the methods that can be used to compute the solution. In fact, methods such as PlugandPlay Priors that abandon the optimization framework have recently been shown to achieve much better quality results than traditional optimization methods in important problems. 
Suhas Diggavi University of California at Los Angeles 
An information theoretic to nanopore sequencing
While DNA sequencing technology has undergone a major revolution, the read lengths afforded by most current generation sequencing technologies still remain small (in the range of hundreds of DNA basepairs). These short reads are then stitched together with algorithms that exploit the overlap between these reads in order to reconstruct the DNA. Long repeated regions of the DNA greater than this short read length, which are common, are not resolvable with this technology, requiring sequencers capable of accurate long reads. Nanopore sequencing promises to address this problem, by increasing the read lengths by orders of magnitude (up to 10K100K bases). However, nanopore sequencers built to date, have high error rate, which if unresolved could limit their applications. There are many algorithmic challenges in realizing this potential, due to many 
P. R. Kumar Texas A&M University 
The prices of packets and watts: Optimal control of decentralized systems
We examine two problems of contemporary interest, both involving the optimal operation of distributed stochastic dynamic systems, one in power systems and another in communication networks. 
Muriel Medard Massachusetts Institute of Technology 
We overview some recent results in distributed functional compression, where we compress for functions rather than for recovering the original data. These results present a natural extension of network source coding when the primary purpose is to recover functions of data. We investigate some implications for caching and security, and overview open problems in the area. 
Eytan Modiano Massachusetts Institute of Technology 
A New Look at Optimal Control of Wireless Networks

Alon Orlitsky University of California at San Diego 
Everywhere Optimal Probability Estimation

Pablo Parrilo Massachusetts Institute of Technology 
Graph Structure in Polynomial Systems: Chordal Networks
The sparsity structure of a system of polynomial equations or an optimization problem can be naturally described by a graph summarizing the interactions among the decision variables. It is natural to wonder whether the structure of this graph might help in computational algebraic geometry tasks (e.g., in solving the system). In this talk we will provide an introduction to this area, focused on the key notions of chordality and treewidth, which are of great importance in areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. In particular, we will discuss “chordal networks”, a novel representation of structured polynomial systems that provides a computationally convenient decomposition of a polynomial ideal into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. As we will illustrate through examples from different application domains, algorithms based on chordal networks can significantly outperform existing techniques. Based on joint work with Diego Cifuentes (MIT). 
Yannis Paschalidis Boston University 
Inverse Equilibrium Problems and PriceofAnarchy Estimation in Transportation Networks
Equilibrium modeling is common in a variety of fields such as game theory, transportation science, and systems biology. The inputs for these models, however, are often difficult to estimate, while their outputs, i.e., the equilibria they are meant to describe, are often directly observable. By combining ideas from inverse optimization with the theory of variational inequalities, we develop an efficient, datadriven technique for estimating the parameters of these models from observed equilibria. A distinguishing feature of our approach is that it supports both parametric and nonparametric estimation by leveraging ideas from statistical learning. 
Tomaso Poggio Massachusetts Institute of Technology 
When Can Deep Networks Avoid the Curse of Dimensionality
A mathematical theory of deep networks and of why they work as well as they do is now emerging. I will review some recent theoretical results on the approximation power of deep networks including conditions under which they can be exponentially better than shallow learning. A class of deep convolutional networks represent an important special case of these conditions, though weight sharing is not the main reason fortheir exponential advantage. Implications of a few key theorems are discussed, together with new results, and conjectures on generalization properties of deep networks trained with Stochastic Gradient Descent. 
Kameshwar Poolla University of California at Berkeley 
The Sharing Economy for the Smart Grid
The sharing economy. It is all the rage. Going on vacation? Rent out your home for extra income! Have space in your car? Pick up passengers for extra income! Companies such as AirBnB, VRBO, Lyft, and Uber have disrupted housing and transportation sectors. Their innovative business models are based on resource sharing that leverage underutilized infrastructure. Are there compelling sharing economy opportunities in the electricity sector? What products can be shared in tomorrow's Smart Grid? 
R. Srikant University of Illinois at UrbanaChampaign 
We consider an abstraction of the network deanonymization problem, where the goal is to infer the node identities in an anonymized graph by observing the node identities and the topology of a correlated graph. More precisely, the goal is to label the nodes of the anonymized graph so that the adjacency matrix of the anonymized graph matches the adjacency matrix of the correlated graph as closely as possible. We will review prior results on this problem for the case of Erdős–Rényi graphs, and present some new results for stochastic block models. Joint work with Joseph Lubars. 
Leandros Tassiulas Yale University 
Cooperation and competition on exchange of network connectivity services
The rapid increase of mobile data poses new challenges to wireless network designers that explore alternate means for wireless connectivity exploiting the proliferation of networks in unlicensed parts of the spectrum as well as of handheld devices with multiple radio interfaces. We will present schemes for the creation of user provided networks where a mobile user may gain network access when another user with a direct network connection is willing to relay its traffic received through a devicetodevice link between the users. We will focus on incentives mechanisms that facilitate the creation of such User Provided Networks in a way that all participants gain in terms of access capacity as well as energy consumption. 