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

FrA1 
Library 
Networks, Games, and Algorithms III 
Invited Session 
Chair: Subramanian, Vijay  Northwestern Univ 

10:0010:20, Paper FrA1.1  
Heavy Tailed Influencers and Stochastic Bounded Confidence Stability (I) 
Baccelli, François  UT Austin 
Chatterjee, Avhishek  UT Austin 
Vishwanath, Sriram  Univ. of Texas at Austin 
Keywords: Social Networks, Stochastic Systems and Control, Performance Analysis
Abstract: In many social networks, whether two agents incorporate each other's opinion or not depends on the proximity of their opinions. The bounded confidence model of opinion dynamics captures this by introducing a parameter called the influence range and by stating than an agent incorporates the opinion of another agent if the distance between their opinions is less than the influence range. We generalize the bounded confidence opinion dynamics model by allowing a stochastic influence range that varies across time and agents, and by incorporating the effect an additive noise on the update rule. We establish the conditions under which this stochastic dynamics is stable in an appropriate sense. Our main observation is that the the presence of heavy tailed influence ranges is critical for stability.


10:2010:40, Paper FrA1.2  
StoreForward and Its Implications for Proportional Scheduling (I) 
Walton, Neil Stuart  Univ. of Amsterdam 
Keywords: Queuing Theory and Analysis, Performance Analysis
Abstract: The Proportional Scheduler was recently proposed as a scheduling algorithm for multihop switch networks. For these networks, the BackPressure scheduler is the classical benchmark.For networks with fixed routing, the Proportional Scheduler is maximum stable, myopic and, furthermore, will alleviate certain scaling issued found in BackPressure for large networks. Nonetheless, the equilibrium and delay properties of the Proportional Scheduler has not been fully characterized. In this article, we postulate on the equilibrium behaviour of the Proportional Scheduler though the analysis of an analogous rule called the StoreForward allocation. It has been shown that StoreForward has asymptotically allocates according to the Proportional Scheduler. Further, for StoreForward networks, numerous equilibrium quantities are explicitly calculable. For FIFO networks under StoreForward, we calculate the policies stationary distribution and endtoend route delay. We discuss network topologies when the stationary distribution is productform, a phenomenon which we call emph{product form resource pooling}. We extend this product form notion to independent set scheduling on perfect graphs, where we show that nonneighbouring queues are statistically independent. Finally, we analyse the large deviations behaviour of the equilibrium distribution of StoreForward networks in order to construct Lyapunov functions for FIFO switch networks.


10:4011:00, Paper FrA1.3  
MultiParty Set Reconciliation Using Characteristic Polynomials (I) 
Mitzenmacher, Michael  Harvard Univ 
Boral, Anudhyan  Harvard Univ 
Keywords: Distributed Computation on Networks, Network Coding in Communication, Coding Theory
Abstract: In the standard set reconciliation problem, there are two parties A_1 and A_2, each respectively holding a set of elements S_1 and S_2. The goal is for both parties to obtain the union S_1 cup S_2. In many distributed computing settings the sets may be large but the set difference S_1S_2+S_2S_1 is small. In these cases one aims to achieve reconciliation efficiently in terms of communication; ideally, the communication should depend on the size of the set difference, and not on the size of the sets. Recent work has considered generalizations of the reconciliation problem to multiparty settings, using a framework based on a specific type of linear sketch called an Invertible Bloom Lookup Table. Here, we consider multiparty set reconciliation using the alternative framework of characteristic polynomials, which have previously been used for efficient pairwise set reconciliation protocols, and compare their performance with Invertible Bloom Lookup Tables for these problems.


11:0011:20, Paper FrA1.4  
Highly Compact Virtual Maximum Likelihood Sketches for Counting Big Network Data (I) 
Mo, Zhen  Univ. of Florida 
Qiao, Yan  Univ. of Florida 
Chen, Shigang  Univ. of Florida 
Li, Tao  Univ. of Science and Tech. of China 
Keywords: Performance Analysis, Distributed Computation on Networks
Abstract: As the Internet moves into the era of big network data, it presents both opportunities and technical challenges for traffic measurement functions, such as flow cardinality estimation, which is to estimate the number of distinct elements in each flow. Cardinality estimation has important applications in intrusion detection, resource management, billing and capacity planning, as well as big data analytics. Due to the practical need of processing network data in high volume and high speed, past research has strived to reduce the memory overhead for cardinality estimation on a large number of flows. One important thread of research in this area is based on sketches. The representative work includes the FM sketches, the LogLog sketches, and the HyperLogLog sketches. Each sketch requires multiple bits and many sketches are needed for each flow, which results in significant memory overhead. This paper proposes a new method of virtual maximum likelihood sketches to reduce memory consumption. First, we design virtual sketches that use no more than two bits per sketch on average. Second, we design virtual sketch vectors that consider all flows together. Based on these new constructs, we design a flow cardinality solution with an online operation module and an offline estimation module. We also consider the problem of differentiated estimation that gives flows of high priorities better precision in their cardinality estimations. We implement the new solution and perform experiments to evaluate its performance based on real traffic traces.


11:2011:40, Paper FrA1.5  
Scheduling Tasks with Precedence Constraints on Multiple Servers (I) 
Pedarsani, Ramtin  UC Berkeley 
Zhong, Yuan  Columbia Univ 
Walrand, Jean  Univ. of California, Berkeley 
Keywords: Distributed Computation on Networks, Queuing Theory and Analysis, Performance Analysis
Abstract: We consider the problem of scheduling jobs which are modeled by directed acyclic graphs (DAG). In such graphs, nodes represent tasks of a job and edges represent precedence constraints in processing these tasks. The DAG scheduling problem, also known as scheduling in forkjoin processing networks, is motivated by examples such as job scheduling in data centers and cloud computing, patient flow scheduling in health systems and many other applications. We consider a flexible system, in which servers may process different, possibly overlapping, sets of task types. In this paper, we first discuss the difficulties in designing provably efficient policies for DAG scheduling, which arise due to interactions between the flexibility of the processing environment and the precedence constraints in the system. A major difficulty is the classical synchronization issue, which is further complicated in the presence of system flexibility. Then, we propose two queueing networks to model the scheduling problem that overcome this difficulty. These are virtual queues that enable us to design provably efficient scheduling policies. We show that the wellknown MaxWeight policy for these queueing networks is throughputoptimal. Finally, to compare the delay performance of the two queueing networks, we consider a simplified model in which tasks and servers are identical. We characterize their delay performances under a simple firstcomefirstserve policy, via a novel coupling argument.


11:4012:00, Paper FrA1.6  
BATS: Network Coding in Action (I) 
Yang, Shenghao  Tsinghua Univ 
Yeung, Raymond W.  The Chinese Univ. of Hong Kong 
Cheung, Jay H.F.  The Chinese Univ. of Hong Kong 
Yin, Hoover H.F.  The Chinese Univ. of Hong Kong 
Keywords: Networks, Games, and Algorithms
Abstract: BATS code is a lowcomplexity random linear network coding scheme that can achieve asymptotic bandwidth optimality for many types of networks with packet loss. In this paper, we propose a BATS code based network protocol and evaluate the performance by realdevice experiments. Our re sults demonstrate significant readytoimplement gain of network coding over forwarding in multihop network transmission with packet loss. We also propose an improved protocol to handle the practical issues observed in the experiments.


FrA2 
Solarium 
Statistics and Learning for HighDimensional Data 
Invited Session 
Chair: Montanari, Andrea  Stanford Univ 
CoChair: Raginsky, Maxim  Univ. of Illinois at UrbanaChampaign 

10:0010:20, Paper FrA2.1  
Practical Approximate Projection Schemes in Greedy Signal Space Methods (I) 
Needell, Deanna  Claremont McKenna Coll 
Garnatz, Chris  Pomona Coll 
Gu, Xiaoyi  UCLA 
Kingman, Alison  Harvey Mudd Coll 
LaManna, James  Pitzer Coll 
Tu, Shenyinying  UCLA 
Keywords: Sparse Data Analysis, Statistical Signal Processing, Optimization
Abstract: Compressive sensing (CS) is a new signal acquisition paradigm which shows that far fewer samples are required to reconstruct sparse signals than previously thought. Although most of the literature focuses on signals sparse in a fixed orthonormal basis, recently the Signal Space CoSaMP (SSCoSaMP) greedy method was developed for the reconstruction of signals compressible in arbitrary redundant dictionaries. The algorithm itself needs access to approximate sparse projection schemes, which have been difficult to obtain and analyze. This paper investigates the use of several different projection schemes and catalogs for what types of signals each scheme can successfully be utilized. In addition, we present novel hybrid projection methods which outperform all other schemes on a wide variety of signal classes.


10:2010:40, Paper FrA2.2  
Lower Bounds on the Bayes Risk and Minimax Risk (I) 
Chen, Xi  New York Univ. 
Guntuboyina, Adityanand  Univ. of California, Berkeley 
Zhang, Yuchen  UC Berkeley 

10:4011:00, Paper FrA2.3  
Stochastic Optimization and Sparse Statistical Recovery: An Optimal Algorithm for High Dimensions (I) 
Agarwal, Alekh  Univ. of California, Berkeley 
Negahban, Sahand  Yale Univ. 
Wainwright, Martin  UC Berkeley 

11:0011:20, Paper FrA2.4  
Hypercontractivity in Hamming Space (I) 
Polyanskiy, Yury  MIT 

11:2011:40, Paper FrA2.5  
Principal Component Analysis with Structured Factors (I) 
Montanari, Andrea  Stanford Univ. 

FrA3 
Butternut 
Information Theory and Practice 
Regular Session 
Chair: Zheng, Lizhong  MIT 

10:0010:20, Paper FrA3.1  
Joint Estimation and Detection against Independence 
Katz, Gil  Supelec 
Piantanida, Pablo  Supelec 
Couillet, Romain  Supelec 
Debbah, Merouane  Supelec 
Keywords: Multiuser Detection and Estimation, Information Theory, Detection and Estimation
Abstract: A receiver in a twonode system is required to make a decision of relevance as to received information, using side information that may or may not be correlated with the received signal. In case the information is judged to be relevant, the receiver is then required to estimate the source with average distortion D. Focusing on the case of testing against independence, a singleletter expression for the rateerrordistortion region is proposed and proven. The resulting region ports a surprising resemblance to a seemingly nonassociated classification problem, known as the informationbottleneck. The optimal region is then calculated for a binary symmetric example. Results demonstrate an interesting tradeoff between the achievable errorexponent for the decision and the distortion at the decoder.


10:2010:40, Paper FrA3.2  
Uniformly Reweighted APP Decoder for Memory Efficient Decoding of LDPC Codes 
Ilic, Velimir  Univ. of Arizona 
Dupraz, Elsa  ENSEA / Univ. Cergy Pontoise / CNRS 
Declercq, David  Etis Ensea/ucp/cnrs 
Vasic, Bane  Univ. of Arizona 
Keywords: Coding Techniques and Applications, Coding Theory, Coding for Wireless Communications
Abstract: In this paper we propose a uniformly reweighted a posteriori probability (APP) decoder. It is derived as an algorithm of approximate Bayesian inference on the LDPC code graph, and a correction parameter is introduced and numerically optimized to overcome the suboptimaly of the decoder and improve performance compared to the original APP decoder. In addition, we propose a memory efficient implementation of the algorithm that requires memory that is linear only in the codeword length.


10:4011:00, Paper FrA3.3  
Communicating Lists Over a Noisy Channel 
Kocak, Mustafa Anil  NYU Pol. School of Engineering 
Erkip, Elza  Pol. Univ 
Keywords: Information Theory
Abstract: This work considers a communication scenario where the transmitter chooses a list of size K from a total of M messages to send over a noisy communication channel, the receiver generates a list of size L and communication is considered successful if the intersection of the lists at two terminals has a cardinality greater than a threshold T. In traditional communication systems K = L = T = 1. The fundamental limits of this communication scenario in terms of K, L, T and the Shannon capacity of the channel between the terminals are examined. Specifically, necessary and/or sufficient conditions for asymptotically error free communication are provided.


11:0011:20, Paper FrA3.4  
Fast NearOptimal Subnetwork Selection in Layered Relay Networks 
Kolte, Ritesh  Stanford Univ 
Ozgur, Ayfer  Stanford Univ 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications
Abstract: We consider the problem of finding the largest capacity subnetwork of a given size of a layered Gaussian relay network. While the exact capacity of Gaussian relay networks is unknown in general, motivated by recent capacity approximations we use the informationtheoretic cutset bound as a proxy for the true capacity of such networks. There are two challenges in efficiently selecting subnetworks of a Gaussian network. First, evaluating the cutset bound involves a minimization of a cut function over the exponentially many possible cuts of the network and therefore a greedy approach has exponential complexity. Second, even if the mincut for each subnetwork can be evaluated efficiently, an exhaustive search over the possibly exponentially many subnetworks of a network has prohibitive complexity. Algorithms exploiting the submodularity property of the cut function have been proposed in the literature to address these challenges. Instead, in this paper, we develop algorithms for computing the mincut of a layered network and selecting its largest capacity subnetwork which are based on the observation that the cut function of a layered network admits a linestructured factor graph representation. We demonstrate numerically that our algorithms exploiting the layered structure can be significantly more efficient than the earlier algorithms exploiting submodularity.


11:2011:40, Paper FrA3.5  
Distributed Testing against Independence with Multiple Terminals 
Zhao, Wenwen  Worcester Pol. Inst 
Lai, Lifeng  Worcester Pol. Inst 
Keywords: Information Theory, Multiuser Detection and Estimation
Abstract: Motivated by distributed learning with big data sets problems, we study a distributed testing against independence problem with multiple terminals. We connect the problem at hand to a source coding with multiple helpers problem, which is open in general. We fully characterize the rate region of the source coding with multiple helpers problem under a certain Markovian condition. Using this rate region characterization, we obtain a singleletter characterization of the optimal error exponent for the type 2 error probability under the type 1 error probability and communication rates constraints.


11:4012:00, Paper FrA3.6  
Degrees of Freedom in Fading Channels with Memory: Achievability through Nonlinear Decoding 
Karzand, Mina  Massachusetts Inst. of Tech 
Zheng, Lizhong  MIT 
Keywords: Information Theory, MIMO Systems, Coding for Wireless Communications
Abstract: In noncoherent communication systems, neither the transmitter nor the receiver knows the realization of channel fading coefficients. To overcome this limitation and facilitate reliable communication, the transmitter sends fixed values on some predetermined training symbols. The maximum number of symbols that can be used for communication in a block of time is the degrees of freedom (DOF) of the system. Given DOF equals to D, reliable communication implies existence of a D dimensional subspace of the input signal space which is recoverable by the receiver with probability one. The training symbols specify this D dimensional subspace. Thus the minimum number of necessary training symbols determines the DOF of the system. We formalize this rationale and name it Dimension Counting Argument. We then use this argument to prove a lower bound on the DOF of fading channels with memory. We study the MultipleInput MultipleOutput systems with n_t transmit antennas and n_r receive antennas where fading coefficients in blocks of length T have a temporal correlation matrix with rank Q. We prove that in these systems, N transmit antennas (N=min[n_t,lfloor(T/Q)rfloor]) should be used to achieve min[n_r(T N Q),N(TN)] DOF per block of time. We show that the geometric interpretation of such systems is equivalent to a nonlinear mapping over manifolds of different dimensions. The inherent nonlinearity of the model manifests itself in the nonlinearity of the proposed decoding algorithms.


12:0012:20, Paper FrA3.7  
The DoF of the Asymmetric MIMO Interference Channel with Square Direct Link Channel Matrices 
Liu, Tang  Univ. of Illinois at Chicago 
Tuninetti, Daniela  Univ. of Illinois at Chicago 
Jafar, Syed  Univ. of California Irvine 
Keywords: Information Theoretic Approaches in Wireless Communications, MIMO Systems, Information Theory
Abstract: This paper studies the sum Degrees of Freedom (DoF) of Kuser asymmetric MIMO Interference Channel (IC) with square direct link channel matrices, that is, the uth transmitter and its intended receiver have M_uinmathbb{N} antennas each, where M_u need not be the same for all uin[1:K]. Starting from a 3user example, it is shown that existing cooperationbased outer bounds are insufficient to characterize the DoF. Moreover, it is shown that two distinct operating regimes exist. With a dominant user, i.e., a user that has more antennas than the other two users combined, it is DoF optimal to let that user transmit alone on the IC. Otherwise, it is DoF optimal to decompose and operate the 3user MIMO IC as an (M_1+M_2+M_3)user SISO IC. This indicates that MIMO operations are useless from a DoF perspective in systems without a dominant user. The main contribution of the paper is the derivation of a novel outer bound for the general Kuser case that is tight in the regime where a dominant user is not present; this is done by generalizing the insights from the 3user example to an arbitrary number of users.


FrA4 
Pine 
Security, Privacy, and Integrity 
Regular Session 
Chair: Zhao, Jun  Carnegie Mellon Univ 

10:0010:20, Paper FrA4.1  
Information Integrity in Lossy Source Coding with Side Information 
Graves, Eric  Army Res. Lab 
Wong, Tan F  Univ. of Florida 
Keywords: Intrusion/Anomaly Detection and Diagnosis, Information Theory, Security and Trust
Abstract: In this paper we investigate how to achieve information integrity in two common models of source coding with side information. We first look at the classical WynerZiv problem, where the side information is available only to the decoder, with an adversary whom may arbitrarily change the ``bin'' index sent to the decoder. Interestingly, it is easy to show that standard WynerZiv coding suffices to guarantee no adversary attack strategy may achieve arbitrarily small probability of fooling the decoder if the side information is correlated with the source. Subsequently, we consider the case where the side information is available also at the encoder, and hence joint source encoding can be performed. Here we show the result of WynerZiv problem also extends to joint encoding without needing the side information to be correlated with the source. Moreover, no loss in the optimal compression rates is incurred to guarantee information integrity in both cases.


10:2010:40, Paper FrA4.2  
Notes on InformationTheoretic Privacy 
Asoodeh, Shahab  Queen's Univ 
Alajaji, Fady  Queen's Univ 
Linder, Tamas  Queen's Univ 
Keywords: Information Theory
Abstract: We investigate the tradeoff between privacy and utility in a situation where both privacy and utility are measured in terms of mutual information. For the binary case, we fully characterize this tradeoff in case of emph{perfect privacy} and also give an upperbound for the case where some privacy leakage is allowed. We then introduce a new quantity which quantifies the amount of private information contained in the observable data and then connect it to the optimal tradeoff between privacy and utility.


10:4011:00, Paper FrA4.3  
The Privacy/security Tradeoff across Jointly Designed Linear Authentication Systems 
Goldberg, Adina  Univ. of Toronto 
Draper, Stark  Univ. of Toronto 
Keywords: Coding Theory, Information Theory, Security and Trust
Abstract: In the area of secure biometrics, work has been done to build an information theoretic framework characterizing privacy and security of single biometric systems. People have worked extensively on designing such systems, some cryptographic in nature, and others tied to error correcting codes. However, there is still little known about security and privacy across multiple jointly designed systems. This work will focus on the privacy/security tradeoff across multiple "secure sketch" biometric systems. Secure sketch is a type of biometric system architecture related to errorcorrecting codes where a system is characterized by a paritycheck matrix over a finite field, or equivalently by a subspace of a vector space over that same field. Given a set of systems (a design), we introduce worstcase measures of privacy leakage and security in the case that a subset of the systems becomes compromised. It turns out that more secure designs are necessarily less private and vice versa. We study the tradeoff between privacy and security by relaxing a restricted version of the problem, by studying the algebraic structure of the problem, and by formulating graph theoretic questions. These approaches generate bounds on achievable privacy/security pairs.


11:0011:20, Paper FrA4.4  
Two ShannonType Problems on Secure MultiParty Computations 
Lee, Eun Jee  Princeton Univ 
Abbe, Emmanuel  Princeton Univ 
Keywords: Information Theory, Coding Theory
Abstract: In secure multiparty computations (SMC), parties wish to compute a function on their private data without revealing more information about their data than what the function reveals. In this paper, we investigate two Shannontype questions on this problem. We first consider the traditional oneshot model for SMC which does not assume a probabilistic prior on the data. In this model, private communication and randomness are the key enablers to secure computing, and we investigate a notion of randomness cost and capacity. We then move to a probabilistic model for the data, and propose a Shannon model for discrete memoryless SMC. In this model, correlations among data are the key enablers for secure computing, and we investigate a notion of dependency which permits the secure computation of a function. While the models and questions are general, this paper focuses on summation functions and relies on polar code constructions.


11:2011:40, Paper FrA4.5  
Connectivity in Secure Wireless Sensor Networks under Transmission Constraints 
Zhao, Jun  Carnegie Mellon Univ 
Yagan, Osman  Carnegie Mellon Univ 
Gligor, Virgil  Carnegie Mellon Univ 
Keywords: Sensor Networks in Communications, Security and Trust, Sensor Networks
Abstract: In wireless sensor networks (WSNs), the EschenauerGligor (EG) key predistribution scheme is a widely recognized way to secure communications. Although connectivity properties of secure WSNs with the EG scheme have been extensively investigated, few results address physical transmission constraints. These constraints reflect realworld implementations of WSNs in which two sensors have to be within a certain distance from each other to communicate. In this paper, we present zeroone laws for connectivity in WSNs employing the EG scheme under transmission constraints. These laws help specify the critical transmission ranges for connectivity. Our analytical findings are confirmed via numerical experiments. In addition to secure WSNs, our theoretical results are also applied to frequency hopping in wireless networks.


11:4012:00, Paper FrA4.6  
Information Leakage for Correlated Sources with Compromised Source Symbols Over Wiretap Channel II 
Balmahoon, Reevana  Univ. of the Witwatersrand 
Cheng, Ling  Univ. of the Witwatersrand 
Vinck, A.J Han  DuisburgEssen Univ 
Keywords: Source Coding and Compression, Information Theory, Security and Trust
Abstract: Correlated sources are present in communication systems where protocols ensure that there is some predetermined information for sources. Here, we investigate two correlated sources across the wiretap channel II and their effect on the information leakage when some channel information and some source data symbols (the predetermined information) have been wiretapped. The adversary in this situation has access to more information than if a link is wiretapped only and can thus determine more about a particular source. We show that since the sources are correlated, if the information on one link and a portion of its data symbols are compromised then there is also information leakage for the other source. Further, we describe a method to reduce the information leakage for the scenario where the information from the source data symbols overlaps with the channel information.


FrA5 
Lower Level 
Coding for Networks 
Regular Session 
Chair: Kiah, Han Mao  Univ. of Illinois at Urbana Champaign 

10:0010:20, Paper FrA5.1  
TwoWay Function Computation 
Shin, Seiyun  KAIST 
Suh, Changho  KAIST 
Keywords: Network Coding
Abstract: We explore the role of feedback for the problem of reliable computation over twoway multicast networks. Specifically we consider a scenario in which there are forwardmessage computation demands and feedback is offered through the backward network for aiding the forwardmessage computation. We characterize the feedback computation capacity of a fournode AvestimehrDiggaviTse deterministic network in which two nodes in one side wish to compute modulo2 sums of two independent Bernoulli sources generated from the other two nodes. As a consequence of this result, we show that the backward network can be more efficiently used for feedback, rather than if it were used for independent backwardmessage computation. Our achievability proof builds upon a network decomposition framework developed in our earlier work.


10:2010:40, Paper FrA5.2  
Efficient Pooling against Strategic Adversary with Applications in Anonymous and Reliable Networking 
Heidarzadeh, Anoosheh  California Inst. of Tech 
Zhao, Shiyu  California Inst. of Tech 
Ho, Tracey  California Inst. of Tech 
Effros, Michelle  California Inst. of Tech 
Keywords: Network Coding in Communication, Network Coding, Network Games and Algorithms
Abstract: In many anonymous peerbased networking schemes, it is difficult to identify adversarial participants who drop or corrupt packets they are supposed to forward. This paper considers a pooling problem which models the strategic interaction between an adversary and a sender who chooses relay nodes from a pool of participants, a subset of which is controlled by the adversary. The sender adaptively chooses sets of relay nodes over a number of rounds, while the adversary chooses whether or not to attack in rounds where adversarial nodes are chosen. We introduce a class of strategies, called random pooling strategies, over which it is tractable to optimize and whose performance is within a factor of 1.4 of the optimal strategy when the number of adversaries is given.


10:4011:00, Paper FrA5.3  
Multiuser Broadcast Erasure Channel with Feedback and Side Information, and Related Index Coding Results 
Papadopoulos, Athanasios  Univ. of California, Los Angeles 
Georgiadis, Leonidas  Aristotle Univ. of Thessaloniki 
Keywords: Information Theory, Network Coding in Communication, Coding Theory
Abstract: Abstract In this paper we consider the Nuser broadcast erasure channel with public feedback and side information. Before the beginning of transmission, each receiver knows a function of the messages of some of the other receivers. This situation arises naturally in wireless and in particular cognitive networks where a node may overhear transmitted messages destined to other nodes before transmission over a given broadcast channel begins. We provide an upper bound to the capacity region of this system. When the side information is linear, this bound is tight for the case of twouser broadcast channels. The special case where each user knows the whole or nothing of the message of each other node, constitutes a generalization of the index coding problem. For this instance, and when there are no channel errors, we show that the bound reduces to the known Maximum Weighted Acyclic Induced Subgraph bound. We also show how to convert the capacity upper bound to transmission completion rate (broadcast rate) lower bound and provide examples of codes for certain information graphs for which the bound is either achieved of closely approximated.


11:0011:20, Paper FrA5.4  
Network Embedding Operations Preserving the Insufficiency of Linear Network Codes 
Li, Congduan  Drexel Univ 
Weber, Steven  Drexel Univ. Dept. of Ec 
Walsh, John MacLaren  Drexel Univ 
Keywords: Network Coding, Information Theory, Data Storage
Abstract: In this paper, preservation of insufficiency of linear codes, when extending a network, is investigated. Linear codes over some finite field suffice for a network if and only if for every point in the rate region, there exists a code over that finite field to achieve it. Three operations on a network, that can obtain embedded network, are defined under which the sufficiency of linear codes over a finite field is preserved. Equivalently, insufficiency of linear codes over that finite field is also preserved under the reverse of the operations. Notions of vector linear codes and scalar linear codes are introduced. It is shown that the preservation holds for both vector and scalar linear codes. Experimental results on the rate regions of multilevel diversity coding systems (MDCS), a subclass of the broader family of multisource multisink networks with special structure, are presented for demonstration.


11:2011:40, Paper FrA5.5  
Secret Message Capacity of a Line Network 
Papadopoulos, Athanasios  Univ. of California, Los Angeles 
Czap, Laszlo  EPFL 
Fragouli, Christina  Ucla, Epfl 
Keywords: Information Theory, Network Coding in Communication, Coding Theory
Abstract: We investigate the problem of information theoretically secure communication in a line network with erasure channels and state feedback. We consider a spectrum of cases for the private randomness that intermediate nodes can generate, ranging from having intermediate nodes generate unlimited private randomness, to having intermediate nodes generate no private randomness, and all cases in between. We characterize the secret message capacity when either only one of the channels is eavesdropped or all of the channels are eavesdropped, and we develop polynomial time algorithms that achieve these capacities. We also give an outer bound for the case where an arbitrary number of channels is eavesdropped. Our work is the first to characterize the secrecy capacity of a network of arbitrary size, with imperfect channels and feedback.


11:4012:00, Paper FrA5.6  
Efficient InterpolationBased Decoding of Interleaved Subspace and Gabidulin Codes 
Bartz, Hannes  Tech. Univ. München 
WachterZeh, Antonia  Tech. Israel Inst. of Tech 
Keywords: Coding Theory, Network Coding in Communication, Network Coding
Abstract: An interpolationbased decoding scheme for interleaved subspace codes is presented. This principle can be used as a (not necessarily polynomialtime) list decoder as well as a probabilistic unique decoder. Both interpretations allow to decode interleaved subspace codes beyond half the minimum subspace distance. Further, an efficient interpolation procedure for the required linearized multivariate polynomials is presented and a computationally and memory efficient rootfinding algorithm for the probabilistic unique decoder is proposed. These two efficient algorithms can also be applied for accelerating the decoding of interleaved Gabidulin codes.


FrA6 
Visitor Center 
Complementary and Quantam Codes 
Regular Session 
Chair: Klappenecker, Andreas  Texas A&M Univ 

10:0010:20, Paper FrA6.1  
RowCorrelation Function: A New Approach to Complementary Code Matrices 
Coxson, Greg  Coxson Associates 
Logan, Brooke  Rowan Univ 
Nguyen, Hieu  Rowan Univ 
Keywords: Information Theory, Detection and Estimation
Abstract: New tools are developed for testing Complementary Code Matrix (CCM) existence, first for binary CCMs and then for more general pphase classes, by formulating a CCM in terms of its rowcorrelation function. It is shown that a result of Lam and Leung on vanishing sums of roots of unity is useful in this approach for developing pphase CCM existence tests in terms of the prime factorization of p. In addition, other existence tests and properties are found by using the rowcorrelation function to derive new dot product and congruence relations between rows of a CCM.


10:2010:40, Paper FrA6.2  
EntanglementAssisted Quantum Error Correcting Codes Over Nice Rings 
Lee, Sangjun  Texas A&M Univ 
Klappenecker, Andreas  Texas A&M Univ 
Keywords: Coding Theory
Abstract: Entanglementassisted quantum error correcting codes have the nice feature that they can be constructed from classical additive codes that do not need to be selforthogonal an advantage over stabilizer codes. In the literature, these codes were investigated for finite fields, mostly binary fields. A generalization of the Pauli basis to nice error bases indexed by rings allows one to consider alphabet sizes that are not restricted to powers of a prime. The main goal of this paper is to show how entanglementassisted quantum error correcting codes over nice rings can be constructed. We develop the rudiments of symplectic geometry over rings and prove that an Rmodule with antisymmetric bicharacter can be decomposed as an orthogonal direct sum of hyperbolic pairs.


10:4011:00, Paper FrA6.3  
Quantum Communication Over Bit Flip Channels Using Entangled Bipartite and Tripartite States 
Raina, Ankur  Indian Inst. of Science, Bangalore 
Garani Srinivasa, Shayan  Indian Inst. of Science, Bangalore 
Keywords: Information Theory
Abstract: Super dense coding is a well known protocol to communicate two classical bits using a preshared pair of entangled qubits. We consider the case of quantum communication over the noisy bit flip channel with a shared Bell pair and show that the encoding scheme is perfectly secure. We extend the idea of super dense coding to a tripartite system and derive expressions for Holevo capacity and accessible information for various communication scenarios among the node links.


11:0011:20, Paper FrA6.4  
Quantum Codes Over Rings and Quadratic Algebras 
Sarma, Anurupa  Intel Corp 
Klappenecker, Andreas  Texas A&M Univ 
Keywords: Coding Theory
Abstract: Stabilizer and subsystem code constructions can be used to derive quantum codes from classical codes over rings. One drawback is that the distance properties of the classical codes are not based on the Hamming distance, so one cannot easily leverage classical code constructions. It is shown that socalled unramified quadratic algebras can remedy the situation by allowing one to use the Hamming distance. Furthermore, a new proof is given of the fact that nice rings (the rings supporting the construction of quantum codes) are finite Frobenius rings.

 