An Unconventional Winter - Theoretical Computer Science at IIT Delhi

I was informed about the winter school via email and decided to go since I was interested in theoretical computer science (TCS) and had nothing, in particular, to do in December. I thought it would be an excellent opportunity to explore research in TCS and see IIT Delhi. Applying for TCS consisted of filling out a form and submitting my CV.

Travel expenses were taken care of in part by the CSE Department, IITD, who refunded the equivalent of a train ticket to Delhi. I arrived one day before the classes started and spent the day settling in. I was given a room in Hostel Shivalik and access to the mess inside the Hostel. The room was quite comfortable - a pillow, mattress and rug were provided, along with a bucket and mug, which I shared with my roommate. The food and service in the mess were excellent. When evening came, I went for a walk around the campus with a couple of other early arrivals. The IIT Delhi campus was huge; we had plenty to explore. We saw large dogs, cats, peacocks and rabbits (which were being raised inside the hostel; a rabbit would occasionally enter the mess during mealtimes). The temperature fell quite quickly after sunset, and I was pretty unprepared for the cold of a Delhi winter. We spent the rest of the evening in the hostel and discussed the upcoming lectures.

On the first day, we opened with a session on secret-sharing in cryptography. The lecture was fascinating, with active participation from the audience. We had an introduction session where each person briefly mentioned where they were from and what branch and degree they were pursuing. The attendees were quite diverse in branch, with people from CSE, mathematics, math and computing, electrical etc. There were B Tech, B Sc, M Tech, M Sc, PhD students and even one student who was currently in the industry. The attendees were from colleges across India, from the IITs, NITs, IIITs, ISIs, and others. After networking with everyone during the long lunch breaks, I gained a good picture of the wider world beyond CSE.

The lectures were very engaging and exciting. Most lectures began with simple real-life examples before moving to a formal statement of the problem being explored. After this, a naive solution was presented and analysed, followed by a non-trivial improvement to the naive approach. By the end of the lecture, the discussion would have arrived at cutting-edge research related to the problem. We had classes on quantum computing, expert learning, cake-cutting, dynamic graph algorithms, stable matching, approximation algorithms and complexity theory. Every day ended with an activity session during which we would explore questions posed during the earlier lectures and try to solve them. Despite being at the UG level and requiring little to no background knowledge to follow, most of the lectures were quite intellectually challenging. We were exposed to several new ideas in every lecture.

The intellectual discussions were not limited to the classroom; we split into groups and explored the city during one activity session. My group walked in the Rose garden while discussing the relative merits of different voting systems and various optimisations to the algorithms designed to solve the cake-cutting problem, along with interesting variants of the cake-cutting problem. We ended our walk at one of the shops inside IITD, where, over a cup of tea, Dr Rohit Vaish showed us how Sperner's lemma could be used to obtain solutions arbitrarily close to perfect using a simplex embedded in an n-dimensional space, where n is the number of people among whom the cake is divided.

One memorable lecture involved a practical demonstration of the core principles of information theory in the form of a card trick. The professor asked a volunteer to pick five cards from their assistant and return any four of the five cards. When the assistant read out the four returned cards, the professor guessed the fifth card. This was done by encoding information about the fifth card in the order in which the four other cards were read out. We analysed a general version of this card trick and showed how, to pull off this trick, the number of cards in the pack is limited by the number of permutations the assistant could make from the cards given.

On the last day of the school, we had two interactive sessions with the CSE faculty of IIT D. The first session consisted of a panel of junior faculty who dealt with questions about the current state of CS research and explained how academia operates. The second session consisted of a panel of senior faculty, who told us about the long-term trends they had observed over their long careers. The panellists in both sessions were very pleasant and approachable, eager to share their words of wisdom with the young minds arrayed before them.

Here is a small list of particularly memorable exchanges:

• When asked about how one dealt with very challenging problems where one did not make any headway after spending a considerable amount of time and effort on them, the panellists said that though one had to move on eventually, one ought not to forget about the problem entirely but to "move it to the back burner and let it simmer". One of the panellists gave an example of one such problem, which they solved after letting it simmer for several years.

• Someone from the audience asked a question which was in most of our minds - How does one ensure that one stays productive in a research setting? A student's productivity is reflected in the grades they achieve, and the professional's productivity is reflected in the work that they do. In a similar vein, what determines a researcher's productivity? What feedback mechanisms let a researcher know if they are utilising their time well? Before answering, the panellists acknowledged the importance and the complexity of the question posed to them. The panellists advised one must keep reading research papers and trying to summarise them. In addition to providing an objective metric for productivity, this also exposes one to new ideas which may be applied to problems which one is currently working on.

• When the discussion turned to talk about PhD applications, one of the senior faculty members shared an interesting anecdote about a statement of purpose they had seen. In response to a question about what made one interested in CS, an applicant had responded that they had always been interested in CS from a very young age since their parents began teaching them CS even before they were born. We were told that people who regularly look at SoPs are quick to develop a "bullshit detector"; we were advised to keep the floweriness of the language to a minimum and write SoPs which are clear, concise and stick to the point.

• Regarding the issue of choosing which topic to research, we were told to avoid falling for whatever was the hot topic out of a misplaced fear that since all the funding was being given to projects in that area, no other areas would be adequately funded. One of the panellists told us the tale of how they had chosen to do research in AI before it exploded, during the time before the AI winter. They went where their interests took them and explored other areas during the winter and were pleased to see the current resurgence of AI.

• Another popular question put to both panels was the question regarding teaching: How does one balance their pedagogic responsibilities with other academic duties? The panellists said that condensing information they had learnt to a form that can be taught to others helps solidify what they had learnt. One of the professors said that they often try to see if complex topics which others think are meant to be learnt by graduate students can somehow be explained to undergrads. Another professor mentioned that they find teaching to be mentally calming, much like meditation.

• The panellists also identified a problem with how research papers are often written - even though the spelling and grammar are perfect, the structuring of the paper is such that the ideas presented need to flow smoothly. They noted how some papers seem to start with a recap of existing ideas rather than directly presenting the new idea being written about and advised that the author should write the initial part of the paper in a way that hooks the reader and makes them eager to read more. They also stated that they considered the active voice better suited to papers than the passive voice. For instance, saying "X was done." prompts the reader to ask, "By whom? Did the authors do X, or did someone else do X?" This can be avoided by saying, "We did X". One panellist shared an amusing anecdote of someone who was the sole author of a paper who used the singular first person everywhere. The reviewers were so jarred seeing "I" and "me" everywhere that they requested that the author use the plural first person, despite having no co-authors.

• During lunch, the students often congregated in circles to talk. The topic of discussion at one such circle was the question of whether it was better to pursue a research career in India or go abroad. One of the panellists said that there was a significant advantage in doing research in India since the funding is a lot more certain. The professor doing research in India does not need to worry about securing funding or paying their research assistants since the funds are given by the government. In contrast, researchers in the USA have to spend a significant amount of time and effort to secure funding for each project. Furthermore, paying salaries during summer becomes difficult, and thus professors encourage their assistants to get summer internships just to ensure they have an income. When asked about other G7 countries, one of the professors told us about their experiences in Germany with the DAAD programme .

After lunch (during which I was involved in a very interesting discussion about a research paper which explored how a computer that could send the results of a computation backwards in time would affect existing complexity classes), the faculty and students went on an excursion to the National Museum in Delhi. After a couple of hours or so, various groups splintered off to visit other landmarks while others returned to their rooms to start packing.

Overall, my experience with TCS was very good: it exposed me to exciting ideas and people. To those interested in theoretical CS and considering a career in academia, I recommend that you attend the TCS winter school when it is next conducted.

Special thanks to Lella Hemasri Sai for her inputs.

-----------------------------------------------

For more info on Spener's Lemma:

https://www.nytimes.com/2014/04/29/science/to-divide-the-rent-start-with-a-triangle.html

NYT: Sperner's lemma defeats the rental harmony problem