# ISIT 2016 Barcelona: Monday

I went to ISIT 2016 in Barcelona this year and have decided to write a few posts on some of the talks and papers I saw there. ISIT is a very big conference,  and I got to see great work on a variety of topics. Here’s a brief sketch of what I saw on Monday:

After listening to the plenary by Elza Erkip on co-operation in wireless networks, I attended a talk on low rank matrix completion over $\mathbb{F}_2$ by Saunderson, Fazel and Hassibi. The setup is the following: Let $A$ be an $n\times n$ matrix with entries from $\mathbb{F}_2$ having rank $k\ll n$. You observe a subset of its entries, and the objective is to complete the rest of the matrix. Interestingly, this problem has connections to network and index coding, and finding optimal linear codes for these problems can be reduced to a low-rank matrix completion problem. The solution is NP hard, so they proposed an LP relaxation using ideas of Feldman (LP decoding of binary linear codes). They also gave some meta-algorithms with some theoretical guarantees, but I guess that the complexity is high. They don’t seem to have any guarantees on the LP relaxation, but it seems to do well empirically.

There was also some recent work on integer forcing source coding by  He and Nazer. Integer forcing is a technique that was developed for MIMO channels, where instead of decoding all the messages directly, you decode sufficiently many integer-linear combinations of the messages and subsequently compute the individual messages. This is inspired by the compute-and-forward technique of Nazer and Gastpar. The integer forcing idea was used for source coding by Ordentlich and Erez, and He and Nazer gave a successive cancellation generalization this ISIT. They also showed a duality between the successive integer-forcing distributed source coding for Gaussian sources and successive integer-forcing channel coding for the Gaussian MAC.

There was also some interesting work on near-optimal finite length scaling for nonbinary polar codes by Pfister and Urbanke, that I unfortunately missed. They consider $q$-ary polar codes for prime powers $q$ constructed from Reed-Solomon polarization kernels, a problem initially studied by Mori and Tanaka. Pfister and Urbanke study the finite-length  scaling over $q$-ary erasure channel with erasure probability $\epsilon$. They showed that (for a fixed $\gamma,\delta>0$) for all sufficiently large $q$, the fraction of “good” channels, or channels with erasure rate at most $N^{-\gamma}$  is at least $1-\epsilon -O(N^{\delta -1/2})$.

I also attended Oron’s talk (work with Permuter and Pfister) that talked about an upper bound on the feedback capacity of certain channels with state. He talked about unifilar finite-state channels, i.e., finite-state channels where the current state is a time-invariant function of the current input, the current output, and the previous state. They showed that their bound is tight for known unifilar FSCs including the trapdoor channel and the input-constrained BEC.

I had one of my talks on Monday, on secret key generation from correlated Gaussian sources. We gave a polynomial-time scheme using nested lattice codes for secret key generation in a multiterminal source model. My talk slides can be found here. We used lattice quantizers to reduce the problem to that of SK generation over discrete alphabets and then used standard techniques of information reconciliation and linear SK generation. We also used ideas from concatenated coding for ensuring that the overall computational complexity is polynomial in the number of samples.

There were other interesting talks in my session as well. He, Luo and Cai had a paper on the strong secrecy capacity of the wiretap II channel where the main channel is a DMC. This is a setting where the eavesdropper can observe any arbitrary subsequence (of a certain fixed length) of the output of the main channel, and the objective is to guarantee strong secrecy. They showed that if the eavesdropper can observe an $\alpha$ fraction of the output of the main channel, and the capacity of the main DMC is $C_m$, then the secrecy capacity of the wiretap II channel is $(1-\alpha)C_m$. Bassi, Piantanida and Shamai had a paper on secret key generation in the noisy channel model, with a generalized set up when compared to previous work. Issa, Kamath and Wagner studied the Shannon cipher system, but with a new secrecy metric called the “maximal leakage”. They claimed that this was a stronger measure of secrecy than what is typically used in the literature, but not too strong to be uninteresting.

The last session that I attended was on entropy. Kamath and Verdu had an interesting paper on estimating Shannon and Renyi entropy rates of DTMCs. They studied certain plug-in estimators, and gave some guarantees on the convergence of the estimator. Ordentlich had a paper on lower bounds on the entropy rate of binary HMMs.

Other papers that sounded interesting to me: A paper on a generalization of approximate message passing by Fletcher, Ardakan, Rangan and Schnieter got me curious. I have to look up this AMP stuff sometime. Reeves and Pfister had some Replica-symmetry based methods for compressive sensing. There was also a paper on duplication distance of binary strings by Alon, Bruck and Jain. Deshpande, Abbe and Montanari have a paper on an information theoretic view of the binary stochastic block model, which is used widely in problems such as community detection. Rush and Venkataramanan had a paper on finite sample analysis of AMP, that also looks interesting.