It was January 2012. I had completed one semester in the PhD program. I had one more semester to search for an adviser with whom I had to spend 1/10th of my life learning about research. A senior Professor had already rejected me due to my poor grades. My only hope was a young Professor who had joined my university almost at the same time I joined and his name was Rezaul Chowdhury.
Rezaul worked in parallel computing which did not interest me then. As I had no choice and he was my only bet I emailed him that I was a PhD student and wanted to speak to him. He promptly replied and one fine day I met him. I showed him my CV and a draft of the mathematical puzzles book I was writing. I conveyed to him that I was looking for an adviser, I love algorithms, and I wanted to work in algorithms and puzzles if possible. He asked me to work under him for a semester. If both of us like each other’s style of working then he would be my official adviser and also fund me. I was happy.
The Range 1 Query (R1Q) Problem
I believed that the second semester would be the most important semester in my PhD program as if I succeed in getting my adviser I thought I would be safe, else, I knew I would be fucked. That day Rezaul game me a problem to think on that later became The Range 1 Query (R1Q) Problem, the title and topic of my first real research paper. The problem is like this: Given a two dimensional matrix, preprocess the matrix such that given a query range such as a rectangle, or right-triangle, or polygon or circle, we need to answer whether the query range contains a 1 or not in O(1) i.e. constant time and O(N) bits of space i.e. linear space. This was the major problem that we encountered in a compiler being developed at MIT called Pochoir that converts a 40 line dynamic program (a jargon in algorithms) into 40,000+ line fast optimized and parallel code. He also gave me a puzzle that I don’t remember now. I solved the puzzle in 4 or 5 hours but how much ever I tried I could not solve the R1Q problem.
I was new to research. I did not know what exactly research was. I did not know how to solve a problem in an organized way. Though I studied extensively in undergrad leaving out all play, parties, and functions, due to the poor way in which the education system is developed in India I was far far away from even knowing what exactly was research. India is an underdeveloped country in education. When I came to IBM, at nights I used to read a lot and work on puzzles. In my PhD program, as I was loaded with a lot of mostly stupid courses in my second semester I could not dedicate a lot of time towards the problem. I was thinking on the problem on Thursdays and reporting my observations on Fridays. I recall that I had 12 to 15 different brilliant ideas that could be used to solve the problem. But, I could not go beyond ideas. Ideas remained ideas. In algorithmics, ideas + proofs = algorithms. As I could not prove that some of the ideas / approaches I had worked, they did not become algorithms. I thought a lot on those ideas but could not succeed to get proper algorithms. But, in a couple of months I identified a randomized data structure that could be used to get randomized algorithms to solve the problem.
In the end of Spring 2012, I had some ideas / intuition that the count min data structure would work. Rezaul gave a lot of mathematical techniques to prove that it indeed works. By the end of Summer 2012 we had a few randomized algorithms to solve the problem. Subsequently, Rezaul also gave some deterministic algorithms on which I worked on to prove the complexity bounds and also formalized them. Further we developed algorithms to answer right-triangular R1Q. In an algorithms seminar, we got ideas to solve the spherical R1Q. Thus, we had developed algorithms and data structures to solve different variations of the R1Q problem.
The tribes that are responsible to expand the boundaries of human knowledge are called scientists, inventors, innovators, and engineers. When I was in high school, I wanted to become a scientist. I thought being scientist by itself is a different profession. I did not know that traditionally most Professors are scientists. Though there have been lawyers, book binders, politicians, poets who were scientists but majority of the scientists are Professors. When I was working in IBM I saw that there was absolutely no research that was done as part of the job (excluding research labs). When I say research, I mean deep thinking to invent something completely new and not just to get some small ideas. This is only possible in academia, research labs and top-level hierarchy of some companies. Therefore, I decided to pursue a PhD program in algorithms as I thought a PhD would give me a proper formal training in research and that too in the sexiest subject, algorithms.
Ideas, observations, algorithms, concepts, implementations, proofs, and experiments should be published. Publishing the inventions / discoveries is one of the biggest inventions of mankind. Simple concepts such as farming, raising pets, knowledge about a few trees and animals was easily passed on to next generations. But, complicated ideas of mathematics, biology, physics, administration, war strategies, grammar, principles of drama, dance steps etc could never be remembered. Hence he discovered the idea of publishing. Publishing is a way to create a written (or some other) record of the ideas. The ideas can be published as books, papers, reports, articles, pamphlets, patents, blogs, newspapers etc. This way he could record his thoughts for generations so that the people from future need not reinvent the already discovered / invented stuff. For the same reason, I write my blog to publish my thoughts and experiences and we were able to publish our first research paper.
Our First Research Paper
I was pretty excited to publish our paper because the problem I worked on was so simple to describe to anyone, looked like a puzzle, and was so fundamental in nature. Unfortunately, our paper was rejected again and again in top conferences for the reason that reviewers thought though the problem was nice, solutions were non-trivial and interesting, the solutions used standard approaches or methods to solve the problem. The paper was rejected four times in top conferences.
I was pretty disappointed when we got rejects for the first two times. Then my God-adviser Rezaul gave me one lesson that changed me for eternity. He said “Getting rejects is good”. I was curious to know the reason for his opinion. He said “Rejects keeps us humble”. I was totally blown away for his simplicity and humbleness. Ever since I do not give a shit for the results of the papers. Probably I would be happier if my paper gets rejected. That gives us an opportunity to improve the paper, learn from the mistakes, and accept every type of consequence with equal humility.
We submitted our paper to a high-level (but definitely not top) conference called COCOON. I was expecting a reject but luckily it got accepted. Thus I got my first real research paper by the grace of my God-adviser Rezaul.
There are two types of venues to publish papers in computer science: conferences and journals. A paper that gets published in conferences are generally short, say around 10 pages, gets reviewed comparatively faster within 4 months and the published papers should be presented in front of the authors of the other published papers. On the other hand, journals are the de facto standard for publishing, are longer say upto 200 pages, having longer review time, up to 3 years for complicated papers, and there will be no presentations to be done. As my first paper got accepted at a conference, I had to present our paper at the conference held at Georgia State University, Atlanta, Georgia on August 4 – 6, 2014. This was not the first time I was presenting the paper. I had already presented 10+ times on several topics in several colleges / universities in Karnataka, IBM competitions, Stony Brook University, University of Maryland, and MIT. I was bored for having given presentation related to our paper four / five times and was not keen on the presentation. Still, I prepared for it. Everything seemed fine and I got ready to leave to Atlanta on August 2.
It was the day of my travel. I had booked a flight from New York City to Atlanta on August 2 at 1 pm. It was raining heavily on that day. I left very early and got the 8:40 am train. The train came to a halt at some station as there was an accident in the next train station. It was an unconditional wait. After 45 minutes the train continued. As I had planned for two hours of buffer time I was saved from missing my flight. I reached the airport. It was time to get on the flight. When there was 20 min left for the departure there was an announcement that they were looking for volunteers who can travel on 5 pm flight and they would give $600 gift voucher. No one volunteered. After 10 more minutes they again called out if there were any volunteers and they were willing to give $800 gift voucher. I thought it was a good way to make some quick money (in a legal way) and agreed. I got $800 amazon gift card for free. The next flight was at 5 pm i.e I had to wait for four more hours.
During the wait, I walked and thought and talked to myself about the greatest educational company of India that I would be building around 2021. I also spent some time looking into a few mathematical puzzles. The time passed quickly and I boarded the 5 pm flight. As we (other volunteers and I) had volunteered for this flight, we were given a first class seat. For the first time in my life I sat on a priority / first class seat. The seat was wide and comfortable. There was enough space for the legs to move. Within five minutes of being seated we were served. As I love one of the best inventions of mankind, i.e., alcohol, I drank vodka and red wine and got a mild high. Detailed blog post on this greatest invention some other time. There was no vegetarian food as I had not ordered it before boarding. I kept looking into the clouds, skies, and oceans through the windows. I got several pictures of them. Traveling on flights is one of the nicest experiences I had in my life. My thoughts and experiences of around 20 flight travels in a future blog post.
I landed in Atlanta at around 7:30 pm. The Atlanta airport was very big and nice. I read somewhere that it is one of the busiest airports in North America. The design and style of the airport was sophisticated. I took a Marta train to Peachtree station for $2.5 and got into my room in a hotel called the Ellis hotel.
The next day, Aug 3, was a Sunday. I left my room early to roam around the city. There were lots of blacks in the city. There were lots of beggars everywhere: in the parks, on the streets, near the company buildings, literally everywhere. The food prices were expensive. Even the stupidest 10 gram breakfast would cost minimum $10. Because of the city being so expensive and lots of beggars I did not like the city. My plan was to visit Georgia aquarium as I loved water, sea animals, and aquarium. I had breakfast at a restaurant that was near to the aquarium. Then I realized that my camera Canon Rebel T5i’s batteries had drained completely. As I did not want to visit the aquarium without using the camera I returned back to my hotel to change the batteries. I thought of bunking the third day of the conference and visit the aquarium. I charged the batteries and in the evening I went to the Centennial park and spent hours of quality time watching kids play in the water fountains and sprinklers.
It was Monday. I had to give my first conference presentation as a PhD student. I wore a suit for the first time in my life and got ready. I left to Georgia State University where the conference was held. The talks started. I could not listen to the morning presentations as I was preparing for my presentation to be given in the afternoon. At 2:20 pm I gave my talk and answered two questions in around 20 minutes. The talk was ok. I was pretty confident that the audience would remember the problem statement of my talk even after six months because I drilled them with the problem statement again and again.
The same day I was also a chair for a session. A session is a collection of 4 or 5 papers related to the same topic. I was the chair for computational biology and computational geometry. A chair introduces a speaker to the audience. He keeps track of the timings for the presentation. Ideally, a chair should let the speaker know of the time after 10 minutes, 15 minutes, and 19 minutes during a 20 minute presentation. This is to make sure that the speaker does not overshoot the time limit by a large extent. If the speaker finishes a presentation in the time limit then the audience can ask the questions. If the speaker overshoots the time limit the chair asks the audience to take their questions offline due to time constraints. If nobody asks any questions then the chair asks one or two good questions. Knowing the rules of the game I tried to enact my role in that drama as a chair. It was a nice experience for me. The day came to an end and I was free from all tensions of presentations and chairing.
The first day I was busy with presentations and chairing. The third day I was planning to bunk the conference. The second day was my only hope to listen to some talks. I focused my attention and listened carefully to the talks. Some ideas were really nice. Most of the talks were dead-boring. I have a serious problem that if the talks are bad, I get headaches. So, to avoid that I was mailing my best friend during the middle of the talks.
It was lunch time and I went to get my lunch. There were two or three boxes of vegetarian food out of 50+ boxes. Grabbing a veggie box I went to a nearby table and started eating. There was a Chinese girl sitting near the end of the table and reading something. I introduced myself and waited for her reply. I believe she replied her name as Na. Then I asked her if she had already presented her paper and asked her about her research interests. She replied that she presented her paper on the first day. But, she could not understand my words “research interests”. I tried to tell her different phrases in different ways but could not make her understand what I was saying even after five or six attempts. She asked me sorry because she had problems with English language. Initially I was irritated by the fact that she was not able to understand even though I spoke clearly. When she apologized for her problem in understanding English, I got melted away literally, felt very sorry for her, and started hating myself for getting irritated. Then I used a totally different strategy to communicate to her. I wrote my questions and sentences on the Atlanta map and she replied me in words thinking about every sentence. I told her not to worry that she would be wasting my time and that I had all the time in the universe to listen to her. She was quite happy. Then she said she was working on theorem provers and formal logic. When she asked me about my future plans I told her in detail (of course in writing) about the greatest educational company of India that I would be building in a couple of years. She was quite impressed. We talked for 30+ minutes. She was nice.
That day evening there was a banquet for all of us. A banquet is a get together dinner party where people meet and eat. I met several Indians there. Ramanujan was from Bergen, Norway, Akanksha was from IISc, Sujan from IIT, and Gaurav from France, and Satheesh from Georgia State University. They were working on different fields such as parameterized complexity, circuit complexity, probability, NP completeness etc. We had some stupid food and then chatted a lot. We brought into the discussion table the topics such as politics, difference between US and India, Norway, research, and other topics. When we finished we had spent a couple of hours already and it was late evening, say, around 8 pm. Before parting ways I got to know that Akanksha was put up in the same hotel as mine. When we were discussing plans I told her that I was planning to bunk the third day to visit the aquarium. She said even she was uninterested in the talks and was looking for a company to roam around the city. Then I was happy that I had a company to see places. We decided to leave to Georgia aquarium the next day early morning.
That night we went to the Centennial park, watched kids playing in the fountains and sprinklers, and talked about each other. Akanksha had completed her masters degree from IISc, Bangalore. She had done her undergrad from Chattisgarh. She was damn innocent, almost muted out (I mean very less talking person), typical Indian traveling- and food-loving girl. She had come to the US for the first time. She liked sports a lot and she was learning kung fu. I was dumbstruck when I got to know that she was learning kung fu. I had only seen kung fu being performed in Kung Fu Panda movie and I was with an Indian girl who was trying to master kung fu. I felt very happy about that. Girls should learn martial arts for their safety and defense and sometimes to beat innocent guys like me for no reason. They can learn martial arts either from a class or at home. Just to test if she was not bluffing I asked her to beat me. She gave me a tight knock on my back. Ui ma!!! It was funny and scary at the same time. For a moment I was afraid if she would beat me black and blue if she gets upset about me for unknown reasons. But, I think she was too innocent to even know what upset means. :)
As planned, Akanksha and I left for the aquarium the early morning. We had our free food at the conference and left to the aquarium. On the way I cracked a couple of jokes (a typical thing boys in 20s do in front of girls) not to impress her but to make her happy. I feel happy when I can make someone smile / giggle. I think she was similar to my mom. Both of them rarely smile as if they have to pay $200 fine for giving a smile. Anyway, it was fun and I did a couple of pranks on her taking advantage of her innocence. :)
I was pretty excited to see the giant aquarium as I loved animals, water, and nature. When we entered the aquarium my first feeling was ooooohhhhhh…. I was so so so happy that I wanted to kick someone. I saw Akanksha and smiled and immediately at the thought that she was a kung fu expert and a fighter girl, i stopped smiling and turned my face. She asked ‘What?’. I replied ‘Nothing’ and we progressed further.
I saw an open area where there were sting rays and small sharks. We could touch them gently with our two fingers. It was so awesome. I loved seeing those amazing creatures moving in water like the jet airplanes. I wanted to swim like them too. Then we went to a section where there were lots of fishes. One aquarium had more than 300 different colored fish taken from a single pond in Africa. We could see a few crocodiles swimming in the aquarium above our head. Continuing forward, there were piranhas on one side. Sea horses, dragon fish, tiny fish smaller than the size of the smallest pill, giant fish, fish that did not move even after minutes, etc. God, so many types of fish. It was a festival for my eyes.
Next was the legendary tunnel of Georgia aquarium where one can see whales, sharks, fish, giant sting rays etc. It spanned 180 degrees above our heads. I took tens of videos in the aquarium there as I believe videos have more life than pictures. Though I was a bit sad that the animals were not in their natural habitat and even thousands of gallons of water for them would be like a small cage for a lion. Then I realized that in another perspective this saves them from poachers, hunters, etc. And it is quite certain that the probability of they not being killed by some other predators is 100% at the aquarium.
We went to the section of penguins where every penguin was attached with a colored ring. When I asked for information, they said that the male and female penguins are indistinguishable from each other and only a DNA testing reveals their sex. When someone wants to take a penguin out to some other location they have to take its partner too as they pair for lifetime. Then we moved to otters. The otters looked like seals but they were different. The otters are smaller in size (compared to seals), have rough skin, and they eat food equivalent to 25% of their body weight. There was one beautiful girl explaining about them. I asked a simple question and she could not answer properly. To see her cute face again and again I asked her lots of questions and I did not care for the answers. In fact, I wanted to know the answers. I could see her lips moving but no sound reached my ears. And poor Akanksha thought I was genuinely interested in knowing about otters. Ha ha ha.. :)
How can I miss it? It was one of the most amazing shows I had seen. We went to a theater where there were hundreds of people already seated. We got two great seats in the exact center of the theater. There was a large deep pool in front of us. Behind the pool was a big screen and some stairs in the middle. Photos / videos were not allowed. The show started. I opened my eyes and mouth wide open and focused totally. A small 2 min intro was given about our hero. Our hero, long long ago while traveling on a ship was captured by sea-monsters (a ship having weird ghostly people) and was saved by dolphins. The story unfolds to the present time and the storyteller (an actor) tells about his voyages and suddenly the sea monsters comes on the screen as well as in reality and captures our hero and chain him in their ship deep inside a tunnel.
The hero and his crew make a master plan of creating sound waves to call for the help of dolphins. He asks our (audience) help in calling for the dolphins. Slowly all of us call for the dolphins repeatedly. But nothing happens. We all call again for the dolphins and within a few minutes the dolphins come (both on screen and reality) from the bottom and jump so high at the center of the pool and make a big splash. The first drops of tears fell from me at that moment. If there was rain on the screen, there was rain in reality. If there was lightning on the screen, there was lightning for real. The dolphins use so many different strategies to attack the sea monsters and knock them down to save our hero. To celebrate this amazing win, our hero, crew, and the dolphins dance together leaving behind the feeling that humans and dolphins are two different creatures. The energetic dolphins go backwards, fall on water on their heads (to go inside the water easily) or on their sides (to splash water), can take a person on top of their nose and the person can be seen half inside the water and half outside and the dolphins move around the pool quickly. I was so happy and emotional looking at them that I cried for them like a baby thinking if somehow I can go into that virtual story or a fairy tale with dolphins and become a story myself. In no time the show ended. With heavy heart we had to leave.
The next show was a 4D show where we had to wear 3D glasses and watch a movie in 3D and the 4th dimension effects were the reality effects such as water sprinklers, winds, breezes, color paper flying around etc. The movie was to show the importance of sea animals. Before the movie started there was a funny incident to prove the innocence of Akanksha. When she wore the 3D glasses she said that the glass had a problem and she was not able to see anything from her left eye. I replied “3D glasses are like that. So, do not worry.” Then she said either it is her eye problem or the problem with the glass. I thought that there might be a dent in her glasses. So, I gave her my glasses and took her glass. She became silent. I asked her “Is it fine now?” She replied in a worried manner “I think I have a problem in my eye. Even from this glass I am not able to see anything through my left eye”. Then I replied “Sweety, even I am not able to see properly from my left eye. Once the movie starts you will not feel like that. As I said earlier 3D glasses will be like this. Most 3D glasses have separate colors / effects / materials for the left and right glasses. So, do not worry. Just enjoy life”. I also explained her some varieties of 3D glass technologies. Then she was happy. Innocence at its best. :)
The climax was a giant aquarium where one could clearly see whales, sharks, giant sting rays, fishes etc. The room was lit by a gold colored light. We sat there on the steps covered by a smooth carpet for an hour or so. I was so happy that it was one of the nicest moments in my life. I thanked the supreme energy of the universe for a romantic experience. As Akanksha was crazy for pictures for uploading them as profile pictures I considered her as a supermodel and took hundreds of pictures of her. During the course, I conducted all my photography experiments on her. It was nice. Though reluctant, as per her insistence I had to leave the aquarium due to time constraints. We entered the aquarium at 10 am and were leaving the aquarium at around 6:30 pm.
Then we went to Georgia Institute of Technology, where a fountain was good. Apart from that, the campus was crap. We lost our path to the hotel while coming back due to the mistakes of both. In fact, it was my mistake majorly. Throughout the walk for hours I tried to cheer her up as she was a bit sleepy, a bit tired (she looked as if she was drunk), a bit mad at me for having messed up with the routes. I tried to apply exact algorithms to find the shortest route (in traveling salesman problem exact algorithms take exponential time) and she was trying to apply approximation algorithms (in traveling salesman problem approximation algorithms take polynomial time) and it was total fun. I like when a girl smiles and when a girl gets angry (of course it depends on girls too). For me, girls are like flowers. They are delicate, smooth, lovely, innocent, and cute. :) Finally, after lots of walking we reached our hotel. I gave all her solo pictures to her not keeping a single copy of any pic. The day came to an end.
The next day I got ready to leave. I met a server in the hotel restaurant named Joseph who had served my breakfast during the day of my presentation. His service was so amazing and we had chatted for at least 30 min. When I had forgot to take my credit card back he had honestly returned back my credit card to the hotel management. I met Joseph and for his goodness I gave a small token of $10 (I know, it is too less) and took a picture with him. I took Marta train to airport, flew from Atlanta to New York City, boarded train from NYC to Stony Brook and in the late evening was at my home. Wrote this big blog post at various places such as West Meadow beach, room, etc.
I am so so so happy to have got my first real research paper by the grace of my algorithm master, research guru, and God-adviser Rezaul Chowdhury. Hoping to learn more research, more algorithms, and more lifing from him. I wish everyone the very best. Chase your dreams. Enjoy life. Tata. :)