Vineet Nair — WACT 2016

Vineet Nair talks about his visit to Tel Aviv for the 2016 Workshop on Algebraic Complexity Theory

To begin with, all the excitement went down the drains when my flight from Mumbai got delayed.This meant that I would miss my connecting flight from Ethiopia. Anyways, I landed at Ben Gurion airport in the morning. Adding to my miseries, the airline misplaced my luggage.In short, my journey was far from pleasant.Finally, I reached the student dorms around 5 in the morning, welcomed by an amicable smile of Gaurav Sinha, who remained my roommate for the next ten days. We had several interesting conversations over the next few days mostly on our research related topics, sometime we went off the track and shared our philosophical sides.

We had a bootcamp for the first three days, those were the best three of my total ten days stay. It was well structured by the organizers. Amir Shpilka started with the introduction of VP and VNP and some basic structural results in the area. This was followed by some interesting lower bound results by Ramprasad Saptharishi. Further, Ankit Gupta presented the famous depth reduction results. The bootcamp was concluded by two set of talks: Michael Forbes presented results in connection to Polynomial Identity Testing (PIT), and Chandan Saha spoke about shifted partial derivatives – a measure used heavily to prove lower bounds in the recent literature. These set of talks were insightful and helped me better understand the literature surrounding the problems I wish to solve, but I gained most by the interaction with fellow attendees in between the lectures and during lunch and tea breaks. Special thanks to Rohit Gurjar who patiently answered all my queries.

The main theme of the workshop was connections between `Algebraic Complexity Theory’ and other areas like `Geometry Complexity Theory’ and `Proof Complexity’. All the talks were informative and the topics were dealt nicely enough to not give a gibberish feeling even to novices like me. Some of the talks that peaked my interest were `Perfect matching for bipartite graphs is in quasi-NC’ by Rohit Gurjar, `Factors of polynomials of low individual degree’ by Rafael Oliveira, `An almost cubic lower bound for depth three circuits’ by Neeraj Kayal and `Pseudo randomness for bounded space’ by Parikshit Gopalan. The videos of all these are available at the following link .

The participants had a day’s break due to Shabbat between the bootcamp and workshop. Shabbat meaning `the day of rest’ in Hebrew, is a day of religious observance and abstinence from work, kept by Jews from Friday sundown to Saturday sundown.We ventured out to Old Jerusalem on this day. The city was mostly closed due to Shabbat, but it still had a lot to offer for a wanderer’s eye. We walked through the Damascus gate absorbing the cultural richness of this place.  A few of the places we visited were the western wall, new Jewish quarter,  Al-Aqsa mosque,  Church of the Holy Sepulchre, king David’s tomb, the room of last supper. By the time we headed back in the evening I remember feeling overwhelmedby the history and culture of this city.

Apart from this, we had a guided walking tour of the Old Jaffa port arranged by the organizers. Our guide explained the significance of each place really well, though I don’t remember much of it now. Imagine a place having history of at least four to five thousand years and has been conquered multiple times by a number of emperors. This place ought to be special and a few lines cannot justify the experience one has visiting this place.

At the end, my experience of attending this workshop was numinous.  I would like to thank the organizers: Amir Shpilka, Michael Forbes and Ramprasad Saptharishi for supporting my travel and accommodation that provided me the opportunity to attend this enlightening workshop.

Kirankumar Shiragur — CDC 2015

Kirankumar Shiragur writes about his trip to Osaka, Japan to present a paper at CDC 2015.  The paper was based on his M.Sc. thesis work at IISc. Kiran will join Stanford MS&E as a Ph.D. student in Fall 2016.

The purpose of the visit was to present my work with Prof. Arnab Bhattacharyya in the area of Opinion Dynamics. The research work investigates the convergence behaviour of different variants of the Hegselmann-Krause system (HK system for short). The HK system is one of the most popular models for the dynamics of opinion formation in multiagent systems. Agents are modeled as points in opinion space, and at every time step, each agent moves to the mass center of all the agents within unit distance. The rate of convergence of HK systems has been the subject of several recent works. In our work, we investigated two natural variations of the HK system and their effect on the dynamics. These results collectively were accepted in CDC 2015. We were invited to the conference and I got the opportunity to present our paper. I enjoyed being at Japan and the remaining part of the blog would give you different reasons for it.

I reached the airport (Osaka, Japan) on Dec 14th. From there, I took one of the fast-running trains  which connects the airport to a place nearby my designated stay. The train ride was pretty nice! Japan is a developed country and you can see tall buildings located on both sides of pathway of the train. The architecture of these buildings is very different and is eye pleasing. I reached my destination after an hour of train ride and looked out for signs to take an exit near to my Hotel.  As my stay was nearby I decided to walk. The Japanese people are really nice and helpful beyond one can think. I approached one of the old Japanese person for help as I couldn’t find my hotel and he ended up walking with me for fifteen minutes to my hotel. Japanese have nice tradition to greet people which feels great!. We bowed to each other and he left. If you are in Japan, you would be greeted very often and even by strangers.

On the next morning (Dec 15th), I visited the conference and attended couple of interesting talks on Sum of Squares (which I was exploring at that point) and some other interesting topics on the next day as well. On the third day (Dec 17th), I attended one of the talks by Prof. Behrouz Touri, CU-Boulder. Prof. Touri has published a lot of articles on the convergence of the Hegselmann-Krause system. I read a lot of his work in this area and was very excited to meet him in person!. I attended the talk and waited for an hour to meet him after everybody in the audience left.

The experience of meeting him was great!. I discussed with him about his work and described to him my current work and the work we published at the conference. During our discussion on other related topics, it turned out that we both independently were trying to find the convergence proof for Heterogenous Hegselmann-Krause system. We discussed about this topic for an hour, and also pointed out each other some recent work in this area. He redirected me to one of his work where they prove convergence of a system very close to Heterogenous HK system. I enjoyed meeting him and consider it to be the best part of the conference. He too was impressed by my work and wanted to write me a letter of recommendation in case I am applying for a Ph.D and I did take his recommendation :).

Dec 18th was the day of my presentation and last day of the conference. My presentation was on the very first session of the day and my talk was first in the session. The talk was about 20 mins long with 5 minutes for QnA. I was nervous but had a wonderful experience delivering the talk in front of a large and varied audience. After the end of my session, I went on to explore more of the beautiful Osaka city.

The last two days is when I explored more of Osaka city. During this period I visited couple of tourist places and apart from these the city itself is beautiful. I visited some of the top places to visit in Osaka (Google recommendation) mentioned below.

Osaka Castle : A very beautiful place, the pictures describe themselves. It has a museum worth visiting.

Dōtonbori: Great shopping place, you will be surprised by their shopping streets.


Tempozan Ferris Wheel: One of the biggest wheels in Japan giving awesome view over city and located at the right spot.

Osaka Aquarium: Largest aquarium and they even allow you to touch fishes which is pretty cool!.

Shitennō-ji: It is the first Buddhist and oldest officially administered temple in Japan and Buddhism is one of the two major religions. A must visit place. It is a very quite and peaceful place.

Ōsaka Tenman-gū: is a Shinto shrine in Osaka near to my hotel and Shinto is another major religion in Japan. The temple is very beautiful.

Apart from all these my last experience is the one which made my trip memorable!.Finally when I was all set to leave the city. I decided to take a train to Airport. My train was scheduled at 12:04 PM. I took the ticket and rushed to the platform. I reached a platform at 12:02 PM and there was a train already standing there. Just to confirm, I showed my ticket to the train operator and realised I was at the wrong platform. I rushed to the right platform and found a train ready to departure. It was 12:08 PM and I boarded this train. The train duration was one hour and my flight was scheduled around two and half hours later to that. Just to confirm, I asked an old couple sitting next to me if I boarded the right train. They looked panicked 🙂 even though it was me who boarded the wrong train. Yes, I boarded a wrong train and they took me to ticket checker. The ticket checker explained that I boarded a wrong train. He was uncomfortable with english, and we ended up communicating using Google translator 😀 and it is really hard. He took out the route map and wrote down schedule for next three trains to reach airport. My flight boarding was suppose to start at 2:50 PM and the last train in this schedule reached the airport at 2:25 PM. I panicked and was almost certain to miss my flight. Impatiently I waited for next stop of this train which was at 1:10 PM. My next connecting train was at 1:20PM. I was nervous about not making to one train properly and was wondering on how would I board three of them consecutively with a time difference of 5-10 minutes for each. I was also worried about any of these trains getting delayed. However that was not the case, I reached at each of these station at the accurate time he wrote (Accurate in seconds!). Japanese are punctual in time and that was the reason I missed my initial train in the first place :). I got down from my first train at 1:10 PM and was lost to find my next train. Suddenly a train station police came in my direction and asked “Airport?” I said yes and he took me to the next train which I was suppose to board and this happened in all other further stations. My train checker called and informed these people to pick me up and drop me on to next train. This is the level of help they do. This incident was remarkable and made my trip most memorable. I reached airport at 2:25 PM and finally caught my flight.


All these incidents made this trip the best of all. I love Japan and wish to visit it again. I am even considering to spend some years there ;). Thank you Prof. Arnab Bhattacharyya for providing me such an opportunity!.

Palash Dey — AAMAS 2015

For our first report, Ph.D. student Palash Dey describes his visit to Istanbul, Turkey to attend AAMAS 2015, one of the leading conferences in the area of intelligent systems. His papers at the conference are linked from here.

May 4: On the first day, I attended the Workshop on Exploring Beyond the Worst Case in Computational Social Choice (EXPLORE 2015). A prominent and long-pursued research thread in computational social choice (comsoc) theory is to study the use of computational intractability for protecting election systems against various manipulative attacks. However, some recent works expose the weakness of this approach – the intractability results hold only in the worst case! After that, it became very important to study intractability results beyond worst case guarantees. This was the focus of the workshop. On a related note, we had a paper in this conference where we show that although the classical manipulation problem is known to be NP-complete, they are not very hard to solve in the sense that they admit what is known as a polynomial kernel in the context of parameterized complexity.

May 5: The whole day was the doctoral consortium. This event was meant to be for guiding senior Ph.D. students in their future career (but many junior Ph.D. students including me also attended the program). It had interviews of a few established researchers, and they were sharing their own Ph.D. experiences. The session was really an interactive one, and I enjoyed it very much. In the second part, I presented my Ph.D. work. It was a ten-minutes talk. The mistake I made was that I intended to present all of my works and thus I really had to hurry! Choosing any one of my works and explaining it would have surely made people understand better.

May 6: I had a paper presentation that day. I also presented the corresponding poster.

May 7: I bunked the whole day!

May 8: Again I had two papers to present. During the poster session, I explained my work to Edith Elkind and Toby Walsh. Both of them are leading researchers in comsoc. After the presentation, I had a chat with Jerome Lang who is again a leading figure in comsoc.

Favourite papers

I found two papers at the conference particularly interesting.

  1.  “Complexity of Mechanism Design with Signaling Costs”, by Andrew Kephart and Vincent Conitzer: This paper proposes a notion of mechanism design in a restricted setting in the following sense. The set of actions of the players are fixed. The mechanism designer has to choose from a set of utility matrices (possibly exponential) to implement a social choice function. The question is does there exist a game which implements that choice function.
  2. Controlling Elections by Replacing Candidates or Votes“, by Andrea Loreggia, Nina Narodytska, Francesca Rossi, K. Brent Venable, Toby Walsh: This paper introduces a notion of candidacy game in the context of an election. This is particularly interesting since we are still finding a suitable notion of equilibrium in the context of voting. They proposed in
    this paper (and also a series of paper before!) a behavioral dynamics on the behavior of voters and candidates and showed some existential results.

Local Travel and Food

Bus and metro were very accessible and cheap (compared to other European countries). I was staying in the area called Taksim which was very nearby to the historical places namely Aya Sofia, Topkapi Palace, several museums, Blue mosque and so on. I just used to go to Eminuno by bus, and all the above mentioned places are at a walkable distance away. Also the ferry ride in Bosphorus channel is something one should not miss.

Regarding food, there were lots of (quite cheap) restaurants selling doner, hamburgers, and kebabs (both beef and chicken were available).

Bosphorus The Blue Mosque