Arpita Biswas — AAAI ’18

Arpita Biswas, PhD student in the Game Theory Lab at the department of Computer Science and Automation, shares her experience of her trip to New Orleans, Louisiana, USA.

This post is about my recent visit to the city of New Orleans, where I presented my paper titled “Groupwise Maximin Fair Allocation of Indivisible Goods”, at the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018). The conference was held between 2nd February and 7th February 2018.

About the Location

The conference venue was the Hilton New Orleans Riverside hotel, located in the Warehouse and Arts District, which overlooks the famous Mississippi river.  The area surrounding the venue was very scenic.  The hotel was also very close to some of the popular tourist attractions, such as the French Quarter, Jackson Square, the Audubon Aquarium, the Butterfly Garden and the Zoo. Fortunately, my visit coincided with onset of the Mardi Gras festival! This gave me the opportunity to witness, first-hand, the city’s vibrant spirit at its best. People were engrossed in eating, throwing beads, and parades. The carnival was truly one of a kind, with funky costumed parade rolls, followed by decorated trucks which threw gifts (beads, toys, hats, decorative accessories) towards the crowd. The super excited crowd, who thronged the road sides, collected the gifts in huge bags, and danced to the rhythms of the parade! In the evening, the neon lights added a new dimension to the revelry– the shiny clothes of the performers and their bead-necklaces emitted colorful reflections, and the gift-loaded trucks simply dazzled!

Apart from the ongoing carnival, I thoroughly enjoyed the spectacular neighborhoods. A walking distance away from the conference venue was the French Quarter, which is famous for its historic and picturesque architecture, antique stores, century-old restaurants, and the vibrant night-life. The streets are lined with incredible performers — dancers, magicians, painters, and singers (accompanied with incredibly skilled drummer, flutist, guitarist, saxophonist etc.). The legendary Jazz music clubs and live performances were, quite literally, music to the ears! Further walk down from the French Quarter landed me to the most raucous place I have ever been, called the Bourbon Street. The entire street was throbbing with loud music, and people dancing to the beats. Surprisingly, I found most of the people dressed up in strange costumes– red shiny eye-wears and furry head-gears with glowing horns (almost like Halloween costumes). I could not stay there for long since I witnessed the crowd getting crazy and throwing beads and paper cups at each other; it was an experience that is best enjoyed from a distance! On the way back, I visited Jackson Square where the grand St. Louis Cathedral is located. It is known to be the oldest active Roman Catholic Cathedral in the United States, originally built in 1727 (rebuilt in 1850). This building stands tall amidst beautiful flower gardens. Moreover, the horse-carts, lined up all around the fence, make it a prominent subject of interests for painters and photographers. I was overwhelmed with the incredible paintings which were displayed around the iron fences by the talented artists. The tour for the day ceased on a distinctly Parisian note– a pleasing cup of coffee (café au lait) and authentic doughnuts called Beignets (a must-try) at the Cafe Du Monde coffee bar (established on 1862). I found this place so relaxing and soothing that I walked down to Jackson Square almost every evening during my stay.

Another place where I had a remarkable experience is the Butterfly Garden and Insectarium. I really enjoyed the interactive exhibits and the showcase of a wide variety of live insects (which I have never heard of till then). The exhibition also included a 4D animated movie on insects. However, I was overwhelmed after going inside the glass covered butterfly house, where stunning and colorful butterflies were flying all over the room. They demonstrated how the newly hatched butterflies are gently taken out of the cocoons and set free to fly around. This museum was really informative and educational. Some of the other places worth visiting are the Audubon Zoo and the Audubon Aquarium; I regret not being able to visit those.

Some other recommended “things-to-do” that I had to skip due to heavy rainfall are the “swamp tours” (highly recommended for people who are fascinated with alligators, snakes and other swamp creatures) and the “ghost tours” (starting from the unique above-ground structure of the cemeteries to the stories about witches, ghosts, vampires, murderers, Voodoo practices etc.). The ghost tour is highly popular for people who want to get a taste of the haunted side of New Orleans.

About the Conference 

The AAAI Conference on Artificial Intelligence (AI) is one of the top-tier conferences in AI.  AAAI 2018 was densely packed with presentations, and was heavily attended with about 930 main track presentations, 7 invited talks, 16 different workshops, 25 tutorial talks and about 2700 attendees. There were more or less 8 parallel sessions running throughout the day! This made it difficult to attend talks from multiple disciplines. Hence, I chose to attend the talks in the “Game Theory and Economics” session, which is more related to my PhD topic.

Our paper (joint work with Siddharth Barman, Sanath Kumar Krishnamurthy and Y. Narahari) addresses the problem of fair allocation of indivisible goods, which is currently a very active area of research, with lots of possible real-world applications. In particular, we define two new “fairness” notions for allocating indivisible goods, and provide a polynomial time algorithm to compute such allocations.

During the conference, I had several interesting discussions with many eminent researchers from the Game Theory community. This conference provided me an excellent platform to network with active researchers, and I got valuable feedback on my ongoing work. Apart from my own paper, I presented two other papers (because the authors of those papers could not make it to the conference). All my talks were highly appreciated, and I am glad that I got the opportunity to present and discuss other exciting topics.

There were various other networking opportunities which were organized by the AAAI committee. The “student welcome dinner” and “student abstracts session” helped the students understand each other’s works, dive into possible collaboration opportunities and explore interesting research directions. The “student job fair” was extremely popular among those who were looking for internships or full-time positions at industrial research groups. The “breakfast with champions” session was organized as part of the annual women mentoring event, where a few female students got the opportunity to interact with some of the prominent researchers and professionals. I found this session extremely inspiring and informative. Overall, the conference was well organized, giving the students ample opportunity to get inspired and bring back with them loads of research ideas.

Last but not the least; I gratefully thank Google for the PhD Fellowship and Microsoft Research for the travel grant. 

Adarsh Patil — HiPEAC ’18

Adarsh Patil talks about his trip to Manchester, UK to present a paper at HiPEAC 2018. Adarsh is a M.Sc. (Engg) student at CSA advised by Prof. R. Govindarajan.

This post is about my visit to Manchester, United Kingdom to attend the HiPEAC 2018 conference. The conference took place from 22^nd to 24^th January 2018 at the 130 year old Manchester Central Convention Center.

I was to present my paper titled “HAShCache” in the main track of the conference. The work aims to architect an effective organization for stacked DRAMCache to improve performance of integrated heterogeneous CPU+GPU architectures. It was submitted to the ACM TACO journal which has a rolling submission window throughout the year. Papers accepted in the journal the previous year are then invited to present their work at the annual HiPEAC conference.

The Plan

I started planning for the trip as soon as I received the invitation letter in Nov 2017. The UK visa process was smooth, and I received the passport with the stamped visa in 1 week. I booked the KLM flight to Manchester via Amsterdam and stay at Premier Inn hotel diagonally opposite to the conference venue.

Short backstory here: Along with my masters degree, IISc gave me a wonderful hobby that kept me going during the rigors of the program – RUNNING. My first ever competitive run on 2016 Republic Day had kindled a running fire in me and by 2018, I had already run 5 Half Marathons. My travel to Manchester gave me a perfect opportunity to do my debut race outside the country – my first international half marathon.  I signed up for the 35^th Essar four villages Half Marathon scheduled on 21^st January 2018 at Helsby village (about 55 kms from Manchester).

The Journey

After a long hiatus of 5 years, this would my first trip out of the country. While doing my web check-in, I quickly realized my snafu – If you book a seat on Air France, KLM, Delta or Etihad – they are all operated on code share basis by Jet Airways!! As I entered the Bengaluru International Airport, I was already mentally prepared for bad airline service. But hey could be worse, at least I would get good Indian meals I thought. I couldn’t be more wrong – the Jet Airways flight to Amsterdam was delayed which meant I would miss my connecting flight to Manchester. Once I boarded the flight (as expected), my in-flight entertainment system screen was tiny and had headphone jack and volume button issues. This was a 13.5 hour flight, and I settled in recognizing there was very little the airhostess could do as the flight was full. I landed in the Amsterdam airport a full 4 hours late, and I ran from pillar to post in this massive airport to figure out how to get my flight rescheduled, get my boarding pass and get to the boarding gate. Eventually I reached Manchester on the evening of 20^th Jan.

 

The Run

The very next morning, a very kind gentleman and a fellow runner at the event picked me up from the hotel to reach the race venue. The conditions were extreme and unlike anything I had ever prepared for here at Bangalore. Temperatures of -1 degrees Celsius with snow and rain pelting down and a cold bone chilling wind to top it off. Jet lagged from travel and with no good veg food the previous night meant I completed the 21.1 kms in 2 hours 10 mins. Yet it was a very memorable experience for me to run in the famed and lush serene British countryside.

 

The Conference

In a nutshell – The conference had 3 excellent keynotes. The opening keynote was by Dr Maria Girone, CTO of CERN, who spoke about the computing challenges at the Large Hadron Collider (LHC). The entire world is intrigued by the work done at the LHC, and Dr Maria gave us a glimpse of the work and problems people at the LHC are attempting to solve. She illustrated the way compute is structured at LHC to store and analyze the results of the experiments. The rate of data generation (1 PB/s of data generated by the detectors and over 60PB/s is stored and processed per experiment) and processing capability along with the scale of compute being used at LHC is truly mind boggling and poses several interesting problems to computer science researchers from all streams.

The second day, Dr Dileep Bhandarkar from Qualcomm Data Center division spoke about the emerging trends in the datacenter. Dr Dileep motivated the need for improved energy efficiency in modern processors for data centers. He delved into details of the upcoming ARM based high performance processors for data centers that are being engineered at Qualcomm. These processors have the ability to provide good performance compared to modern x86 based cores while being much more energy efficient. Because of the simpler ARM cores, the die is also able to accommodate larger capacity caches improving memory access latency. From being leaders in mobile processor technology, Qualcomm have adapted lessons learnt from the mobile computing platforms and are including several heterogeneous add-in accelerators on die. His talk was very well received and showed that there is plenty of opportunity for innovation and research into improving efficiency of chips.

On the final day Daniel Belov (CTO of Google Deep Mind) spoke about the advancements in Deep Neural Networks and the challenges that lay ahead. He showcased the work at Deep Mind and highlighted challenges encountered when training deep reinforcement learning agents on large workloads with hundreds of terabytes of data. He also spoke about why it poses unique challenges when designing distributed systems and hardware.

There were several parallel workshops held along with the main track of the conference. This gave me an opportunity to concisely understand some of the problem statements other researchers were tacking in adjacent domains. My presentation was in the forenoon session on the second day of the conference and was attended by a fair number of people and including the keynote speaker of the day and the compilers legend Paul Feautrier.

HiPEAC also gave me the opportunity to network with Profs and students of the HPC, architecture and compiler community some of whose papers I had fondly read. The banquet dinner at Hilton Manchester Deansgate was a true fine dining experience creating an informal setting to socialize and network to make connections for everything from jobs to pursuing PhD to floating nascent ideas.

The City

Manchester has a long history from the early vibrant cultural and social scene right from the industrial revolution to WW2 and beyond. The old Victorian era buildings and heritage is very preserved in the city center and is a beautiful sight to see and walk around. The city is well connected by trams and metro rail making it easy to move around the city. I visited the area of the Quays in downtown Manchester which is home to MediaCityUK housing the BBC studios where several famous TV shows and news bulletins are recorded and broadcast. The area also houses a huge museum which showcases the rich history of Manchester and the events that shaped the city. It also has one of the pieces from the building at Hiroshima after Little boy and a shard of the World Trade Center building after 9/11 to remind people about the horrors of war.

Manchester City tour isn’t complete without stopping off at the world famous Old Trafford football stadium where the echoes of “Glory Glory Man United” ring during the club football matches. Unfortunately, there was no match being played when I visited, but it was an experience in itself to see the magnificent arena where legends have played. I stopped by at the practice pitches to try to catch a glimpse of some famous footballers but alas it was not to be as this was off-season.

Britain’s most famous flea market is located at Bury in Greater Manchester. The market has various stalls selling absolutely everything you might need. Vendors here always sold me everything with a friendly face and lovely manners. There are plenty of eateries here, and I spent a few hours here trying the range of street food from the Bury black pudding to potato pies. I picked up some souvenirs and a variety of handmade chocolates here.

I had a remarkably memorable experience attending HiPEAC 2018 at Manchester. It is here that my M.Sc. (Engg) research work and my hobby culminated to a telltale ending. I thank Prof Govindarajan and IISc for giving me this opportunity to attend the conference.

Monika Dhok — ICSE ’16

Monika Dhok talks about her trip to Austin to present a paper at ICSE ’16.  Monika is a Ph.D. student at CSA advised by Muralikrishna Ramanathan.

This blog is about my recent travel to Austin to attend a conference on Software Engineering. Even before the journey started, I knew it would be once in a lifetime experience since I was travelling alone for the first time. I made reservations with British Airways. By the time I landed in Austin, it was already dawning. Since I was in hurry to reach the hotel, without exploring many options available for commute from the airport, I decided to hire a yellowcab, a commonly used cab service in Austin. During conference days, I planned my stay at Candlewood Suites as it was nearby the conference venue.It’s located in a nice area and is safe for travelling alone. Though it is far from downtown, one can commute easily using metro bus  which is very convenient and cheap. I didn’t get much time to roam around the city during the conference, but afterwards I took some exciting tours.

The conference was held from 14th May to 22nd May, 2016. I gave a paper presentation based on our work on “Type Aware Concolic Testing of JavaScript Programs”. Concolic testing is a technique that performs symbolic execution that treats program variables as symbols, along with concrete execution which monitors input values along a certain path. To start with, Concolic testing was proposed for statically typed languages. We observe that when this technique is applied to JS programs, huge number of tests are generated. The goal of this work is to introduce type awareness in Concolic testing to reduce the total number of generated tests for JS programs. The newly generated test suite does not compromise on bugs detected and achieved coverage. This work was presented in symbolic execution, a technical research track.

This tool is implemented on top of Jalangi framework. After the talk, I met graduate students who are working on the same framework and discussed what analyses they are implementing. Presenting at the conference allowed me to receive useful feedback on my work. Discussions with researchers in the area of software engineering were very helpful. I got the opportunity to meet researchers like Xiangyu Zhang, Michael Pradel and Satish Chandra who work in similar areas. I also discussed with them other problems that I was planning to work on and was glad with their positive feedback. There were several sessions on program analysis and related techniques. These sessions were equally helpful as they were relevant to my research interests.

After the conference, I had planned to stay at an Airbnb place which was another great experience. The place had way more than average amenities for guests right from toothbrush to breakfast. My exploration began with a day tour to the city. I came to know about duck tours from some blogs online and I decided to give it a shot. This ride was accompanied with a cool guide who was briefing various stories about places around the streets of Austin. During the tour, this bus suddenly gets in to the Austin lake, a water reservoir on the Colorado river and the place is scenic. I also traveled to San Antonio, a city in south Texas with rich colonial heritage. The main tourist attraction in San Antonio is the river walk which is the walkway along the banks of the San Antonio River lined by bars, shops and restaurants. On the way to San Antonio, I also visited San Marcos mall for shopping. The place is huge with several stores and is a must visit for shopping fans.

Duck tour bus

Austin lake

River walk

River walk

San Marcos shopping outlet

I am very much thankful to Microsoft Research and ACM Sigcaps for funding this travel. The published work is available at http://dl.acm.org/citation.cfm?id=2884859

 

 

 

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 https://www.cs.tau.ac.il/~shpilka/wact2016/videos/index.php .

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!.

Rohit Vaish — CMU Visit

Rohit Vaish (Ph.D. student advised by Prof. Shivani Agarwal) talks about new interests spurred by a recent visit to CMU.

This post is about my research visit to Carnegie Mellon University (in Pittsburgh, Pennsylvania) during Fall 2015 semester. The visit was organized under the Indo-US Joint Center for Advanced Research in Machine Learning, Game Theory and Optimization supported by the Indo-US Science and Technology Forum. My host faculty for this visit was Prof. Avrim Blum.

The broad theme of our work was designing algorithms for joint-decision making in multiagent systems. In particular, we focused on the problem of kidney exchange. This problem arises in settings where patients with kidney disease manage to find a friend/relative/spouse who is willing to donate a kidney to them but is medically incompatible (say due to blood-type or tissue-type mismatch). In such a scenario, a transplant can still be carried out via a 2-way exchange, i.e. bringing together two such willing-but-incompatible donor-patient pairs (that happen to be cross-compatible) and having the donor from each pair donate a kidney to a patient from the other pair. In this case, all four surgeries (one each for the donor and patient from each pair) need to be conducted simultaneously in order to keep any of the donors from backing out. Nowadays, more complex cyclic exchanges (like 3-way and 4-way) are fast becoming common.

In its early stages, the task of matching donor-patient pairs was performed either by individual hospitals or by a team of locally connected hospitals. Recent years, however, have seen the emergence of centrally organized exchanges such as APKD, NKR and UNOS in the US, NLDKSS in the UK, ACCORD in the European Union etc. In a centralized kidney exchange, incompatible donor-patient pairs are revealed to the central exchange by the participating hospitals. A matching mechanism then operates on this pool of revealed donor-patient pairs to find as many opportunities for 2-way (or 3 or 4-way) exchange as possible, thereby maximizing social welfare (and the number of lives saved). Hospitals might find it in their selfish interest to conceal certain easy-to-match donor-patient pairs and perform the surgeries in-house, thereby benefiting both from internal matches and the matches suggested by the centralized exchange. There is growing theoretical and empirical evidence to suggest that strategic behavior on the part of the hospitals leads to significant inefficiencies in the overall social welfare. Besides, even in the absence of strategic considerations, the matching problem itself tends to become computationally intractable when 3-way (or larger) exchanges are allowed. The challenge facing an algorithm designer, therefore, is threefold – namely, to design a matching mechanism that (a) incentivizes the agents (in this case, the hospitals) to reveal complete information about their donor-patient pairs, (b) is computationally efficient and (c) minimizes the loss in efficiency. This thread was the subject of our research.

Pioneered by South Korea in 1991, kidney exchange has grown immensely ever since. In fact, the eminent Stanford economist Prof. Alvin E. Roth was awarded the Nobel Memorial Prize in Economic Sciences 2012 (along with Lloyd S. Shapley) in part for his pioneering contributions to the theory and practice of kidney exchange. Check out his talk at Simons Institute (where he discusses the above mentioned issues in greater detail) and his ever active blog.

A recent innovation in the practice of kidney exchange is that of altruistic donation. This refers to the situation when a generous donor simply wants to donate a kidney without any particular recipient in mind. Such donors are extremely valuable in kickstarting an altruistic donor chain, where the altruistic donor donates a kidney to a patient in need, whose willing-but-incompatible donor can in turn donate to another patient in need and so on. These chains are especially useful since they bypass the requirement of conducting all the surgeries simultaneously as with cyclic exchanges. The longest chains till date have been sixty humans long or more!

If you would like to know more, feel free to get in touch!

Pankaj Dayama — AAMAS 2015

Ph.D. student, Pankaj Dayama, gives us our second report on AAMAS 2015.

I travelled to Istanbul, Turkey to attend the AAMAS 2015 conference. I had a paper (“Truthful Interval Cover Mechanisms for Crowdsourcing Applications”) to present in the conference and also attended several talks/poster sessions. Overall the experience was very good. It was very diverse conference with many different tracks, so it was really difficult to shortlist the talks to attend.  I found the following ones very interesting:

1. “Learning Submodular Functions with Applications to Multi-Agent Systems”, Invited talk by Maria Florina Balcan. This talk focused on use of machine learning in understanding submodular functions. In particular, it discussed recent work on studying the learnability of submodular functions with applications to the analysis of multi-agent systems. She discussed few general algorithms for learning such functions. Further, application of these algorithms for learning influence function in social networks was presented and empirical studies showed that it outperforms existing approaches.
2. “Dynamic Influence Maximization Under Increasing Return to Scale”, H. Zhang, A. Procaccia, and Yevgeniy Vorobeychik. This paper addressed the algorithmic question of maximizing the total number of adopters of a product at the end of finite time horizon T, where the decision maker faces a budget constraint B. They formulate a dynamic influence maximization problem under increasing return to scale and show that the optimal policy has a simple structure. It must spend the entire budget in single stage (“Best-Stage”). In the setting where time dependency of the cost function is  replaced by cumulative adoption, they propose “Best-K-Stage” heuristic algorithm and show that it significantly outperforms the “Best-Stage” algorithm.

I also got a chance to go around Istanbul and really loved the city. My hotel was very close to the conference venue near Taksim Square. It was just a few miles from old part of the city which has several museums and mosques. I did visit a few places:

• Blue Mosque (also known as Sultan Ahmed Mosque)  with blue domed exterior
• Suleymaniye Mosque (largest mosque in Istanbul)
• Grand Bazaar (with over 3000 shops selling leather goods, carpets, ceramic, etc): Any shopping here will be a test of your bargaining skills)
• Spice Bazaar (with shops selling spices, nuts, dried fruit, Turkish Coffee, Turkish Delight,etc.)
• Boat tour down the Bosphorus
• Dolmabache Palace (new palace built towards the end of Ottoman period after Topkapi Palace)
• Galata Bridge
• Basilica Cistern: One of the largest underground ancient water cistern.

Regarding travel and food, the local commute in Istanbul is very efficient and cheap. I had some challenge finding good vegetarian food, but I did like the Aryan drink, Turkish tea, and sweets (Turkish Delight and Baklava).

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).

First Post!

We are students of the Department of Computer Science and Automation in the beautiful campus of the Indian Institute of Science. This blog will showcase our adventures as we travel to different parts of the world to talk about our exciting research and expand our horizons!