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.

Advertisements

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.

 

Inventories and driving cars

This week, we had a talk by Amit Sharma, the CTO of Zoomcar as part of the newly initiated industry interaction seminar series. Zoomcar is a self-drive car rental company. The idea is that you can rent a car to drive for a few hours/days. The idea is that you can book a car, pick it up from one of the many pickup points, drive it around and return it to the same point. This is convenient if you want to go out for a drive but don’t own a car. Although there are several such companies in the west, India is only slowly warming up to this idea now.

The main theme of the talk was of inventory management. I found this problem quite interesting, and will attempt to describe a basic version of the same here.

Suppose that we have  K identical items (in this case, cars) in our inventory. Several customers arrive at the store to rent these items for specified durations of time. Customer i arrives at time t_i^{(b)} (booking time) and requests an item for the duration t_i^{(s)} (the start time) to t_i^{(e)} (end time). Note that t_i^{(b)}<t_i^{(s)}<t_i^{(e)}. The problem now is to decide which bookings can be satisfied, and how one can allot the various items to the users. Customer i must be told, immediately upon requesting a booking, whether he can be allocated a car/item or not. The actual allocation of the car/item however can be done anytime before t_{i}^{(s)}. Each booking is associated a certain revenue depending on the duration for which it is booked. For example, a customer booking an item for 2 hours may have to pay more money per hour than a customer booking for a day (discounts for longer durations). To make matters worse, the K items may not be available at all times. For example, some of them may be unavailable from 8 am to 1 pm on Sundays due to a scheduled servicing/maintenance.

The problem sounds simple enough, but there are several challenges. Optimal solutions may exist, but we want an algorithm that runs in real time, and has a complexity as low as possible. For example, listing all the items that are available at any point of time requires a huge storage space, and an algorithm that searches through all of this may require a large overhead. However, just keeping track of the number of items available over time and using this to decide whether items are available or not will not work. To illustrate this, suppose that item 1 is available from 1 pm to 5 pm, and item 2 is available from 3 pm to 9 pm. If we only list the number of items, we see that one item is available from 1 pm to 3 pm, two are available from 3 pm to 5 pm, and one available from 5 pm to 9 pm. Let us now imagine that a user wants an item from 2 pm to 6 pm. We see that the number of items available for this duration is atleast one. However, this request cannot be catered to since no single item is available from 2-6 pm.

There are several other challenges that I have not mentioned here. One can formulate different problems depending on what the variables to be optimized are, and what quantities are to be optimized. For example, only optimizing the revenue may not work, as it may eventually lead to decrease in customer satisfaction. The algorithm must be, in some sense, “fair”. Regular maintenance of items is required, and one can optimize when each item must go for maintenance. In essence, this is an interesting (real-world) problem and good solutions may have a great impact on several areas.

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!

The DNA model: Three important lessons

I came across an article in a Google+ post that I found very interesting. Here is the link to the original article:
http://ajrccm.atsjournals.org/content/167/8/1047.long

The article is about the famous paper by Watson and Crick that proposes a model for the DNA. It turns out that they were not the first to propose such a model, and neither were they the only ones working on a model for the DNA. Two other researchers, Rosalind Franklin, and Maurice Wilkins were independently studying the DNA, trying to come up with a structure. Watson and Crick had met these two people, and studied the experimental results by Franklin and Wilkins. Apparently, Franklin and Wilkins, although working in the same university, had a tiff with each other and did not work together. The three groups published their findings in the same issue of Nature. However, it was Watson and Crick’s paper that became more famous and the model of the DNA today is popularly attributed to them. The rivalry between Franklin and Wilkins proved to be costly for them.

People generally tend to work independently in most universities in India and there is little collaboration, even within the same university. People tend to see others as their rivals, but little do they realize that they could increase their research output by working together. This is true not just in research, but in many other fields as well.

Getting back to the DNA story, two other researchers, Fraser and Stokes had come up with a similar helical structure for the DNA. Their structure had some minor fallacies, but they did not publish their findings. Had they done so, Watson and Crick might not have been given so much credit. There have been many such cases, where people came up with good ideas, but did not believe in them enough to publish it, thereby losing the glory.

The article also describes how the paper by Watson and Crick was very well written and neatly presented, in contrast to the two other papers which were littered with jargon. A research paper that is well written, and follows a simple style reaches out to a wider audience and becomes more popular. Paul Halmos deeply emphasizes on this aspect in his essay, “How to write Mathematics” (a link to the pdf can be found here)

To summarize, these three lessons are very important for every researcher:

  1. It is a better idea to collaborate with researchers of the same university than to work independently. It saves a lot of time, and you both get the credit.
  2. Publish all your findings. Unless it is in print, you don’t get any credit, and
  3. When you write up a paper, make sure that it can be easily understood by a wide enough audience. This is probably the most difficult of the three, since writing a good article takes a lot of time and experience.

Book review: “And then there were none”

I read “And then there were none” by Agatha Christie last weekend, and there’s just one thing I’d like to say, “Mind blowing”.

I’m not exactly a big fan of Christie’s, and when a friend recommended me to read it, I was a bit sceptical. I didn’t find the first chapter too pleasing, but after that, I simply couldn’t put the book down. The plot is simply brilliant, and Agatha Christie keeps you guessing.

Ten people are mysteriously invited to a desolate island by a person they have never met before. There doesn’t seem to be anything common in them, or is there? The first night they are marooned on the island, there is a mysterious recording played. And then, they start dying, one by one. An island inhabited by no one else but the ten of them. And there is also that creepy poem about ten little soldier boys…..

The story is fast paced, and keeps you engrossed. The ending is brilliant, where the plot is revealed. This is surely a masterpiece, and it is one of the best selling books of all time. Definitely worth reading.