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.

Conference travel: checklist for IISc students

I’ve made  an outline of the procedures involved in travelling to an international conference. This is mostly for ECE students at IISc, and based on my past experiences.

You have a paper accepted at XYZ conference. Congratulations! The next step is to get the necessary permissions from IISc to travel. Download this form (available from the forms page in the ece website). Fill the form, get it signed by your advisor and submit it at the ECE office. As a PhD student, you can avail up to 1 lakh for conference travel (GARP), and you can distribute this amount over upto two conferences. You must specify in the form if you would like to avail GARP. If you have already used it up, or are using funds from other sources, you must specify that you do not require financial support. If you are using any travel grant as part of a fellowship (TCS, etc.), then you must specify this in the form. You must attach a copy of the email notifying that your paper has been accepted. Submit this form as soon as possible as you require the permission letter while applying for a visa.

If you are going to a conference in India, then you do not get any travel support from IISc. You need to submit a letter addressed to the chairman (signed by your advisor) and a copy of your acceptance notification email at the ECE office.

The application typically requires 1-2 weeks for processing. Once this is done, you should get an official letter from the dean/registrar sanctioning leave for the conference duration and an approval for the travel grant (if any). This is necessary while applying for the visa. You can also apply for a travel advance by submitting this form.

Meanwhile, you can register for the conference, and book accommodation and flight tickets. Do the registration well ahead of time, as you will require an invitation letter from the conference organisers while applying for the visa (typically, you will get this only after registering).

Apply for travel grants. DST and CSIR offer travel grants (see here and here) to research students and young faculty. There are other organisations that offer travel grants as well, e.g., IARCS. Check with your local IEEE chapter if they provide any support. If your conference offers grants, apply to that as well. Make sure that these are done well in advance, as they take time to process.

Book your accommodation. Check sites like booking.com, makemytrip, hostels.com, etc. for  options. I’ve recently discovered that Airbnb offers great options, and is particularly convenient if you are going in a group.

Check the visa requirements for the country you are visiting. Note that if you are planning to avail GARP/DST/CSIR, you will have to fly Air India/partner flights. If Air India does not have flights to your venue, you must take Air India to the closest point. In case you do not have direct flights and have to stop over at another country, check if you require a transit visa. Start the visa application process as soon as possible, as this takes time. Typically, you must submit copies of permission letter from IISc, proof of funds for travel, invitation letter from conference organisers, air tickets, hotel bookings, etc. You should not face any issues with the visa if these documents are in place.

Once all this is done, and you get your visa, you can purchase foreign exchange. If you have an SBI account, go the the IISc branch for this. Otherwise, you can check Canara Bank (Inquire with CanBank as to where they have forex) or other agents such as Cox&Kings, etc. You can find some in Malleshwaram. Keep enough cash for your trip. I recommend buying an international travel card as well.

During the conference, make sure that you retain bills for all expenses incurred, including local travel (bus/train/metro/taxi) and food. Also make sure that you retain boarding passes of your flights.

After you return, the ordeal of getting your bills reimbursed begins. Fill out the TA/DA form, get it signed by your advisor and the chairman. Submit this with a covering letter and all bills (original copies for the amount you are requesting from IISc) at the finance section. If you are getting funds from several sources, you must submit bills to all these separately. Also check with the finance section for any other strange requirements.

 

Installing Dropbox in Ubuntu

Installing Dropbox in an Ubuntu system that uses a proxy can be quite frustrating, as I have experienced. So here is a workaround.

  • Download the Dropbox daemon from  here (for 32-bit) or here (for 64-bit)
  • Extract the downloaded archive. A hidden folder called .dropbox-dist is created in your Downloads directory.
  • Open a terminal, navigate to the folder where you have the extracted .dropbox-dist folder, and type
$ .dropbox-dist/dropboxd
  • Finish the setup.
  • Open startup applications, and add the file dropboxd.
  • And voila! You’re done!

Plagiarism

Mamidala Jagadesh Kumar

Literal and Intelligent Plagiarism: Students Beware!

M. Jagadesh Kumar, NXP (Philips) Chair Professor, Dept of Electrical Engineering, Indian Institute of Technology, New Delhi, INDIA. Email: mamidala@ee.iitd.ac.in

(How to cite this article: M. J. Kumar, “Literal and Intelligent Plagiarism: Students Beware!”,  IETE Technical Review, Vol.29 (3), pp.181-183, May-June 2012.)

Academic plagiarism has become like a viral fever that can affect even a healthy person if sufficient preventive measures are not taken. Untrained research students, who need to write good quality research papers under tight time constraints, are usually the victims. It is not uncommon for research supervisors to experience a psychological burden while approving the student’s paper for submission to a journal or a conference. Who knows if a sentence copied by the student while writing a research paper may be detected years later, subjecting the research supervisor to a great embarrassment. When the supervisor asks them to be careful about plagiarism, the students may…

View original post 1,322 more words

Nash and cryptography…

Turing's Invisible Hand

The National Security Agency (NSA) has recently declassified an amazing letter that John Nash sent to it in 1955.  It seems that around the year 1950 Nash tried to interest some US security organs (the NSA itself was only formally formed only in 1952) in an encryption machine of his design, but they did not seem to be interested.  It is not clear whether some of his material was lost, whether they ignored him as a theoretical professor, or — who knows — used some of his stuff but did not tell him.  In this hand-written letter sent by John Nash to the NSA in 1955, he tries to give a higher-level point of view supporting his design:

In this letter I make some remarks on a general principle relevant to enciphering in general and to my machine in particular.

He tries to make sure that he will…

View original post 614 more words