 
Last updated on September 25, 2017. This conference program is tentative and subject to change
Technical Program for Wednesday October 1, 2014

WeA1 
Library 
Topics in Machine Learning 
Invited Session 
Chair: Farnoud (Hassanzadeh), Farzad  Caltech 
Organizer: Farnoud, Farzad  Univ. of Virginia 
Organizer: Milenkovic, Olgica  Univ. of Illinois 
Organizer: Mazumdar, Arya  Univ. of Massachusetts Amherst 

08:3008:50, Paper WeA1.1  
Sampling and Estimation in Slow Mixing Markov Processes (I) 
Santhanam, Narayana Prasad  Univ. of Hawaii 

08:5009:10, Paper WeA1.2  
Group Testing with Unreliable Elements (I) 
Mazumdar, Arya  Univ. of MinnesotaTwin Cities 
Mohajer, Soheil  Univ. of Minnesota 
Keywords: Universal Algorithms and Machine Learning
Abstract: We consider a generalization of the wellknown nonadaptive group testing problem. In our generalization, tests or measurements are performed in the presence of a number of unknown but fixed pretenders, that will, with certain probability be active during any test. We show some simple extensions of the achievability results of group testing tailored for this case.


09:1009:30, Paper WeA1.3  
The Minimal Realization Problems for Hidden Markov Models (I) 
Huang, Qingqing  MIT 
Dahleh, Munther  MIT 
Ge, Rong  Microsoft Res 
Kakade, Sham  Microsoft Res 
Keywords: Universal Algorithms and Machine Learning, Statistical Signal Processing
Abstract: Abstract—In this paper, we study the problem of finding a minimal order (quasi) Hidden Markov Model for a random process, which is the output process of an unknown stationary HMM of finite order. In the main theorem, we show that excluding a measure zero set in the parameter space of transition and observation probability matrices, both the minimal quasi HMM realization and the minimal HMM realization can be efficiently constructed based on the joint probabilities of length N output strings, for N > max(4 log_d(k) + 1; 3), where d is the size of the output alphabet size, and k is the minimal order of the realization. We also aim to connect the two lines of literature: realization theory of HMMs / automatas, and the recent development in learning latent variable models with tensor techniques.


09:3009:50, Paper WeA1.4  
Approximate Sorting for Data Streams and User Preference Rankings (I) 
Farnoud, Farzad  Univ. of Virginia 
Yaakobi, Eitan  Tech.  Israel Inst. of Tech. 
Bruck, Jehoshua  Caltech 

09:5010:10, Paper WeA1.5  
Statistical Algorithms and a Lower Bound for Planted Clique (I) 
Grigorescu, Elena  Purdue Univ. 
Feldman, Vitaly  IBM Res.  Almaden 
Reyzin, Lev  Univ. of Illinois at Chicago 
Vempala, Santosh  Georgia Tech. 
Xiao, Ying  Georgia Inst. of Tech. 

WeA2 
Solarium 
Controlled Sensing and Information Processing in Networks I 
Invited Session 
Chair: Nedich, Angelia  Univ. of Illinois 

08:3008:50, Paper WeA2.1  
Compressive and Coded Change Detection with Applications in Structural Health Monitoring (I) 
Atia, George  Univ. of Central Florida 

08:5009:10, Paper WeA2.2  
Remote Estimation Games Over Shared Networks (I) 
Vasconcelos, Marcos  Univ. of Maryland 
Martins, Nuno  Univ. of Maryland 
Keywords: Networked Control Systems, Detection and Estimation, Optimization
Abstract: Consider a system that is formed by two sensors, which measure a random variable each, and two remote estimators. Each estimator is tasked to produce an estimate of one of the variables based on information sent to it by its corresponding sensor. We propose a new class of problems in which information is transmitted from the sensors to the estimators via a collision channel with and without capture. Our results characterize the structure of the policies that are in Nash equilibrium or are secure in a welldefined sense. We compare these results with the ones obtained for the case when the sensors fully cooperate as members of a team to minimize the same cost.


09:1009:30, Paper WeA2.3  
Asynchronous Incremental BlockCoordinate Descent (I) 
Aytekin, Arda  KTH  Royal Inst. of Tech 
Feyzmahdavian, Hamid Reza  KTH  Royal Inst. of Tech 
Johansson, Mikael  Royal Inst. of Tech. (KTH) 
Keywords: Optimization, Distributed Computation on Networks, Decentralized and Distributed Control
Abstract: This paper studies a flexible algorithm for minimizing a sum of component functions, each of which depends on a large number of decision variables. Such formulations appear naturally in ``big data'' applications, where each function describes the loss estimated using the data available at a specific machine, and the number of features under consideration is huge. In our algorithm, a coordinator updates a global iterate based on delayed partial gradients of the individual objective functions with respect to blocks of coordinates. Delayed incremental gradient and delayed coordinate descent algorithms are obtained as special cases. Under the assumption of strong convexity and block coordinatewise Lipschitz continuous partial gradients, we show that the algorithm converges linearly to a ball around the optimal value. Contrary to related proposals in the literature, our algorithm is delayinsensitive: it converges for any bounded information delay, and its stepsize parameter can be chosen independently of the maximum delay bound.


09:3009:50, Paper WeA2.4  
Optimized Path Planning for Electric Vehicle Routing and Charging (I) 
Alizadeh, Mahnoosh  Stanford Univ 
Wai, HoiTo  Univ. of California Davis 
Scaglione, Anna  Univ. of California Davis 
Goldsmith, Andrea  Stanford Univ 
Fan, Yueyue  Univ. of California Davis 
Javidi, Tara  Univ. of California, San Diego 
Keywords: Machine Learning and Approximate Dynamic Programming, Optimization, Network Games and Algorithms
Abstract: We consider the decision problem of an individual EV owner who needs to pick a travel path including its charging locations and associated charge amount under timevarying traffic conditions as well as dynamic locationbased electricity pricing. We show that the problem is equivalent to finding the shortest path on an extended transportation graph. In particular, we extend the original transportation graph through the use of virtual links with negative energy requirements to represent charging options available to the user. Using these extended transportation graphs, we then study the collective effects of a large number of EV owners solving the same type of path planning problem under the following control strategies: 1) a social planner decides the optimal route and charge strategy of all EVs; 2) users reach an equilibrium under locationallyvariant electricity prices that are constant over time; 3) the transportation and power systems are separately controlled through marginal pricing strategies, not taking into account their mutual effect on one another. We numerically show that this disjoint type of control can lead to instabilities in the grid as well as inefficient system operation.


09:5010:10, Paper WeA2.5  
Anomaly Detection Over Independent Processes: Switching with Memory 
Cohen, Kobi  Univ. of California, Davis 
Zhao, Qing  Univ. of California, Davis 
Keywords: Detection and Estimation, Intrusion/Anomaly Detection and Diagnosis
Abstract: The problem of sequential detection of anomalous processes among K independent processes is considered. At each time, only a subset of the processes can be observed, and the observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. Each anomalous process incurs a cost per unit time until its anomaly is identified and fixed. Different anomalous processes may incur different costs depending on their criticality to the system. Switching between processes and state declarations are allowed at all times, while decisions are based on all past observations and actions. The objective is a sequential search strategy that minimizes the total expected cost, incurred by all the processes during the detection process, under reliability constraints. We develop a simple closedloop policy (i.e., decisions depend on past observations and actions) for the anomaly detection problem. Asymptotic optimality of the proposed policy is shown when a single process is observed at a time and strong performance are demonstrated by simulation examples under multiprocesses probing.


WeA3 
Butternut 
Dynamic Games and Decision Theory 
Regular Session 
Chair: Pachter, Meir  Air Force Inst. of Tech 

08:3008:50, Paper WeA3.1  
Contract Design for Frequency Regulation by Aggregations of Commercial Buildings 
Balandat, Maximilian  UC Berkeley 
Oldewurtel, Frauke  UC Berkeley 
Chen, Mo  UC Berkeley 
Tomlin, Claire  UC Berkeley 
Keywords: Dynamic Games and Decision Theory, Optimization, Reliable and Robust Control
Abstract: We investigate the contract design problem that an energy aggregator who participates in the wholesale market for Ancillary Services faces. Specifically, we consider a situation in which commercial buildings agree to adjust their heating, ventilation and air conditioning power consumption with respect to a nominal schedule, according to a signal sent by the aggregator. This signal may vary arbitrarily within a certain band, whose (timevarying) width is part of the agreedupon contract between aggregator and building. In return, the aggregator offers monetary rewards to incentivize the individual buildings. This allows the aggregator to bundle the resulting capacities from different buildings and sell the total capacity in the spot market for frequency regulation. The aggregator's problem is to jointly determine nominal schedules, regulation capacities and monetary rewards to maximize its profit, while ensuring that the individual buildings have an incentive to participate. Assuming that there is no private information, we cast the contract design problem as a bilevel optimization problem, which we in turn reformulate as a mixedinteger program. We further show that if the building does not impose negative externalities on the aggregator, the problem reduces to a Linear Program.


08:5009:10, Paper WeA3.2  
Active Target Defense Differential Game 
Pachter, Meir  Air Force Inst. of Tech 
Garcia, Eloy  InfoSciTex Corp 
Casbeer, David W.  Air Force Res. Lab 
Keywords: Dynamic Games and Decision Theory, MultiAgent Systems and Robot Control
Abstract: A pursuitevasion differential game involving three agents is discussed. This scenario considers an Attacker missile pursuing a Target aircraft. The Target is however aided by a Defender missile launched by, say, its wingman, to intercept the Attacker before it reaches the Target aircraft. Thus, a team is formed by the Target and the Defender which cooperate to maximize the distance between the Target aircraft and the point where the Attacker missile is intercepted by the Defender missile, and the Attacker which tries to minimize said distance. The solution to this differential game provides optimal heading angles for the Target and the Defender team to maximize the terminal separation between Target and Attacker and it also provides the optimal heading angle for the Attacker to minimize the said distance.


09:1009:30, Paper WeA3.3  
Rating and Matching in Peer Review Systems 
Xiao, Yuanzhang  UCLA 
Dorfler, Florian  ETH Zurich 
van der Schaar, Mihaela  Univ. of California Los Angeles 
Keywords: Dynamic Games and Decision Theory, Networked Control Systems, Social Networks
Abstract: Peer review (e.g. paper review) is vital for the success of a research community. A key problem in peer review is that the effort in reviewing papers is costly. Hence, it is important to design mechanisms to elicit high effort from reviewers. Exploiting the repeated interaction of the researchers, we propose a rating and matching mechanism to elicit high effort from reviewers. Our proposed mechanism overcomes two major difficulties: adverse selection (i.e. the unidentifiable quality of heterogeneous reviewers) and moral hazard (i.e. the unobservable effort levels from reviewers). Our proposed mechanism assigns and updates ratings for the researchers, and matches researchers' papers to reviewers with similar ratings. In this way, the mechanism identifies different types of reviewers by their ratings, and incentivizes different reviewers to exert the appropriate amount of effort in the equilibrium. Central to our design is the matching rule. We first propose a baseline matching rule, provide design guidelines, and analyze the equilibrium review quality and ratings of researchers. We then extend the baseline rule in two directions. Both extensions result in a class of matching rules that allow us to tune the extent of reward and/or punishment. Interestingly, it is beneficial (in terms of the optimal equilibrium review quality) to reward in the first extension, and to punish in the second, due to the different ways the reward and punishment are carried out.


09:3009:50, Paper WeA3.4  
Optimal Contract Design for Energy Procurement 
Tavafoghi, Hamidreza  Univ. of Michigan 
Teneketzis, Demosthenis  Univ. of Michigan 
Keywords: Dynamic Games and Decision Theory, Optimization
Abstract: We consider a mechanism design problem for strategic agents with multidimensional private information and uncertainty in their utility/cost functions. We show that the optimal mechanism is a menu of contracts that can be implemented as a nonlinear pricing scheme. We illustrate the result by considering an optimal energy procurement mechanism from a strategic seller with conventional (deterministic) and renewable (random) plants. We address the problem of risk sharing and expost voluntary participation (commitment) under uncertainty.


09:5010:10, Paper WeA3.5  
Electricity Pooling Markets with Elastic Demand: A Mechanism Design Approach 
Rasouli, Mohammad  Univ. of Michigan 
Teneketzis, Demosthenis  Univ. of Michigan 
Keywords: Decentralized and Distributed Control, CyberPhysical Systems, Dynamic Games and Decision Theory
Abstract: In the restructured electricity industry, electricity pooling markets are an oligopoly with strategic producers possessing private information (private production cost function). We focus on pooling markets where aggregate demand is represented by a nonstrategic agent. We consider demand to be elastic. We propose a market mechanism that has the following features. (F1) It is individually rational. (F2) It is budget balanced. (F3) It is price efficient, that is, at equilibrium the price of electricity is equal to the marginal cost of production. (F4) The energy production profile corresponding to every nonzero Nash equilibrium of the game induced by the mechanism is a solution of the corresponding centralized problem where the objective is the maximization of the sum of the producers' and consumers' utilities. We identify some open problems associated with our approach to electricity pooling markets.


WeA4 
Pine 
Source Coding and Information Theory 
Regular Session 
CoChair: Grover, Pulkit  Carnegie Mellon Univ 

08:3008:50, Paper WeA4.1  
A Novel Correlation Model for Universal Compression of Parametric Sources 
Beirami, Ahmad  Duke Univ 
Fekri, Faramarz  Georgia Inst. of Tech 
Keywords: Source Coding and Compression, Statistical Signal Processing, Universal Algorithms and Machine Learning
Abstract: In this paper, we consider k parametric sources with unknown source parameter vectors. In this setup, we propose a novel correlation model where the degree of correlation of each parameter vector is governed by a single variable. We derive the properties of the parameter vectors. In particular, we derive bounds on the correlation between the parameter vectors and show show that this will include independence all the way to convergence in mean square sense. Then, we set up the minimax and maximin games in universal compression and characterize the compression risk under the proposed correlation model when side information from one other source is available at both the encoder and the decoder.


08:5009:10, Paper WeA4.2  
Randomized Source Coding with Limited Common Randomness 
Saldi, Naci  Queen's Univ 
Linder, Tamas  Queen's Univ 
Yuksel, Serdar  Queen's Univ 
Keywords: Source Coding and Compression, Information Theory
Abstract: We study a Shannontheoretic version of the socalled distribution preserving quantization problem. In this problem, a stationary and memoryless source is encoded under a distortion constraint with the additional requirement that the reproduction also be stationary and memoryless with a given law (which may be different from the source distribution). The encoder and decoder are stochastic and assumed to have access to common randomness which is independent of the source. Recent work has obtained the minimum achievable coding rate for a given distortion level under the assumption that unlimited common randomness is available. Here we consider the general case where the available common randomness may be limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. Connections with recent work by Cuff on distributed channel synthesis are also discussed.


09:1009:30, Paper WeA4.3  
Rateless Lossy Compression Via the Extremes 
No, Albert  Stanford 
Weissman, Tsachy  Stanford 
Keywords: Source Coding and Compression
Abstract: We begin by presenting a simple lossy compressor operating at nearzero rate: The encoder merely describes the indices of the few maximal source components, while the decoder's reconstruction is a natural estimate of the source components based on this information. This scheme turns out to be nearoptimal for the memoryless Gaussian source in the sense of achieving the zerorate slope of its distortionrate function. Motivated by this finding, we then propose a scheme comprising of iterating the above lossy compressor on an appropriately transformed version of the difference between the source and its reconstruction from the previous iteration. The proposed scheme achieves the rate distortion function of the Gaussian memoryless source (under squared error distortion) when employed on any finitevariance ergodic source. It further possesses desirable properties we respectively refer to as infinitesimal successive refinability, ratelessness, and complete separability. Its storage and computation requirements are of order no more than frac{n^2}{log^{beta} n} per source symbol for beta>0 at both the encoder and decoder. Though the details of its derivation, construction, and analysis differ considerably, we discuss similarities between the proposed scheme and the recently introduced SPARC of Venkataramanan et al.


09:3009:50, Paper WeA4.4  
Information Friction Limits on Computation 
Vyavahare, Pooja  Indian Inst. of Tech. Bombay 
Mahzoon, Majid  Carnegie Mellon Univ 
Grover, Pulkit  Carnegie Mellon Univ 
Limaye, Nutan  Indian Inst. of Tech. Bombay 
Manjunath, D  IIT Bombay 
Keywords: Information Theory, Distributed Computation on Networks
Abstract: The recently proposed ``Information friction'' model accounts for energy losses incurred in moving bits on a computational substrate and was first studied in the context of encoding and decoding computations for communication. Information friction loss is modeled as being proportional to bitmeters, the sum of the lengths over which the bits are transported during the computation. Its analysis provides us with an understanding of the fundamental energy requirements for computation. In this paper, we obtain lower bounds on information friction for several canonical computations that have been analyzed to obtain ``AT^2'' bounds in the context of what is called ``VLSI complexity'' and, more recently, in deriving computation throughput in the context of wireless sensor networks.


09:5010:10, Paper WeA4.5  
The Capacity of NonIdentical Adaptive Group Testing 
Kealy, Thomas Owen  Univ. of Bristol 
Johnson, Oliver  Univ. of Bristol 
Piechocki, Robert  Univ. of Bristol 
Keywords: Information Theory, Coding Techniques and Applications, Source Coding and Compression
Abstract: We consider the group testing problem, in the case where the items are defective independently but with nonconstant probability. We introduce and analyse an algorithm to solve this problem by grouping items together appropriately. We give conditions under which the algorithm performs essentially optimally in the sense of informationtheoretic capacity. This has applications to the allocation of spectrum to cognitive radios, in the case where a database gives prior information that a particular band will be occupied.


WeA5 
Lower Level 
Information Processing Systems 
Invited Session 
Chair: Stojanovic, Milica  Northeastern Univ 

08:3008:50, Paper WeA5.1  
Active Target Detection with Navigation Costs: A Randomized Benchmark (I) 
Choudhary, Sunav  Univ. of Southern California 
Kartik, Dhruva  Indian Inst. of Tech. Guwahati 
Kumar, Naveen  Univ. of Southern California 
Narayanan, Srikanth  Univ. of Southern California 
Mitra, Urbashi  Univ. of Southern California 
Keywords: Sparse Data Analysis, Detection and Estimation, Optimization
Abstract: Detecting the presence of a target within a field, is a longstanding problem of interest in a variety of applications from environmental to military. We consider a framework in which a single autonomous vehicle (AV), physically samples a decaying separable field to determine the source location; the key metric of interest being the tradeoff between sample and computational complexity, navigational cost and the detection error probability. Withoutnavigation costs and detection error probability considerations, standard lowrank matrix completion theory is orderoptimal for sample complexity of field reconstruction. We derive an active (adaptive) sampling and reconstruction strategy for target detection which takes the form of a partial lowrank matrix completion algorithm and analyze its detection error probability and sample complexity for exponentially decaying target signatures to demonstrate a substantial improvement over naive applications of lowrank matrix completion.The results are consistent with the intuition that detection should be easier than estimation. As a consequence of the strong concentration properties of the Euclidean Traveling Salesperson Problem, it turns out (somewhat surprisingly) that separation of navigational path planning and sampling pattern design is order optimal for uniform prior on the target location and a given detection error probability.


09:1009:30, Paper WeA5.3  
Estimation and Tracking of TimeVarying Channels in OFDM Systems (I) 
Stojanovic, Milica  Northeastern Univ. 
Tadayon, Sayedamirhossein  Northeastern Univ. 

09:3009:50, Paper WeA5.4  
SelfSynchronizing Signal Parsing with Spiking FeatureDetection Filters 
Loeliger, HansAndrea  ETH Zurich 
Neff, Sarah  ETH Zurich 
Reller, Christoph  ETH Zurich 
Keywords: Detection and Estimation
Abstract: Following an earlier suggestion, the concept of a hierarchical network of featuredetection filters is developed. The individual filters are derived from a localized leastsquares approach based on nongenerative state space models, which results in simple forwardonly recursions for the actual computations. It is demonstrated that such filters can naturally cope with spiking signals, and the use of spiking signals in such networks is advocated. The feasibility of the approach is demonstrated with a fourlayer network that understands Morse code.


09:5010:10, Paper WeA5.5  
Least Favorable Distributions to Facilitate the Design of Detection Systems with Sensors at Deterministic Locations 
Fonseca Jr, Benedito  ARRIS Inc 
Keywords: Detection and Estimation, Sensor Networks, Statistical Signal Processing
Abstract: The design of a sensor detection system to detect an emitter at a random location is difficult because of two issues: the conditional dependence among sensors' measurements and the composite hypothesis caused by the lack of knowledge regarding the emitter location distribution. When sensor locations are also random, it was recently shown that it is possible to circumvent these issues by using a least favorable distribution for the emitter location; however, such results do not apply when sensors are at deterministic known locations. In this paper, it is shown that a least favorable distribution for the emitter location can also facilitate the design of sensor detection systems when sensors are at deterministic known locations. It is further shown that, in several cases of interest, the problem of finding a least favorable distribution for the emitter location is equivalent to the obnoxious facility location problem from the field of operations research; and it is shown how the techniques of this field can be used to find the least favorable distribution and facilitate the system design.


WeB1 
Library 
Networks, Games, and Algorithms I 
Invited Session 
Chair: Vaidya, Nitin  Univ. of Illinois 

10:3010:50, Paper WeB1.1  
On Competitive Provisioning of AdSupported Cloud Services (I) 
Nair, Jayakrishnan  California Inst. of Tech 
Subramanian, Vijay  Univ. of Michigan 
Wierman, Adam  California Inst. of Tech 
Keywords: Pricing and Congestion Control, Queuing Theory and Analysis, Network Games and Algorithms
Abstract: Motivated by cloud services with adsupported revenues, we consider the interplay of network effects, congestion, and competition in determining the market structure in such environments. In particular, we study the strategic interactions between competing service providers and a user base, modeling congestion sensitivity and two forms of positive network effects: ``firmspecific'' versus ``industrywide.'' Our analysis reveals that users are generally no better off due to competition in a marketplace of adsupported services as the congestion levels are of the same order as if there were only one firm. Further, our analysis highlights an important contrast between firmspecific and industrywide network effects: multiple firms can coexist in a marketplace with industrywide network effects, but nearmonopolies tend to emerge in marketplaces with firmspecific network effects.


10:5011:10, Paper WeB1.2  
A Result for Nonhomogeneous PlaceDependent Markov Chains Arising in the Study of the AIMD Algorithm and Its Application to Certain Optimisation Problems (I) 
Wirth, Fabian  IBM Res. 
Stuedli, Sonja  Univ. of Newcastle 
Yu, Jia Yuan  Concordia Univ. 
Corless, Martin  Purdue Univ. 
Shorten, Robert  IBM Res. 

11:1011:30, Paper WeB1.3  
On Detecting Epidemics from Weak Signatures (I) 
Meirom, Eli  Tech. 
Caramanis, Constantine  The Univ. of Texas at Austin 
Mannor, Shie  Tech. 
Orda, Ariel  Tech. 
Shakkottai, Sanjay  The Univ. of Texas at Austin 

11:3011:50, Paper WeB1.4  
Competition in Electricity Markets with Renewable Sources (I) 
Acemoglu, Daron  MIT 
Kakhbod, Ali  MIT 
Ozdaglar, Asu  MIT 

11:5012:10, Paper WeB1.5  
Cooperation in Groups: An Evolutionary Games Approach (I) 
Elazouzi, Rachid  Univ. of Avignon 
Altman, Eitan  INRIA 
Ilaria, Brunetti  INRIA Sophia Antipolis 
Haddad, Majed  Univ. of Avignon 

12:1012:30, Paper WeB1.6  
Incentive Mechanism and Protocol Design for Crowdsourcing Systems (I) 
Xie, Hong  The Chinese Univ. of Hong Kong 
Lui, John C.S.  The Chinese Univ. of Hong Kong 
Jiang, Joe Wenjie  Goole Inc, USA 
Chen, Wei  Microsoft Res. Asia 
Keywords: Network Games and Algorithms, Performance Analysis
Abstract: Crowdsourcing systems such as Amazon Mechanical Turk, Yahoo! !Answers, and Google Helpouts have attracted extensive attention over the past few years. In a crowdsourcing system, a large group of workers solve the tasks outsourced by requesters. To make a crowdsourcing system sustainable, it is vital to attract users (both requesters and workers) to participate, and incentivize highquality solutions. To achieve this objective, we design an effective incentive mechanism and reputation protocol. Our design incorporates various important elements of a crowdsourcing system such as workers having heterogeneous skill sets (i.e., some are experts while others are novices), and task assignment process, rating system, etc. Our incentive mechanism is composed of a rating system and a reward dividing scheme, and requires the system administrator to divide the reward based on requesters' rating on the solution quality. We derive the minimum reward needed so that expert workers are guaranteed provide highquality solutions. We show that novice workers will provide lowquality solutions, and our reputation protocol eliminates this undesirable behavior, by tracking a worker's solution history and penalizing him when his reputation is poor. We apply repeated gametheoretic frameworks to quantify the impact of reputation protocol on requesters' overhead (i.e., cost in guaranteeing high quality solutions).


WeB2 
Solarium 
Interactive Communication 
Invited Session 
Chair: Braverman, Mark  Princeton Univ 

10:3010:50, Paper WeB2.1  
Strong Converse for Degraded Wiretap Channel Via Active Hypothesis Testing (I) 
Hayashi, Masahito  Nagoya Univ 
Tyagi, Himanshu  UC San Diego 
Watanabe, Shun  Univ. of Tokushima 
Keywords: Security and Trust, Information Theory, Information Theoretic Approaches in Wireless Communications
Abstract: We establish an upper bound on the rate of codes for a wiretap channel with public feedback for a fixed probability of error and secrecy parameter. As a corollary, we obtain a strong converse for the capacity of a degraded wiretap channel with public feedback. Our converse proof is based on a reduction of active hypothesis testing for discriminating between two channels to coding for wiretap channel with feedback.


10:5011:10, Paper WeB2.2  
An Interactive Information Odometer and Applications (I) 
Braverman, Mark  Princeton Univ. 
Weinstein, Omri  Princeton Univ. 

11:1011:30, Paper WeB2.3  
The Gaussian Channel with Noisy Feedback: NearCapacity Performance Via Simple Interaction (I) 
BenYishai, Assaf  Tel Aviv Univ 
Shayevitz, Ofer  Tel Aviv Univ 
Keywords: Information Theory, Wireless Communication Systems, Coding for Wireless Communications
Abstract: Consider a pair of terminals connected by two independent additive white Gaussian noise channels, and limited by individual power constraints. The first terminal would like to reliably send information to the second terminal, within a given error probability. We construct an explicit interactive scheme consisting of only (nonlinear) scalar operations, by endowing the SchalkwijkKailath noiseless feedback scheme with modulo arithmetic. Our scheme achieves a communication rate close to the Shannon limit, in a small number of rounds. For example, for an error probability of 1e6, if the Signal to Noise Ratio (SNR) of the feedback channel exceeds the SNR of the forward channel by 20dB, our scheme operates 0.8dB from the Shannon limit with only 19 rounds of interaction. In comparison, attaining the same performance using state of the art Forward Error Correction (FEC) codes requires two orders of magnitude increase in delay and complexity. On the other extreme, a minimal delay uncoded system with the same error probability is bounded away by 9dB from the Shannon limit.


11:3011:50, Paper WeB2.4  
Asymmetric Compression (I) 
Natarajan Ramamoorthy, Sivaramakrishnan  Univ. of Washington, Seattle 
Rao, Anup  Univ. of Washington 

11:5012:10, Paper WeB2.5  
Information Complexity for MultiParty NumberInHand Communication (I) 
Oshman, Rotem  Princeton Univ. 

12:1012:30, Paper WeB2.6  
Interactive Channel Capacity Revisited (I) 
Haeupler, Bernhard  Carnegie Mellon Univ. 

WeB3 
Butternut 
Information Theoretic Applications in Wireless 
Regular Session 
CoChair: Zeineddine, Khalid  Northwestern Univ 

10:3010:50, Paper WeB3.1  
Using RelativeRelevance of Data Pieces for Efficient Communication, with an Application to Neural Data Acquisition 
Mahzoon, Majid  Carnegie Mellon Univ 
Albalawi, Hassan  Carnegie Mellon Univ 
Li, Xin  Carnegie Mellon Univ 
Grover, Pulkit  Carnegie Mellon Univ 
Keywords: Information Theoretic Approaches in Wireless Communications, Sensor Networks in Communications, Universal Algorithms and Machine Learning
Abstract: In this paper, we consider the problem of communicating data from distributed sensors for the goal of inference. Two inference problems of linear regression and binary linear classification are investigated. Assuming perfect training of the classifier, an approximation of the problem of minimizing classification errorprobability under Gaussianity assumptions leads us to recover Fisher score: a metric that is commonly used for feature selection in machine learning. Further, this allows us to soften the notion of feature selection by assigning a degree of relevance to each feature based on the number of bits assigned to it. This relative relevance is used to obtain numerical results on savings on number of bits acquired and communicated for classification of neural data obtained from Electrocorticography (ECoG) experiments. The results demonstrate that significant savings on costs of communication can be achieved by compressing Big Data at the source.


10:5011:10, Paper WeB3.2  
Capacity Region of the Reciprocal Deterministic 3Way Channel Via DeltaY Transformation 
Maier, Henning  RWTH Aachen Univ 
Chaaban, Anas  RuhrUniv. Bochum 
Mathar, Rudolf  RWTH Aachen Univ 
Sezgin, Aydin  RuhrUniv. Bochum 
Keywords: Information Theoretic Approaches in Wireless Communications, Information Theory
Abstract: A linear shift deterministic 3way channel with reciprocal channel gains is considered in this work. The 3way channel is an extension of the 2way channel introduced by Shannon. Here, a number of six messages is exchanged, one message from each user to the two other users. Each user operates in a fullduplex mode. We derive the capacity region of this 3way channel w.r.t. the linear shift deterministic channel model. To this end, first, an outer bound is derived using cutset and genieaided upper bounds. Then, it is noted that the outer bound bears a resemblance to the capacity region of a related linear shift deterministic Ychannel. Utilizing a DeltaY transformation, the optimal scheme for the related Ychannel is modified in a way that achieves the outer bound of the 3way channel. Mainly, the capacity achieving communication schemes are based on multiway relaying by signal alignment, interference neutralization and backward decoding. We also consider a scheme which is based on interference alignment only. It turns out, that for the symmetric linear deterministic 3way channel, this scheme is optimal. Thus, backward decoding and the resulting delays are avoided.


11:1011:30, Paper WeB3.3  
On the DiversityMultiplexing Tradeoff of SecretKey Agreement Over MultipleAntenna Channels 
Zorgui, Marwen  King Abdullah Univ. of Science and Tech 
Rezki, Zouheir  King Abdullah Univ. of Science and Tech 
Alomair, Basel  King Abdulaziz City for Science and Tech 
Alouini, MohamedSlim  King Abdullah Univ. of Science and Tech 
Keywords: Information Theoretic Approaches in Wireless Communications, MIMO Systems, Information Theory
Abstract: We consider secretkey agreement with public discussion over Rayleigh fading quasistatic channels. First, the secretkey diversity gain and the secretkey multiplexing gain are defined. Then, the secretkey diversity multiplexing tradeoff (DMT) is established. The eavesdropper is shown to ``steal'' only transmit antennas. We show that likewise the DMT without secrecy constraint, the secretkey DMT is the same either with or without full channel state information (CSI) at the transmitter (CSIT). This insensitivity of secretkey DMT toward CSIT highlights a fundamental difference between secretkey agreement and the wiretap channel whose secret DMT depends crucially on CSIT. Several secretkey DMTachieving schemes are presented in case of full CSIT.


11:3011:50, Paper WeB3.4  
Gaussian MIMO Wiretap Channel under Receiver Side Power Constraints 
Banawan, Karim  Univ. of Maryland 
Ulukus, Sennur  Univ. of Maryland 
Keywords: Information Theoretic Approaches in Wireless Communications, Information Theory, MIMO Systems
Abstract: We consider the multipleinput multipleoutput (MIMO) wiretap channel under a minimum receiverside power constraint in addition to the usual maximum transmitterside power constraint. This problem is motivated by energy harvesting communications with wireless energy transfer, where an added goal is to deliver a minimum amount of energy to a receiver in addition to delivering secure data to another receiver. In this paper, we characterize the exact secrecy capacity of the MIMO wiretap channel under transmitter and receiverside power constraints. We first show that solving this problem is equivalent to solving the secrecy capacity of a wiretap channel with a doublesided correlation matrix constraint on the channel input. We show the converse by extending the channel enhancement technique to our case. We present two achievable schemes that achieve the secrecy capacity: the first achievable scheme uses a Gaussian codebook with a fixed mean, and the second achievable scheme uses artificial noise (or cooperative jamming) together with a Gaussian codebook. The role of the mean or the artificial noise is to enable energy transfer without sacrificing from the secure rate. This is the first instance of a channel model where either the use of a mean signal or use of channel prefixing via artificial noise is strictly necessary in the MIMO wiretap channel.


11:5012:10, Paper WeB3.5  
On Capacity Regions of TwoReceiver Broadcast Packet Erasure Channels with Feedback and Memory 
Heindlmaier, Michael  Tech. Univ. München 
Reyhanian, Navid  Univ. of Tehran 
Saeedi Bidokhti, Shirin  Tech. Univ. München 
Keywords: Information Theoretic Approaches in Wireless Communications, Network Coding in Communication
Abstract: The tworeceiver broadcast packet erasure channel with feedback and memory is studied. Memory is modelled using a finitestate Markov chain representing a channel state. Outer and inner bounds on the capacity region are derived when the channel state is strictly causally known at the transmitter. The bounds are both formulated in terms of feasibility problems and they are matching in all but one of the constraints. The results are extended to feedback with larger delay. Numerical results show that the gains offered through feedback can be quite large.


12:1012:30, Paper WeB3.6  
Optimal Spectrum Management for the TwoUser Gaussian Interference Channel: Avoidance or Cancellation? 
Zeineddine, Khalid  Northwestern Univ 
Honig, Michael  Northwestern Univ 
Nagaraj, Shirish  Motorola, Inc 
Keywords: Wireless Communication Systems, Multiuser Detection and Estimation, Information Theoretic Approaches in Wireless Communications
Abstract: We study the continuous frequency spectrum management problem for the twouser Gaussian interference channel. We consider a successive interference cancellation scheme between the two receivers. In this model, receiver 1 decodes user 1 and passes the decoded bits to receiver 2 which in turn cancels the interference from user 1. We analytically determine the optimal power spectral density for users 1 and 2 for an asymmetric flat fading channel. We show when frequency division multiplexing (FDM) is optimal. We also show when frequency sharing with cancellation dominates FDM. Moreover we formulate the frequency selective case as a convex optimization problem. Both the sum power constraint and the individual power constraint are analyzed. As opposed to the linear case (no cancellation), only two pure spectrum allocation schemes are optimal when we have interference cancellation: either sharing or orthogonal. No mixed scheme is optimal. The two regions are determined by the channel conditions and are independent of the power constraints imposed. We also notice that the FDM region shrinks and the spectral efficiency increases as a result of introducing cancellation.


WeB4 
Pine 
Wireless Communication Systems 
Regular Session 
Chair: UysalBiyikoglu, Elif  Metu Odtu 

10:3010:50, Paper WeB4.1  
Impact of EndUser Decisions on Pricing in Wireless Networks under a MultipleUserSingleProvider Setting 
Yang, Yingxiang  UIUC 
Mandayam, Narayan  WINLAB, Rutgers Univ 
Keywords: Wireless Communication Systems, Dynamic Games and Decision Theory, Pricing and Congestion Control
Abstract: We consider the impact of enduser decisionmaking on pricing of wireless resources when there is uncertainty in the Quality of Service (QoS) guarantees offered by the Service Provider (SP). Specifically, we consider the scenario where an SP tries to sell wireless broadband services to multiple potential customers when the advertised transmission rate cannot be fully guaranteed at all times. Modeling the decisionmaking of the endusers using Prospect Theory (a NobelPrizewinning theory that captures human decisionmaking and its deviation from Expected Utility Theory (EUT)), we formulate a game to study the interplay between the price offerings, bandwidth allocation by the SP and the service choices made by endusers. We characterize the Nash Equilibria (NE) of the underlying game and study the impact of such decisionmaking on the system performance as well as revenue. We propose "prospect pricing", a pricing mechanism that can make the system robust to decisionmaking that deviates from EUT.


10:5011:10, Paper WeB4.2  
No Regrets: Distributed Power Control under TimeVarying Channels and QoS Requirements 
Stiakogiannakis, Ioannis  Inria 
Mertikopoulos, Panayotis  CNRS (French National Center for Scientific Res 
Touati, Corinne Eva  Inria 
Keywords: Wireless Communication Systems, Optimization, Network Games and Algorithms
Abstract: The problem of power control in wireless networks consists of adjusting transmit power in order to achieve a target SINR level in the presence of noise and interference from other users. In this paper, we examine the performance of the seminal Foschini–Miljanic (FM) power control scheme in networks where channel conditions and users’ quality of service (QoS) requirements vary arbitrarily with time (e.g. due to user mobility, fading, etc.). Contrary to the case of static and/or ergodic channels, the system optimum power configuration may evolve over time in an unpredictable fashion, so users must adapt to changes in the wireless medium (or their own requirements) “on the fly”, without being able to anticipate the system evolution. To account for these considerations, we provide a formulation of power control as an online optimization problem and we show that the FM dynamics lead to no regret in this dynamic context. Specifically, in the absence of maximum transmit power constraints, we show that the FM power control scheme performs at least as well as (and typically outperforms) any fixed transmit profile, irrespective of how the system varies with time; finally, to account for maximum power constraints that occur in practice, we introduce an adjusted version of the FM algorithm which retains the convergence and noregret properties of the original algorithm in this constrained setting.


11:1011:30, Paper WeB4.3  
A BitError Based Capture Model for EPCglobal RFID Systems 
Schantin, Andreas  Univ. of Siegen 
Ruland, Christoph  Univ. of Siegen 
Keywords: Wireless Communication Systems
Abstract: The tag inventory process in systems according to the EPCglobal UHF RFID Air Interface Protocol is based on framed slotted ALOHA (FSA). For FSA, the wellknown maximum throughput of 0.37 is reached when the number of allocated slots is equal to the number of contending tags. These values do not hold when captures happen in the system, i.e. when information can be recovered from collision slots. In this work, we propose a new capture model that allows us to calculate the capture probability in a noisy channel, depending on the occupation number of a slot. We will apply the model to AWGN, as well as fading channels, and show the expected capture probabilities for these cases. We will further show how the proposed model can be used to estimate the throughput improvement in a system when forward error correction is employed during the tag inventory.


11:3011:50, Paper WeB4.4  
ComputeAndForward: Finding the Best Equation 
Sahraei, Saeid  EPFL 
Gastpar, Michael  Univ. of California, Berkeley 
Keywords: Wireless Communication Systems, Information Theoretic Approaches in Wireless Communications, MIMO Systems
Abstract: ComputeandForward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optimizing these coefficients is a Shortest Lattice Vector (SLV) problem. In general, the SLV problem is known to be prohibitively complex. In this paper, we show that the particular SLV instance resulting from the ComputeandForward problem can be solved in low polynomial complexity and give an explicit deterministic algorithm that is guaranteed to find the optimal solution.


11:5012:10, Paper WeB4.5  
Downlink Resource Allocation under TimeVarying Interference: Fairness and Throughput Optimality 
Raman, Ravi Kiran  IIT Madras 
Jagannathan, Krishna  IIT Madras 
Keywords: Wireless Communications at Large, Queuing Theory and Analysis, Stochastic Systems and Control
Abstract: We address the problem of downlink resource allocation in the presence of timevarying interference. We consider a scenario where users served by a base station face interference from a neighbouring base station that uses the same channels. We model the interference from the neighbouring base station as an ON/OFF renewal process, that arises due to its idle and busy cycles. The users feedback their downlink SINR values to their base station, but these values are outdated. In this setting, we characterize how Layer 2 can optimally exploit the reported SINR values, which could be unreliable due to timevarying interference. In particular, we propose resource allocation policies in two wellknown paradigms. First, we address the problem of alphafair scheduling, and propose a policy that ensures asymptotic convergence to the optimal alphafair throughput. Second, we propose a throughput optimal resource allocation policy, i.e., a policy that can stably support the largest possible set of traffic rates under the interference scenario considered. Estimating the outage probability from the outdated SINR values plays an important role in both scheduling paradigms, and we accomplish this using tools from renewal theory.


WeB5 
Lower Level 
Optimization Theory 
Regular Session 
Chair: Chandrasekaran, Venkat  California Inst. of Tech 
CoChair: Kulkarni, Ankur  Indian Inst. of Tech. Bombay 

10:3010:50, Paper WeB5.1  
Differentially Private Distributed Protocol for Electric Vehicle Charging 
Han, Shuo  Univ. of Pennsylvania 
Topcu, Ufuk  Univ. of Pennsylvania 
Pappas, George  Univ. of Pennsylvania 
Keywords: Optimization, Decentralized and Distributed Control
Abstract: In distributed electric vehicle (EV) charging, an optimization problem is solved iteratively between a central server and the charging stations by exchanging coordination signals that are publicly available to all stations. The coordination signals depend on user demand reported by charging stations and may reveal private information of the users at the stations. From the public signals, an adversary can potentially decode private user information and put user privacy at risk. This paper develops a distributed EV charging algorithm that preserves differential privacy, which is a notion of privacy recently introduced and studied in theoretical computer science. The algorithm is based on the socalled Laplace mechanism, which perturbs the public signal with Laplace noise whose magnitude is determined by the sensitivity of the public signal with respect to changes in user information. The paper derives the sensitivity and analyzes the suboptimality of the differentially private charging algorithm. In particular, we obtain a bound on suboptimality by viewing the algorithm as an implementation of stochastic gradient descent. In the end, numerical experiments are performed to investigate various aspects of the algorithm when being used in practice, including the number of iterations and tradeoffs between privacy level and suboptimality.


10:5011:10, Paper WeB5.2  
On the Relationship between Queues and Multipliers 
Valls, Víctor  National Univ. of Ireland Maynooth 
Leith, Douglas  National Univ. of Ireland Maynooth 
Keywords: Optimization
Abstract: We show that the occupancy of appropriate queues can be used as a surrogate for Lagrange multipliers in convex optimisation. Our analysis uses only elementary methods, and is not asymptotic in nature. One immediate consequence is that in network problems the scaled link queue occupancy can be used as multipliers when calculating the dual function. Conversely, the connection with multipliers casts light on the link queue behaviour under optimal decisionmaking (not just maxweight scheduling). Namely, on links corresponding to active constraints the queue occupancy necessarily grows as step size is reduced. Importantly, our analysis encompasses nonlinear constraints, and so generalises analysis beyond conventional queueing networks.


11:1011:30, Paper WeB5.3  
Dimensionality Reduction of Affine Variational Inequalities Using Random Projections 
Prabhakar, Bharat  Indian Inst. of Tech. Bombay 
Kulkarni, Ankur  Indian Inst. of Tech. Bombay 
Keywords: Optimization
Abstract: We present a method for dimensionality reduction of an affine variational inequality (AVI) defined over a compact feasible region. Our method is a randomized algorithm centered around the Johnson Lindenstrauss lemma that produces with high probability an approximate solution for the given AVI by solving a lowerdimensional AVI. The lower dimension can be chosen based on the quality of approximation desired. The algorithm can also be used as a subroutine in an exact algorithm for generating an initial point close to the solution. The lowerdimensional AVI is obtained by appropriately projecting the original AVI on a randomly chosen subspace. The lower dimensional AVI is solved using standard solvers and from this solution an approximate solution to the original AVI is obtained through an inexpensive process. Our numerical experiments corroborate the theoretical results and validate that the algorithm provides a good approximation at very low dimensions and substantial savings in time for an exact solution.


11:3011:50, Paper WeB5.4  
Distributed SubgradientPush Online Convex Optimization on TimeVarying Directed Graphs 
Akbari, Mohammad  Queen's Univ 
Gharesifard, Bahman  Queen's Univ 
Linder, Tamas  Queen's Univ 
Keywords: Optimization, Distributed Computation on Networks, Decentralized and Distributed Control
Abstract: This paper presents a class of subgradientpush algorithms for online distributed optimization over timevarying networks. In this setting, a private strongly convex objective function is revealed to each agent at each time step. In the next time step, this agent makes a decision about its state using this knowledge, along with the information gathered only from its neighboring agents, prescribed by a sequence of timevarying directed graphs. Under the assumption that this sequence is uniformly strongly connected, we design an algorithm, distributed over this timevarying topology, that guarantees that the individual regret, the difference between the accumulated cost of agents' states and the best static offline cost, grows only sublinearly. Simulations illustrate our results.


11:5012:10, Paper WeB5.5  
BroadcastBased Distributed Alternating Direction Method of Multipliers 
Makhdoumi, Ali  MIT 
Ozdaglar, Asu  MIT 
Keywords: Optimization, Distributed Computation on Networks, Decentralized and Distributed Control
Abstract: We consider a multi agent optimization problem where a network of agents collectively solves a global optimization problem with the objective function given by the sum of locally known convex functions. We propose a fully distributed broadcastbased Alternating Direction Method of Multipliers (ADMM), in which each agent broadcasts the outcome of his local processing to all his neighbors. We show that both the objective function values and the feasibility violation converge with rate O( frac{1}{T} ), where T is the number of iterations. This improves upon the O(frac{1}{sqrt{T}} convergence rate of subgradientbased methods.We also characterize the effect of network structure and the choice of communication matrix on the convergence speed. Because of its broadcast nature, the storage requirements of our algorithm are much more modest compared to the distributed algorithms that use pairwise communication between agents.


12:1012:30, Paper WeB5.6  
Relative Entropy Optimization and Applications 
Chandrasekaran, Venkat  California Inst. of Tech. 
Shah, Parikshit  Massachusetts Inst. of Tech. 

WeC1 
Library 
Dynamics and Control of Decentralized Systems II 
Invited Session 
Chair: Beck, Carolyn  Univ. of Illinois 

13:3013:50, Paper WeC1.1  
Overlap Graph Clustering Via Successive Removal (I) 
Ray, Avik  Univ. of Texas at Austin 
Ghaderi, Javad  Columbia Univ 
Sanghavi, Sujay  Univ. of Texas, Austin 
Shakkottai, Sanjay  The Univ. of Texas at Austin 
Keywords: Universal Algorithms and Machine Learning, Networked Control Systems, Optimization
Abstract: We study the following question: given a graph that represents interactions in a real system, can we group vertices with similar interests together? In many applications, we are often in a setting where vertices may potentially belong to multiple communities. In this paper, we propose an efficient algorithm for overlapping community detection which can successively recover all the communities. We provide theoretical guarantees on the performance of the algorithm by leveraging convex relaxation and exploiting the fact that in many networks there are often vertices that only belong to one community.


13:5014:10, Paper WeC1.2  
Distributed Estimators with Minimal Computation (I) 
Khan, Usman A.  Tufts Univ. 

14:1014:30, Paper WeC1.3  
Distributed Consensus with Mixed Time/communication Bandwidth Performance Metrics (I) 
Rossi, Federico  Department of Aeronautics and Astronautics, Stanford Univ 
Pavone, Marco  Stanford Univ 
Keywords: Decentralized and Distributed Control, MultiAgent Systems and Robot Control, Networked Control Systems
Abstract: In this paper we study the inherent tradeoff between time and communication complexity for the distributed consensus problem. In our model, communication complexity is measured as the maximum data throughput (in bits per second) sent through the network at a given instant. Such a notion of communication complexity, referred to as bandwidth complexity, is related to the frequency bandwidth a designer should collectively allocate to the agents if they were to communicate via a wireless channel, which represents an important constraint for robotic networks. We prove a lower bound on the bandwidth complexity of the consensus problem and provide a matching consensus algorithm that is bandwidthoptimal for a wide class of consensus functions. We then propose a distributed algorithm that can trade communication complexity versus time complexity and robustness as a function of a tunable parameter, which can be adjusted by a system designer as a function of the properties of the wireless communication channel. We rigorously characterize the tunable algorithm's worstcase bandwidth complexity and show that it compares favorably with the bandwidth complexity of wellknown consensus algorithms.


14:3014:50, Paper WeC1.4  
The Role of Information in Multiagent Coordination (I) 
Marden, Jason  Univ. of California, Santa Barbara 

14:5015:10, Paper WeC1.5  
On Graph Controllability Classes (I) 
Aguilar, Cesar  California State Univ. Bakersfield 
Gharesifard, Bahman  Queen's Univ 

15:1015:30, Paper WeC1.6  
A Botnet Detection Game 
Soper, Braden  Univ. of California, Santa Cruz 
Musacchio, John  Univ. of California, Santa Cruz 
Keywords: Network Games and Algorithms, Security and Trust, Intrusion/Anomaly Detection and Diagnosis
Abstract: Botnets continue to constitute a major security threat to users of the internet. We examine a novel security game between a bot master and the legitimate users of the compromised network. The more a bot master utilizes his botnet, the more likely it is he will be detected by the legitimate users of the network. Thus he must balance stealth and aggression in his strategic utilization of the botnet. The legitimate users of the network must decide how vigilant they will be in trying to detect the presence of the botnet infection. We establish the existence of a unique, pure, symmetric Nash equilibrium in a game with homogeneous agents. Network effects are numerically explored in relation to the infectivity of the network.


WeC2 
Solarium 
Statistical Information Processing Systems 
Invited Session 
Chair: Singer, Andrew  Univ. of Illinois 

13:3013:50, Paper WeC2.1  
Computing with 10, 000Bit Words (I) 
Kanerva, Pentti  UC Berkeley 
Keywords: Universal Algorithms and Machine Learning, Biological Information Systems, Stochastic Systems and Control
Abstract: Today's computers compute with numbers and memory pointers that hardly ever exceed 64 bits. With nanotechnology we will soon be able to build computers with 10,000bit words. How would such a computer work and what would it be good for? The paper will describe a 10,000bit architecture that resembles von Neumann's. It has a randomaccess memory (RAM) for 10,000bit words, and an arithmeticlogic unit (ALU) for "adding" and "multiplying" 10,000bit words, in abstract algebra sense. Sets, sequences, lists, and other data structures are encoded "holographically" from their elements using addition and multiplication, and they end up as vectors of the same 10,000dimensional space, which makes recursive composition possible. The theory of computing with highdimensional vectors (e.g. with 10,000bit words) has grown out of attempts to understand the brain's powers of perception and learning in computing terms and is based on the geometry and algebra of highdimensional spaces, dynamical systems, and the statistical law of large numbers. The architecture is suited for statistical learning from data and is used in cognitive modeling and naturallanguage processing where it is referred to by names such as Holographic Reduce Representation, Vector Symbolic Architecture, Random Indexing, Semantic Indexing, Semantic Pointer Architecture Unified Network, and Hyperdimensional Computing.


13:5014:10, Paper WeC2.2  
Carbon Nanotube Digital Systems: ImperfectionImmune Design, Variations, Statistical Error Compensation (I) 
Hills, Gage  Stanford Univ. 
Shulaker, Max  Stanford Univ. 
Chen, HongYu  Stanford Univ. 
Wong, H.S. Philip  Stanford Univ. 
Mitra, Subhasish  Stanford Univ. 

14:1014:30, Paper WeC2.3  
A Framework for Machine Vision Based on NeuroMimetic Front End Processing and Clustering (I) 
Akbas, Emre  Univ. of California Santa Barbara 
Wadhwa, Aseem  Univ. of California, Santa Barbara 
Eckstein, Miguel  Univ. of California Santa Barbara 
Madhow, Upamanyu  Univ. of California Santa Barbara 
Keywords: Image and Multimedia Signal Processing, Detection and Estimation, Biological Information Systems
Abstract: Convolutional deep neural nets have emerged as a highly effective approach for machine vision, but there are a number of open issues regarding training (e.g., a large number of model parameters to be trained, and a number of manually tuned algorithm parameters) and interpretation (e.g., geometric interpretations of neurons at various levels of the hierarchy). In this paper, our goal is to explore alternative convolutional architectures which are easier to interpret and simpler to implement. In particular, we investigate a framework that combines a front end based on the known neuroscientific findings about the visual pathway, together with unsupervised ``universal'' feature extraction based on clustering. Supervised classification, using a generic radial basis function (RBF) support vector machine (SVM), is applied at the end. We obtain competitive classification results on standard image databases, beating the state of the art for NORB (uniformnormalized) and approaching it for MNIST.


14:3014:50, Paper WeC2.4  
Clustering As a Tool for Dissecting and Simplifying Machine Vision? (I) 
Madhow, Upamanyu  Univ. of California, Santa Barbara 

14:5015:10, Paper WeC2.5  
EnergyEfficient Communication and Information Processing in Presence of Noise (I) 
Grover, Pulkit  Carnegie Mellon Univ 

15:1015:30, Paper WeC2.6  
Enabling Hardware Relaxations through Statistical Learning (I) 
Wang, Zhuo  Princeton Univ 
Verma, Naveen  Princeton Univ 
Keywords: Resilient Systems, Universal Algorithms and Machine Learning, VLSI Signal Processing
Abstract: Machinelearning algorithms are playing an increasingly important role in embedded sensing applications, by enabling the analysis of signals derived from physically complex processes. Given the severe resource constraints faced in such applications (energy, functional capacity, reliability, etc.), there is the need to think about how the algorithms can be implemented with very high efficiency. This paper examines the opportunities on three levels: (1) inherent resilience against computational errors, enabling some degree of fault tolerance; (2) topdown training of statistical models using data explicitly affected by errors, enabling substantial fault tolerance; and (3) bottomup specification of inference kernels based on preferred hardware implementation, enabling reduced hardware complexity. Implementations employing the last two approaches are proposed and evaluated through hardware measurements and simulation.


WeC3 
Butternut 
Stochastic Systems and Control 
Regular Session 
Chair: Mahajan, Aditya  McGill Univ 
CoChair: Sojoudi, Somayeh  NYU Langone Medical Center 

13:3013:50, Paper WeC3.1  
Online Scheduling for Energy Efficiency in RealTime Wireless Networks 
Zuo, Shuai  Texas A&M Univ 
Hou, IHong  Texas A&M Univ 
Keywords: Stochastic Systems and Control, Optimization, Queuing Theory and Analysis
Abstract: This paper studies the problem of using minimum power to provide satisfactory performance for realtime applications over unreliable and fading wireless channels. We demonstrate that this problem can be formulated as a linear programming problem. However, this formulation involves exponentially many constraints, and many parameters are either unavailable or difficult to compute, which makes it infeasible to employ standard techniques to solve the linear programming problem. Instead, we propose a simple online scheduling algorithm for this problem. This algorithm has very low complexity and makes scheduling decisions solely based on system history and current channel conditions. It is also compatible with any power control algorithms. We prove that our algorithm provides satisfactory performance to all realtime applications, and the total power consumption can be made arbitrarily close to the theoretical lower bound. Simulation results show that our scheduling algorithm indeed achieves small power consumption with fast convergence.


13:5014:10, Paper WeC3.2  
PrimalDual Algorithms for Discounted Markov Decision Processes 
Cogill, Randy  IBM Res. Ireland 

14:1014:30, Paper WeC3.3  
Average Cost Optimal Threshold Strategies for Remote Estimation with Communication Cost 
Chakravorty, Jhelum  McGill Univ 
Mahajan, Aditya  McGill Univ 
Keywords: Stochastic Systems and Control, Decentralized and Distributed Control, Information Theory
Abstract: In this paper, we consider a remote sensing system that consists of a sensor and an estimator. A sensor observes a first order Markov source and must communicate it to a remote estimator. Communication is noiseless but expensive. At each time, based on the history of its observations and decisions, the sensor chooses whether to transmit or not. If the sensor does not transmit, then the estimator must estimate the Markov process using its past observations. We study the average cost problem in the light of vanishing discount approach. The problem was studied previously by Lipsa and Martins and by Nayyar et al, where it was shown that the optimal estimation policy is Kalmanlike and the optimal communication policy is to communicate when the estimation error is greater than a threshold. In the discounted setup, we had earlier characterized the optimal policy and the optimal thresholds as a function of communication cost. The average cost problem is investigated as the limiting case of the discounted cost problem as the discount factor approaches one. The average cost and the optimal values of the thresholds are provided in terms of the communication cost. Lastly, we present an example of birthdeath Markov chain to illustrate our results.


14:3014:50, Paper WeC3.4  
On the Use of ModelFree Linear Feedback to Trade Stock: Two Open Research Problems 
Malekpour, Shirzad  Univ. of WisconsinMadison 
Barmish, B. Ross  Univ. of Wisconsin 
Keywords: Stochastic Systems and Control, Control Applications, Reliable and Robust Control
Abstract: This paper is part of a new line of research involving the use of a modelfree controller to trade stock. Motivated by robustness considerations, neither modelling nor identification of the stock price dynamics is involved. Instead, a timevarying investment level is generated using a "hardwired" feedback controller which processes states such as the cumulative gains and losses and the stock price. Within this framework, the focus of this paper is rather narrow: Beginning with existing results for the case of linear feedback, we provide a sampling of the type of research conducted in this evolving area by describing two open stock trading problems. We also include appropriate motivation for these problems and some background on stock trading so that the exposition can be followed by the uninitiated reader. As seen in the sequel, in addition to the development of theory characterizing performance of a trading strategy, an integral part of this research effort involves backtesting using historical stock market data.


14:5015:10, Paper WeC3.5  
Study of the Brain Functional Network Using Synthetic Data 
Sojoudi, Somayeh  NYU Langone Medical Center 
Doyle, John  California Inst. of Tech 
Keywords: Control Applications, Optimization, Sparse Data Analysis
Abstract: The brain functional connectivity is usually assessed with the correlation coefficients of certain signals. The partial correlation matrix can reveal direct interactions between brain regions. However, computing this matrix is usually challenging due to the availability of only a limited number of samples. As an alternative, thresholding the sample correlation matrix is a common technique for the identification of the direct interactions. In this work, we investigate the performance of this method in addition to some other wellknown techniques, namely graphical lasso and ChowLiu algorithm. Our analysis is performed on some synthetic data produced by an electrical circuit model with certain structural properties. We show that the simple method of thresholding the correlation matrix and the graphical lasso algorithm would both create false positives and negatives that wrongly imply some network properties such as smallworldness. We also apply these techniques to some restingstate functional MRI (fMRI) data and show that similar observations can be made.


WeC4 
Pine 
Interference Channels 
Regular Session 
CoChair: Avestimehr, Salman  USC 

13:3013:50, Paper WeC4.1  
The Approximate Capacity of Gaussian Z Interfering Multiple Access Channels 
Pang, Yimin  Univ. of Colorado Boulder 
Varanasi, Mahesh  Univ. of Colorado, Boulder 

13:5014:10, Paper WeC4.2  
Feedback through Overhearing 
Chen, Jinyuan  Stanford Univ 
Ozgur, Ayfer  Stanford Univ 
Diggavi, Suhas  Univ. of California, Los Angeles (UCLA) 
Keywords: Information Theory, Wireless Communication Systems, Coding for Wireless Communications
Abstract: In this paper we examine the value of feedback that comes from overhearing, without dedicated feedback resources. We focus on a simple model for this purpose: a deterministic twohop interference channel, where feedback comes from overhearing the forwardlinks. A new aspect brought by this setup is the dualrole of the relay signal. While the relay signal needs to convey the source message to its corresponding destination, it can also provide a feedback signal which can potentially increase the capacity of the first hop. We derive inner and outer bounds on the sum capacity which match for a large range of the parameter values. Our results identify the parameter ranges where overhearing can provide nonnegative capacity gain and can even achieve the performance with dedicatedfeedback resources. The results also provide insights into which transmissions are most useful to overhear.


14:1014:30, Paper WeC4.3  
On the Symmetric KUser Linear Deterministic Interference Channels with Limited Feedback 
Ashraphijuo, Mehdi  Columbia Univ 
Aggarwal, Vaneet  AT&T Shannon Labs 
Wang, Xiaodong  Columbia Univ 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications, Wireless Communication Systems
Abstract: In this paper, we give an achievable scheme for a symmetric Kuser linear deterministic interference channel with a ratelimited feedback from each receiver to its respective transmitter. For this model, the proposed scheme achieves a symmetric rate which is the minimum of symmetric capacity with infinite feedback, and the sum of the symmetric capacity without feedback and the symmetric amount of feedback.


14:3014:50, Paper WeC4.4  
The Capacity of More Capable Cognitive Interference Channels 
Vaezi, Mojtaba  McGill Univ 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications, Coding Techniques and Applications
Abstract: By introducing a new outer bound, we establish the capacity region for a class of discrete memoryless cognitive interference channel (DMCIC) called cognitivemorecapable channel, and we show that superposition coding is the optimal encoding technique. The new capacity region is the largest capacity region for the twouser DMCIC to date, as all existing capacity results are explicitly shown to be its subsets. In the effort to prove the latter, we also clarify the relation among the existing capacity results of the DMCIC. Besides, as a byproduct of the introduced outer bound, we find a more tractable presentation of the outer bound introduced in [1, Theorem 3.2].


14:5015:10, Paper WeC4.5  
Transmitter Cooperation in Interference Channel with Delayed CSIT 
Lashgari, Sina  Cornell Univ 
Avestimehr, Salman  USC 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications
Abstract: In this work we study the impact of transmitter cooperation on interference management in twouser interference channel. In particular, we consider the twouser interference channel with delayed channel state information at the transmitters (delayed CSIT). We first present a model to capture and quantify the amount of cooperation between the transmitters. In this model we denote the fraction of shared messages that are intended for Rx_1, Rx_2 by rho_1,rho_2, respectively, and then, characterize the degrees of freedom (DoF) region as a function of rho_1,rho_2. As a result, the twouser interference channel and twouser multipleinput singleoutput (MISO) broadcast channel become special cases of no cooperation (rho_1=rho_2=0) and full cooperation (rho_1=rho_2=1) in our framework. Moreover, our result indicates that the maximum benefit of cooperation from the DoF perspective is achieved by sharing only half of the messages between the transmitters.


WeC5 
Lower Level 
Privacy and Social Learning 
Invited Session 
Chair: Oh, Sewoong  UIUC 

13:3013:50, Paper WeC5.1  
NearOptimally Teaching the Crowd to Classify (I) 
Karbasi, Amin  Yale Univ 
Adish, Singla  ETH Zurich 
Ilija, Bogunovic  EPFL 
Gabor, Bartok  Google 
Andreas, Krause  ETH Zurich 

13:5014:10, Paper WeC5.2  
The Large Margin Mechanism for Differentially Private Maximization (I) 
Chaudhuri, Kamalika  Univ. of California, San Diego 
Hsu, Daniel  Columbia Univ. 
Song, Shuang  Univ. of California San Diego 

14:1014:30, Paper WeC5.3  
Active Learning from Uncertain Crowd Annotations (I) 
Yan, Yan  Yahoo! Labs 
Rosales, Romer  LinkedIn Corp 
Fung, Glenn  Gfung@cs.wisc.edu 
Dy, Jennifer  Northeastern Univ 
Keywords: Universal Algorithms and Machine Learning, Machine Learning and Approximate Dynamic Programming, Social Networks
Abstract: Supervised learning means there is a teacher providing labels given data samples, and the goal is to predict the labels of unseen instances. In general, these labelers may make mistakes. Typical learning methods rely on an often overlooked assumption that a single expert can provide the required supervision; however, it is becoming more common for supervision to be available in many forms as data can be shared and processed by increasingly larger audiences. This makes it possible for not just one but many labelers to offer some form of supervision (this phenomena is coined as crowdsourcing). Some annotators may be more reliable than others, malicious, or may be correlated with others. Annotator effectiveness may vary depending on the data instance presented. We utilize a probabilistic model for learning a classifier from multiple annotators, where the reliability of the annotators may vary with the annotator and the data that they observe. Although we may have access to many annotators, it is still expensive to label and not all annotators have the same level of expertise. The general problem of intelligently choosing instances for labeling is known as active learning. The crowdsourcing paradigm posits new challenges to active learning  not only are we interested in which sample to label next but also which annotator should be queried to benefit our learning model the most. This paper presents different approaches for performing active learning in the crowdsourcing setting.


14:3014:50, Paper WeC5.4  
Managing Congestion in Dynamic Matching Markets (I) 
Arnosti, Nick  Stanford Univ. 
Johari, Ramesh  Stanford Univ. 
Kanoria, Yashodhan  Stanford Univ. 

14:5015:10, Paper WeC5.5  
Prediction and Privacy for Human Mobility Data (I) 
Kafsi, Mohamed  EPFL 
Grossglauser, Matthias  EPFL 
Thiran, Patrick  EPFL 

WeD1 
Library 
Networks, Games, and Algorithms II 
Invited Session 
Chair: Lu, Yi  Univ. of Illinois at UrbanaChampaign 

15:3015:50, Paper WeD1.1  
Combinatorial Bandits with RewardDependent Feedback (I) 
Laroche, Cyrille  KTH 
Proutiere, Alexandre  KTH 

15:5016:10, Paper WeD1.2  
Botnet Detection Using Social Graph Analysis (I) 
Wang, Jing  Boston Univ 
Paschalidis, Ioannis  Boston Univ 
Keywords: Intrusion/Anomaly Detection and Diagnosis, Social Networks, Optimization
Abstract: Signaturebased botnet detection methods identify botnets by recognizing Command and Control (C&C) traffic and can be ineffective for botnets that use new and sophisticate mechanisms for such communications. To address these limitations, we propose a novel botnet detection method that analyzes the social relationships among nodes. The method consists of two stages: (i) anomaly detection in an ``interaction'' graph among nodes using large deviations results on the degree distribution, and (ii) community detection in a social ``correlation'' graph whose edges connect nodes with highly correlated communications. The latter stage uses a refined modularity measure and formulates the problem as a nonconvex optimization problem for which appropriate relaxation strategies are developed. We apply our method to realworld botnet traffic and compare its performance with other community detection methods. The results show that our approach works effectively and the refined modularity measure improves the detection accuracy.


16:1016:30, Paper WeD1.3  
Optimal Routing in Overlay Networks (I) 
Paschos, Georgios  MIT 
Modiano, Eytan  MIT 
Keywords: Queuing Theory and Analysis, Stochastic Systems and Control, Wireless Communication Systems
Abstract: Maximum throughput requires path diversity enabled by bifurcating traffic at different network nodes. In this work, we consider a network where traffic bifurcation is allowed only at a subset of nodes called routers, while the rest nodes (called forwarders) cannot bifurcate traffic and hence only forward packets on paths. This implements an overlay network of routers where overlay edges correspond to underlay paths. We study dynamic routing implemented at the overlay. We develop a queuebased policy, which is shown to be maximally stable (throughput optimal) for a restricted class of network scenarios which do not require scheduling of packets belonging to different paths. Simulation results show that our policy yields better delay over dynamic policies that allow bifurcation at all nodes, such as the backpressure policy. Additionally, we provide a heuristic extension of our proposed overlay routing scheme for the unrestricted class of networks.


16:3016:50, Paper WeD1.4  
Bayesian Regression and BitCoins (I) 
Shah, Devavrat  MIT 
Zhang, Kang  MIT 
Keywords: Statistical Signal Processing, Sparse Data Analysis, Stochastic Systems and Control
Abstract: In this paper, we discuss the method of Bayesian regression and its efficacy for predicting price variation of Bitcoin, a recently popularized virtual, cryptographic currency. Bayesian regression refers to utilizing empirical data as proxy to perform Bayesian inference. We utilize Bayesian regression for the socalled “latent source model”. The Bayesian regression for “latent source model” was introduced and discussed by Chen, Nikolov and Shah [1] and Bresler, Chen and Shah [2] for the purpose of binary classification. They established theoretical as well as empirical efficacy of the method for the setting of binary classification. In this paper, instead we utilize it for predicting realvalued quantity, the price of Bitcoin. Based on this price prediction method, we devise a simple strategy for trading Bitcoin. The strategy is able to nearly double the investment in less than 60 day period when run against real data trace.


16:5017:10, Paper WeD1.5  
How to Utilize Caching to Improve Spectral Efficiency in DeviceToDevice Wireless Networks (I) 
Naderializadeh, Navid  Univ. of Southern California 
Kao, David  Univ. of Southern California 
Avestimehr, Salman  USC 
Keywords: Information Theoretic Approaches in Wireless Communications, Information Theory, Wireless Communications at Large
Abstract: In this paper, we study the impact of caching on a recentlyproposed spectrum sharing mechanism for devicetodevice networks, ITLinQ, which schedules communication based on informationtheoretic optimality principles. We provide a lower bound on the spectral reuse (the fraction of users simultaneously scheduled in the ITLinQ framework) as a function of the caching redundancy by proposing a greedy algorithm for sourceuser association and determining its achievable reuse. In order to demonstrate that higher spectral reuse also results in more efficient communication, we numerically evaluate the rates achieved by our scheme and show that it provides substantial throughput gain over the stateoftheart.


17:1017:30, Paper WeD1.6  
Community Detection with the NonBacktracking Operator (I) 
Bordenave, Charles  CNRS 
Lelarge, Marc  INRIA  ENS 
Massoulié, Laurent  Tech. 

WeD3 
Butternut 
Index Coding and Security in Distributed Storage 
Invited Session 
Chair: Duursma, Iwan  Univ. of Illinois 

15:3015:50, Paper WeD3.1  
Single Source/Sink Network Error Correction Is As Hard As Multiple Unicast (I) 
Huang, Wentao  California Inst. of Tech 
Ho, Tracey  California Inst. of Tech 
Langberg, Michael  SUNY at Buffalo 
Kliewer, Joerg  New Jersey Inst. of Tech 
Keywords: Network Coding, Reliable and Trustworthy Networks, Security and Trust
Abstract: We study the problem of communicating over a singlesource singleterminal network in the presence of an adversary that may jam a single link of the network. If any one of the edges can be jammed, the capacity of such networks is well understood and follows directly from the connection between the minimum cut and maximum flow in singlesource singleterminal networks. In this work we consider networks in which some edges cannot be jammed, and show that determining the network communication capacity is at least as hard as solving the multipleunicast network coding problem for the errorfree case. The latter problem is a long standing open problem.


15:5016:10, Paper WeD3.2  
New Bounds for Distributed Storage Systems with Secure Repair (I) 
Tandon, Ravi  Virginia Tech 
Mohajer, Soheil  Univ. of Minnesota 
Keywords: Data Storage, Network Coding in Communication, Security and Trust
Abstract: In this paper, we consider exactrepair distributed storage systems. Characterizing the optimal storagevsrepair bandwidth tradeoff for such systems remains an open problem, in general with results available in the literature for very specific instances. We characterize the optimal tradeoff between storage and repair bandwidth if in addition to exactrepair requirements, an additional requirement of pairwise symmetry on the repair process is imposed. The optimal tradeoff surprisingly consists of only one efficient point, namely the minimum bandwidth regenerating (MBR) point. These results are also extended to the case in which the stored data (or repair data) must be secure from an external wiretapper, and the correspondingly optimal secure tradeoffs are also characterized. The main technical tool used in the converse proofs is a use of Han's inequality for subsets of random variables. Finally, we also present results in which the pairwise symmetry constraint is relaxed and a new converse bound is obtained for the case of exact repair in which an external adversary can access the repair data of any one node. This bound improves upon the existing best known results for the secure and exact repair problem.


16:1016:30, Paper WeD3.3  
MultiServer Private Information Retrieval Over Unsynchronized Databases (I) 
Fanti, Giulia  Univ. of CaliforniaBerkeley 
Ramchandran, Kannan  Univ. of CaliforniaBerkeley 
Keywords: Security and Trust
Abstract: Search histories contain detailed and sensitive information about people. Private information retrieval (PIR) aims to hide search histories from service providers by allowing a user to retrieve the wth record of a database without revealing w to the server. However, most known PIR schemes are either very inefficient (and therefore unlikely to gain traction in a practical sense) or reliant on some restrictive assumptions. In this paper, we consider an efficient class of schemes called multiserver PIR. Multiserver PIR assumes that the client communicates with multiple, noncolluding servers, each possessing an identical copy of the database. The current literature does not address the assumption that servers store perfectlysynchronized databases. This seems implausible, especially if servers are not meant to collude. We propose the first multiserver PIR scheme to return the desired record even when servers' databases are not perfectly synchronized. Our scheme asymptotically has the same computational and communication complexity as stateoftheart PIR schemes for synchronized databases; this comes at the expense of probabilistic guarantees of success and two rounds of communication (most existing schemes require only one). As a secondary result, our approach can be used to efficiently process multiple concurrent PIR queries.


16:3016:50, Paper WeD3.4  
On a Weakly Secure Regenerating Code Construction for Minimum Storage Regime (I) 
Kadhe, Swanand  Texas A&M Univ 
Sprintson, Alex  Texas A&M Univ 
Keywords: Network Coding
Abstract: Weakly secure storage codes aim to hide information about individual files as well as small groups of files from an eavesdropper that has access to a limited number of storage nodes. Such codes are a practical alternative to traditional informationtheoretic schemes that hide information about the entire set of files from the eavesdropper. The weakly secure codes do not use random keys, and as a result, provide a higher storage capacity compared to the traditional approach. In this paper, we focus on the design of weakly secure regenerating codes. In particular, we present an explicit construction of a coset coding based outer code to augment a ProductMatrix (PM) regenerating code (proposed by Rashmi et al.) operating at the minimum storage regime. The proposed outer code weakly secures the PM regenerating code against an eavesdropper that can observe any single storage node. More specifically, the outer code hides information about the groups of files whose size is roughly two times more than what can be achieved using only the PM code. Moreover, the proposed scheme requires a small finite field size and can be easily implemented in practical settings.


16:5017:10, Paper WeD3.5  
RepairEfficient Distributed Storage Codes with Heterogeneous Reliability Requirements 
Tian, Chao  The Univ. of Tennessee at Knoxville 
Keywords: Data Storage, Information Theory, Coding Techniques and Applications
Abstract: The digital contents in a large scale distributed storage systems usually have different reliability requirements (e.g., new customer billing records vs. 10yearold office document backup), and for this reason, erasure codes with different strengths should be utilized to achieve the best storage efficiency. On the other hand, in such large scale distributed storage systems, nodes fail on a regular basis, and the contents stored on them need to be regenerated and stored on other healthy nodes, the efficiency of which is an important factor affecting the overall quality of service. In this work, repairefficient data storage codes are considered in systems with heterogeneous reliability requirements. We formulate the problem of multireliability regenerating (MRR) codes and investigate the optimal storage vs. repairbandwidth tradeoff. One key question is whether contents with different reliability requirements need to be "mixed" in the optimal solution, for which we show that such a mixing can strictly improve upon the nonmixing solution.


17:1017:30, Paper WeD3.6  
When and by How Much Can Helper Node Selection Improve Regenerating Codes? 
Ahmad, Imad  Purdue Univ 
Wang, ChihChun  Purdue Univ 
Keywords: Data Storage, Information Theory, Network Coding in Communication
Abstract: Regenerating codes (RCs) can significantly reduce the repair bandwidth of distributed storage networks. Initially, the analysis of RCs was based on the assumption that during the repair process, the newcomer does not distinguish (among all surviving nodes) which nodes to access, i.e., the newcomer is oblivious to the set of helpers being used. Such a scheme is termed the blind repair (BR) scheme. Nonetheless, it is intuitive in practice that the newcomer should access only those "good" helpers. This paper focuses on characterizing the effect of choosing the helper nodes in terms of the storagebandwidth tradeoff. The results fully answer the following fundamental questions: Under what conditions does proactively choosing the helper nodes improve the storagebandwidth tradeoff? Can this improvement be analytically quantified?


WeD4 
Pine 
Trends in Cryptography 
Invited Session 
Chair: Prabhakaran, Manoj  UIUC 

15:3015:50, Paper WeD4.1  
Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits (I) 
Raykova, Mariana  SRI 
Garg, Sanjam  IBM 
Gentry, Craig  IBM 
Halevi, Shai  IBM 
Sahai, Amit  UCLA 
Waters, Brent  UT Austin 

15:5016:10, Paper WeD4.2  
Secure Computation Over Leaky Channels (I) 
Gupta, Divya  UCLA 
Ishai, Yuval  Tech 
Maji, Hemanta  UCLA 
Sahai, Amit  UCLA 
Wullschleger, Jurg  McGill Univ 

16:1016:30, Paper WeD4.3  
Garbled Circuits and Secure TwoParty Computation (I) 
Kamara, Seny  Microsoft Res. Redmond 
Mohassel, Payman  Yahoo Labs 

16:3016:50, Paper WeD4.4  
Key Derivation from Noisy Sources with More Errors Than Entropy (I) 
Canetti, Ran  Boston Univ. and Tel Aviv Univ 
Fuller, Benjamin  Boston Univ 
Paneth, Omer  Boston Univ 
Reyzin, Leonid  Boston Univ 
Smith, Adam  Pennsylvania State Univ 

16:5017:10, Paper WeD4.5  
Lower Bounds on OptimallyFair Coin Tossing, and Other Applications of ImpagliazzoRudich's Eve Algorithm (I) 
DachmanSoled, Dana  Univ. of Maryland 
Malkin, Tal  Columbia Univ. 

17:1017:30, Paper WeD4.6  
Concurrently Secure Computation without Trust Assumptions (I) 
Jain, Abhishek  Johns Hopkins Univ. 

WeD5 
Lower Level 
Dynamics and Control of Decentralized Systems I 
Invited Session 
Chair: Olshevsky, Alexander  Univ. of Illinois at UrbanaChampaign 

15:3015:50, Paper WeD5.1  
Sufficient Statistics for MultiAgent Decision Problems (I) 
Wu, Jeffrey  Stanford Univ 
Lall, Sanjay  Stanford Univ 
Keywords: Decentralized and Distributed Control, Networked Control Systems, Stochastic Systems and Control
Abstract: Motivated by recent work showing the existence of a separation structure for certain classes of decentralized control problems, we define sufficient statistics for multiagent team decision problems. We show that these statistics are sufficient for optimality for these problems, and reduce in the singleplayer case to the wellknown construction based on the posterior distribution. We develop results which allow the explicit construction and updating of teamsufficient statistics, and give examples.


15:5016:10, Paper WeD5.2  
Distributed Coordination for Economic Dispatch with Varying Load and Generator Commitment (I) 
Cherukuri, Ashish  Univ. of California, San Diego 
Cortes, Jorge  Univ. of California San Diego 
Keywords: Decentralized and Distributed Control, Networked Control Systems
Abstract: This paper considers the economic dispatch problem for a group of power generating units. The collective aim is to meet a power demand while respecting individual generator constraints and minimizing the total generation cost. Assuming that the units communicate over a strongly connected, weightbalanced digraph, we propose a distributed coordination algorithm that provably converges to the solution of the dispatch problem starting from any initial power allocation. Additionally, we establish that the proposed strategy is robust against mismatch between load and total generation (and thus able to handle timevarying loads), and against intermittent generation commitment, a plausible scenario due to the integration of renewable energy sources into the grid. Our technical approach uses notions and tools from algebraic graph theory, nonsmooth analysis, setvalued dynamical systems, and dynamic average consensus. Several simulations illustrate our results.


16:1016:30, Paper WeD5.3  
On Graph Controllability Classes (I) 
Aguilar, Cesar  California State Univ. Bakersfield 
Gharesifard, Bahman  Queen's Univ. 

16:3016:50, Paper WeD5.4  
A Distributed Observer for Distributed Control Systems (I) 
Touri, Behrouz  Univ. of Colorado Boulder 
Gharesifard, Bahman  Queen's Univ 

16:5017:10, Paper WeD5.5  
Secure RateLimited Feedback for Control (I) 
Cuff, Paul  Princeton Univ 
Satpathy, Sanket  Princeton Univ 

17:1017:30, Paper WeD5.6  
ContextAdaptive Big Data Stream Mining 
Tekin, Cem  Univ. of California, Los Angeles 
Canzian, Luca  Univ. of Birmingham, UK 
van der Schaar, Mihaela  Univ. of California Los Angeles 
Keywords: Machine Learning and Approximate Dynamic Programming, Statistical Signal Processing, Stochastic Systems and Control
Abstract: Emerging stream mining applications require classification of large data streams generated by single or multiple heterogeneous sources. Different classifiers can be used to produce predictions. However, in many practical scenarios the distribution over data and labels (and hence the accuracies of the classifiers) may be unknown a priori and may change in unpredictable ways over time. We consider data streams that are characterized by their context information which can be used as metadata to choose which classifier should be used to make a specific prediction. Since the context information can be high dimensional, learning the best classifiers to make predictions using contexts suffers from the curse of dimensionality. In this paper, we propose a contextadaptive learning algorithm which learns online what is the best context, learner, and classifier to use to process a data stream. Then, we theoretically bound the regret of the proposed algorithm and show that its time order is independent of the dimension of the context space. Our numerical results illustrate that our algorithm outperforms most prior online learning algorithms, for which such online performance bounds have not been proven.


17:3017:50, Paper WeD5.7  
Randomized Pricing for the Optimal Coordination of Opportunistic Agents (I) 
Dalkilic, Ozgur  The Ohio State Univ 
Eryilmaz, Atilla  Ohio State Univ 
Lin, Xiaojun  Purdue Univ 


WeD6 
Visitor Center 
Coding Theory Topics 
Regular Session 
CoChair: Leith, Douglas  National Univ. of Ireland Maynooth 

15:3015:50, Paper WeD6.1  
Sparse Binary Matrices As Efficient Associative Memories 
Gripon, Vincent  Telecom Bretagne 
Skachek, Vitaly  Univ. of Tartu 
Rabbat, Michael  McGill Univ 
Keywords: Data Storage, Source Coding and Compression, Coding Techniques and Applications
Abstract: Associative memories are widely used devices which can be viewed as universal errorcorrecting decoders. Employing errorcorrecting code principles in these devices has allowed to greatly enhance their performance. In this paper we reintroduce a neuralbased model using the formalism of linear algebra and extend its functionality, originally limited to erasure retrieval, to handle approximate inputs. In order to perform the retrieval, we use an iterative algorithm that provably converges. We then analyze the performance of the associative memory under the asymption of connection independence. We support our theoretical results with numerical simulations.


15:5016:10, Paper WeD6.2  
Coding for Secure WriteEfficient Memories 
Li, Qing  Texas A&M Univ 
Jiang, Anxiao (Andrew)  Texas a M Univ 
Keywords: Data Storage, Information Theory, Security and Trust
Abstract: Endurance and security are two serious challenges for nonvolatile memories such as flash memories. WriteEfficient Memory (WEM) is an important rewriting code model to solve the endurance problem. Aiming at jointly solving the endurance and the security issues in nonvolatile memories, this work focuses on rewriting code with a security constraint. To that end, a novel coding model, secure WEM, is proposed here. We explore its rewritingrateequivocation region and its secrecy rewriting capacity in this paper.


16:1016:30, Paper WeD6.3  
Writing on Dirty Flash Memory 
Kim, Yongjune  Carnegie Mellon Univ 
Kumar, B.V.K. Vijaya  Carnegie Mellon Univ 
Keywords: Data Storage, Coding Techniques and Applications, Coding Theory
Abstract: The most important challenge in the scaling down of flash memory is its increased intercell interference (ICI). If side information about ICI is known to the encoder, the flash memory channel can be viewed as similar to Costa's ``writing on dirty paper (dirty paper coding).'' We first explain why flash memories are dirty due to ICI. We then show that ``dirty flash memory'' can be changed into ``memory with defective cells'' model by using only one preread operation. The asymmetry between write and erase operations in flash memory plays an important role in this change. Based on the ``memory with defective cells'' model, we show that additive encoding can significantly improve the probability of decoding failure by using the side information.


16:3016:50, Paper WeD6.4  
Low Delay Random Linear Coding Over a Stream 
Karzand, Mohammad  National Univ. of Ireland Maynooth 
Leith, Douglas J.  National Univ. of Ireland Maynooth 
Keywords: Coding Techniques and Applications, Coding Theory
Abstract: We introduce a random linear code construction for erasure packet channel. We then analyze its inorder delivery delay behavior. We show that for rates below the capacity, the mean inorderdelivery delay of our scheme is better than the mean delay introduced by the scheme which implements the random linear block coding. We also compute the decoding failure probability and encoding and decoding complexity of our scheme.


16:5017:10, Paper WeD6.5  
Near RealTime Rateless Coding with a Constrained Feedback Budget 
Hashemi, Morteza  Boston Univ 
Trachtenberg, Ari  Boston Univ 
Keywords: Coding Theory, Coding Techniques and Applications
Abstract: We present a near realtime rateless coding approach based on the constrained use of a feedback channel. The specific feedback used in our scheme is based on a measure of distance between a received word and the symbols already decoded at the receiver, with successive feedbacks providing accumulating information about the state of the decoder. Our encoder, in turn, optimizes its choice of constituent source symbols in each encoding according to the decoder information and not uniformly at random as is typically done. We provide an upperbound on the error probability of our approach when used with a maximumlikelihood decoder, and simulation results demonstrate that the coding performance can be tuned according to the feedback budget available.

 