akrish

My algorithms professor used to tell his students (including me) this story to motivate studying NP-complete problems and reductions. The story goes something like this: say you’re working as a software developer and your boss gives you this project where you need to come up with a efficient way to do some computation. You go to your desk and think about for awhile and then suspect that there is no efficient way to do the computation. So you can’t just go back to your boss and say, “I think this problem is NP-Hard, so I give up,” you need to show your boss that it’s NP-Hard and this motivates the studying of reductions. It further motivates the study of approximation algorithms and other techniques to cope with NP-Completeness.

I’ve heard this story a couple of times from my professor, but I never really felt like this is something that would happen. How often is it that you are given a problem that doesn’t look intractable immediately, and how much convincing will your boss really need? For that matter how often, in a typical job, do you encounter intractable problems? Like how often does this really happen at a typically development job? Now I haven’t spent too much time in industry and really in my time I never ran into NP-Hard problems so I don’t really know. Although the story was motivational for an algorithms course, the situation used to seem implausible to me. That is until I was challenged to do this myself

This summer, I’m working in a computational genomics lab refining some algorithms for analyzing gene expression data. The core problem we are working on is NP-Hard, but in my refinements, I ran into another NP-Hard problem that I did not immediately see as intractable. I guess this story may be a little bit skewed because I am basically doing algorithms research but I still thought it was pretty cool.

My work deals with finding connected components in a large gene network (an undirected graph). To simplify things, we have a scoring function and want to find connected components with good scores and because of the scoring function this turns out to be NP-Hard, read this for the exact problem and why it’s NP-Hard (The exact problem is a generalization of set cover). Anyway, the basic way we do this is to pick a vertex with a “good” score (called the “seed”) and then expand the module from that node.

In our experimentation, we decided to see what would happen if we allowed seeds to be multiple disconnected nodes and grew our modules from these multi-node seeds. Basically, here you choose k nodes to be your seed and you grow the module out from these seeds, but it is not a requirement that the result is a connected component, in this case it is ok if the resulting module consists of k connected components. The motivation was that from a biological perspective, a disease may affect two or more gene pathways and we wanted our algorithms to be able to account for that, hence allowing multiple connected components.

I set out to implement this feature and was thinking about ways to create these multi-node seeds. I started out by filtering away all of the “bad” vertices and was left with a set of 30-50 good vertices but it was (and still is) not clear what’s a good way to combine these single seeds into multi-node seeds.

My first approach was to simply enumerate all of the combinations and then choose the ones where the individual vertices had good scores. This approach besides having exponential time complexity was bad in that the seeds we selected were all very similar. This was because the individual nodes that were very good were in all of the multi-node seeds we selected. Thus this approach was not satisfactory. Another problem with this approach was that we typically did not see disjoint connected components in the resulting solutions.

To remedy the last problem, we decided on a new approach where we select multi-node seeds where each individual vertex is far from the rest. We compute this by looking at the neighborhoods (typically only 1 level of breadth first search) around each seed and computing the intersection of these neighborhoods. So this seemed like a good approach and we were hopeful this would produce disjoint connected components in the results so I set out to implement this.

Lets restate the problem: Given a set of vertices in a graph, where each vertex has an associated set of elements from some universe U. The goal is to find k vertices that minimizes the intersection of the sets, or such that the intersection of these sets is the empty set.

I thought about this problem for awhile and was quite confident that it was intractable. Before talking to the grad student I’m working with about it, I wanted to have at least a sketch of a reduction in mind. My first reaction was that I should be able to reduce set cover to this problem, possibly by “negating” all of the sets or something. I messed with this for awhile and I didn’t really get anywhere.

I mentioned this problem to some other people in my lab and we all thought about it for awhile. Eventually one guy found that he could reduce independent set to this problem quite easily. If you instead go back to the gene network graph and consider each of the “elements of the universe” as neighbors of the vertices in the graph, then you immediately see that this is the independent set problem. If you treat each neighborhood as a node in a graph, and there is a edge between two neighborhoods if they share an element in common, then you can solve this problem by running an independent set solver on this graph. Conversely, given a graph, you can define a universe of elements and a set to each vertex such that vertices that are not connected share no elements and vertices that are connected share some elements. Then you can look for multi-node seeds and solve independent set. The way I explained the problem above, and the way that I thought about it made it difficult to see that it was independent set, but if you go back to the original problem, it’s easier to see.

Now that I new the problem was NP-Hard, I started thinking about ways to get good enough multi-node seeds and eventually settled on a greedy algorithm that grows the seed sets by adding the node with minimal intersection. The resulting seeds are decent and we did start seeing solutions with multiple disjoint components which is exactly what we were looking for. Despite being faced with a “challenging” problem, we did end up finding a good working solution that gave us the results that we wanted.

This little anecdote, although quite silly in retrospect (because the reduction was pretty straightforward), really showed me that what I learned about reductions and NP-Completeness is important from a practical perspective. It also showed me that my professors story was actually quite plausible. Plus it was another situation where I got to apply things that I learned, and I always find that really cool.

Everyone speaks hebrew as their primary language here in Israel, and in interacting with people, I’ve noticed a couple of interesting things about languages. Almost everyone CAN speak english, but it isn’t their natural language (it’s kind of like how after only 6 years of studying spanish I CAN speak spanish, but in speaking spanish with spanish people I’ve met here, I’m not very effective at communicating in the language). I don’t have a hard to getting things done here because most people do speak English pretty well, and if they don’t, then there are always people around that can translate. However, in an environment where very few people naturally speak english, it is much harder to connect with people.

Given that I do spend some time in difficult interactions, I’ve been thinking a lot about languages in a variety of lights. Politically, languages can be a uniting factor (like it is in Israel), or conversely in can hinder unification attempts (like in India). Socially, speaking a different language from everyone else does have negative consequences on your relationships and interactions. And lastly, technically, the language that you think or operate in may close your mind to new ideas.

Language as a political tool
When you think about it, Israel is not incredibly different from India. Yeah, India is a much bigger country geographically and population-wise, but both were under British rule until the mid-20th century, both gained their independence around that time, and both are now relatively modern democratic nations (Israel more so and probably India less so). Further, Hinduism and Judaism are two of the oldest religions and both countries have rich ancient histories. Ok, so there are a lot of differences, but one I found interesting is about language, and how it affects the political environment.

There are tons of languages in India and although Hindi is the official language, unification did not come easy. Now, my view is that most kids in India, while knowing Hindi and their native language, are also very good (almost proficient) at English. I haven’t been to India in years so I could easily be wrong, but a lot of Indians come to the US and speak well enough for me to think this. I found some sources that counter this claim, but my friend Vivek, who lived in India for a couple of years recently supports me (but he went to an international school so…). And of course all of my Indian-American friends pretty much “know” just one language, and if they aren’t from an historically Hindi speaking area, it usually isn’t Hindi.

In contrast, in Israel, EVERYTHING is done in Hebrew (Ok that’s not entirely true, a lot of people speak Arabic and you do see street signs in Arabic). Since Israel was founded as a Jewish nation, there weren’t any real problems with making Hebrew the official language (except for the Arabs that were living here). All of the Arabs that I’ve met speak Hebrew fluently now, so here, everyone who calls themselves Israeli is fluent in Hebrew.

In Israel, practically everyone operates in Hebrew, and as a result, there’s more of a national sense of pride here. In India, I feel like this pride is lacking and the diversity in languages seems to correlated. The fact that it is much harder to settle on a national language in India is evidence that India is really diverse, and this diversity leads to less national pride. In Israel, not only does everyone speak Hebrew, but they are the only country where people speak Hebrew. If I were Israeli, hearing someone speak Hebrew would give us an immediate connection, just because we are both Isreali. One of my lab-mates was traveling in Europe with his family and another Israeli group overheard them speaking in Hebrew and the two groups started talking, simply because they shared this language. When he told me the story, he used the words “sense of national pride,” hopefully supporting my point.

Aside: While I’m here, I do the same thing with people speaking English. If I hear some one speaking English with an American accent, it’s an immediate connection.

So it’s pretty obvious that language is an indicator of how diverse a country is, but I never really thought that it could contribute to national pride.

Language as a Social Barrier
So even though I don’t speak Hebrew, I can communicate well enough to get things done here. However, I’ve noticed that I do miss out on a lot of things. As an example, I play Ultimate here and everyone that plays speaks English really well (In fact, many of the players spent considerable time in the US), but they naturally speak in Hebrew. So one time, there was a foul call that lead to an argument (as it is guaranteed to do in Ultimate), but this time the argument took place in Hebrew. I didn’t see what happened during the foul, but I couldn’t even figure it out by listening in. I could only decipher what happened by listening for tone and interpreting body language, from which I only learned a bit about the incident. After the uproar had died down, I asked what happened and was given a good explanation, but in the heat of the moment I could not participate.

Also, I went to a party this weekend and I found it really hard to interact with people. Of course everyone spoke English pretty well, but over the din of the music and in that kind of a setting, most of the people I talked to seemed reluctant to talk to me. Basically, people don’t want to have to think really hard to speak to someone at a party, so conversations are short and I didn’t really meet that many people. The party was still fun, but I definitely felt that I was at a social disadvantage by not speaking Hebrew.

In both of these situations, I felt left out of an experience because I don’t speak the native language here. Of course, if two people don’t speak the same language at all they are unable to connect, but here it’s hard (though not impossible) to connect with people even if they are quite familiar with English. You can have a conversation and build relationships, but it’s hard to share a lot of experiences without a common primary language.

Language as a mental prison
Ok that heading sounds a lot worse that what I’m going to get at. For my first week here, my parents and I sublet an apartment from this guy in Tel Aviv. When we met him, he was really nice and helpful, and in talking to him, I noticed that he used the participle verb form a lot, and in places that I (or other english speakers) would not use it. For example, he said something like: “When I am taking my bike to go somewhere, I usually am not leaving it for long, because bikes get stolen here.” A native English speaker would probably have said: “When I take my bike to go somewhere, I usually do not leave it for long …”, instead of using the participle form.

I noticed him say it a couple times and I’ve noticed a lot of Israeli’s use the participle in unconventional ways since then. A couple of days ago, I asked a friend about it and she said that it’s because in Hebrew they don’t have a participle form, they just have present, past and future. So, when people think in Hebrew but speak in English, it’s hard for them to figure out when to use the vanilla present tense and when to use the participle, resulting in unconventional uses.

So, I started thinking about how language affects how you think, and here’s where the article takes a technical turn. I think in English, so I’m sure my mind is constrained in certain ways that would not exist if I thought in a different language. Obviously, since I don’t think in another language I don’t know how that would be, right? And similarly, people who think in Hebrew are constrained in different ways that I am, like in how they are not sure about participles.

I think this is true for programming languages too. Over the past year, I’ve spent a lot of time programming in Java and Python, and as Java was my first language, it took me awhile to start using some of the more dynamic features in Python. For example, I don’t immediately see uses for dynamically adding a method to a class, and I think that’s largely because I think in a statically typed language. And recently I build a compiler in C++, and when I write in C++, I don’t think to use features like multiple inheritance, because I’m not used to them existing. Basically, the language that you think in tends to restrict how you use other languages, and it may result in you using a paradigm that works well in one language but that is horrible in another.

I’ve been reading a lot about functional programming and have spent a bit (not a lot) of time with Haskell. Everyone says Haskell is “hard” to learn if you’re used to imperative programming languages because you have to change how you think about programming. From this perspective, I completely buy that. It’s hard to get myself to think purely functionally because I’m used to methods having side effects and all of the stuff that isn’t “purely functional.” Since my first programming languages were all imperative, I’m constrained to think in a certain way, and it’s harder for me to think in a different way.

Of course you can get break those constraints, but it takes a lot of hard work in a new environment. With programming languages, I’m sure that if I spend a lot of time with Haskell, I’ll be able to think in the functional way. From observation it seems that the same is true for spoken languages. Of the Israeli’s that I’ve met, the ones that have lived in the states speak english like natives.

And so…
After spending tim here, I’ve begun to understand how important language is from a variety of perspectives. I find it quite interesting and it makes me a lot more excited to finish reading “The Languge Instinct” by Steven Pinker (but I’ve been “reading” it for like a year so we’ll see if that actually happens). I’m starting to think that traveling is really cool because you get to observe these kinds of things only when you dive into a new environment.

I’ve been in Tel Aviv for almost a week now, and will be here for 9 more. I’ll write about what I’ve done this week when I get a bit more free time, I need to organize my thoughts a bit more. Anyway, I’ve been taking a lot of pictures and I wanted a place to share them so I spent a couple of hours adding a photos section to this blog.

I did a bit of research on what photo-sharing tool to use. Notable options where various photo-blogging tools, Picasa, and Flickr. Photo-blogging tools were unsatisfactory because each image is uploaded as it’s own post, and that serves a much more artsy purpose than I’m looking for; I want to be able to bulk upload photos. Picasa seemed pretty cool but there’s a fixed disk space quota that I’ll most likely exceed very quickly, and I don’t want to have to pay for the service. So I rested on Flickr. Flickr so far has been pretty cool; there’s a 100Mb a month quota, which I’ve already exceeded for May, but you get effectively unlimited space if you’re patient.

So I uploaded a bunch of pictures and now I was looking for a good way to add them to akrish.net. I ran across this wordpress plugin that pretty much served exactly the purpose that I wanted. I installed the plugin, ran into a bunch of difficulties that took way to long to fix, and eventually got the plugin running. Then I updated my wordpress sidebar so that you can get to my albums from any of the pages on my blog. Since I ran into a couple of problems, getting this to work made me pretty happy.

Long story short, links to my albums are on the right. There’s only one right now and it contains some of the pictures of my trip to Israel, including a tour of Jerusalem and some of Tel Aviv. As I mentioned, I’m over my quota for the month so more pictures will be up in June.

By the way, let me know if there are any bugs as I did have to do some stuff by myself.

It’s high time that I wrote something about Ultimate; I’ve been playing for this entire school year and I’d say I’ve become kind of obsessed. So obsessed, that I just spent the last minutes (between writing the previous sentence and this one) watching videos of ultimate on youtube. Ultimate has essentially replaced soccer for me. In high school, I was obsessed with soccer, I would watch games whenever they were on (and often record them), I would run and lift weights to improve my fitness for soccer, and of course I played competitively for a club team and for my high school. This year, I’ve been watching ultimate videos whenever I get free time, I train for ultimate and I played for Thugmo (our Men’s B team).

I have a decent amount to write about with regards to ultimate (of course keep in mind that I’ve been playing for less than a year) and I’m sure there will be many more posts to come about the sport. For this post, I wanted to write about throwing. During the year, I usually spent a couple of hours a week outside of practice just throwing a disc around with a couple of my teammates. I attribute a lot of my improvement over the past year to those sessions outside of practice, as I’ve noticed that my throws are significantly better than they were at the beginning of the year. My coach also repeatedly told us this: throwing is the best way for a new ultimate player to get better.

One thing that I really like about throwing sessions is that you get to goof around. At practices, I spend most of my time working on my real throws, the ones I’d use in games. When I go out and throw with my teammates, yeah we work on real throws, but we also work on stupid throws. Like today, we started out normally, throwing standard flicks and backhands, then started mixing things up with high release throws and upside down throws. Finally, we played a 4v4 scrimmage with only left handed throws. It was really fun, but I’d argue that the scrimmage wasn’t all that beneficial.

There is some benefit to the goofing around though. Some of those throws are really useful (especially hammers and high release backhands), but practice and tournaments aren’t the place to perfect them. That’s where throwing sessions come in. You get to work on the throws that you don’t have, and get them to the point where you feel comfortable throwing them in games. I’ve been working on my high release flick and my left-handed backhanded, both of which I feel can be useful short-distance throws, and I’m almost at the point that I’m willing to throw them in games. The same can be said with my hammer. Throwing sessions have really increased the types of throws that I am comfortable with.

From another perspective, as a overworked student, throwing is a great break. When I was a freshman we used to play soccer as a break, but for soccer you need at least 6 people. With ultimate, you can have a pretty good time with just one other person, and I can almost always find someone on my team who is willing to throw with me for an hour. It’s really easy to organize a throwing session, and I derive a lot of enjoyment from it.

I guess I’m just really excited to be playing a competitive sport again. After a couple of years without it, I realized how much I missed it. Last year, I tried filling the gap with running, but the lack of a close team didn’t cut it for me (although I do still enjoy running). It’s been really amazing to be back on a competitive team.

I’ll leave you with a video I watched while writing this. Enjoy.

If you’ve been reading my old blog posts, the ones from way back, you may have noticed that I have quite a few posts about entrepreneurship. I used to be really excited about starting my own company straight out of college. In my free time I’d read stuff by Paul Graham, Marc Andreessen, and tons of blogs by founders and VCs. I’ve tried to start a couple of serious side projects with some of my friends, and we hoped to turn these into startups when we graduated. And most importantly, one of my dreams was to start my own company. 

Over the last year though, I’ve become really involved in a couple of research projects and my excitement about them has got me thinking about my life direction. Nowadays, when people ask me what I want to do after I graduate (which scarily isn’t that far away), I tell them that I want to go to grad school, get a doctorate degree, and possibly go into academia. If you asked me that question a year ago, I would have said that I wanted to start my own tech company. So why this sudden change?

Well first of all,  I actually don’t think that the two paths are all that different. I’m excited by working on really innovative, leading software/technology, and this property is essential in any research project as well as in any startup (at least to have some core competency). I love the challenge that comes with working on something that’s never been done before, and I definitely want that challenge in any thing I devote myself to. There are tons of other similarities, to name a few: 

• Both research and entrepreneurship have some component of selling your idea to others. With research, you need to get grant money, you need to present your work in a way that will get you published. With entrepreneurship, you need to pitch your startup to VCs, and VCs have to like what you’re doing.
• Both have quite close-knit communities. In research, you largely see the same people at conferences in your area; the grad students and professors that I’ve talked to know a lot of other researchers in their field just by attending conferences. You know who the top researchers are. It’s the same way with entrepreneurs, they have events like startup school as ways to meet fellow entrepreneurs. And of course, you know who the successful people are.
• Both typically involve some small group effort for awhile. With research, you often work in a small group, maybe of 2-4 people. Similarly, when you start a company, you may have 1 or 2 other co-founders and the founders are ultimately responsible for the success of the company. On a similar note, your effort can noticeably impact the success of the company or the research project, largely because there are so few people involved. This is really important to me, it’s one of the things that turns me off to large companies.

So these similarities are all awesome, and the fact that these are also around in the research world made it much easier to change my direction. Of course there are several differences. In a start-up, you have to do a lot more than just build your product; you have to hire employees, interact with VCs and customers, and a lot of the business/managerial stuff. In research (at least as a grad student), you do have to do some of the managerial stuff, writing papers and grant proposals, giving talks about your work (to gain credibility and support in the community), and as a professor the analogue to hiring employees is admitting and advising grad students. So yeah even here there are similarities, but I think this is a fundamental difference between entrepreneurship and research. As a young company, without some of these business skills, it will be very difficult to succeed. In research, your success is much more related to the quality of your work, and doesn’t depend so much on these auxiliary things.

Startups also need to build products, whereas in research, you can often get away with a good prototype. There’s a huge difference here and personally, I hate doing the work to turn a prototype into a product. In research, you just need your project to prove your point effectively, you don’t need your project to be visually appealing and entirely bug free. As an entrepreneur, you do need to spend a lot of time on this, potentially taking away from the core functionality and the level of innovation at your company. I really like this about research; you can focus entirely on the novel aspects of your project, you don’t have to waste time with the stuff you’d need to attract customers.

Now, I think the whole customer thing attracts people to entrepreneurship. They like to measure how successful they are by how many users they have, and yeah it feels great to have people using things that you built (or reading things that you wrote…). But I think there are ways to get this feeling in research too, one way to measure a researchers success is to look at their publications. Even better is to count citations. Citations tell you how many other researchers are looking at and using your work, and it’s pretty much the same measurement of success as the users one.

So research and entrepreneurship have some similarities, but they also have some fundamental differences. I think I transitioned from the latter to the former because I found that I didn’t want to get caught up in all the other stuff that comes with being a founder, I wanted to focus on the new technology. In my research I’m totally able to do that.

Another thing I love about research is that you’re always learning, and you’re always learning really cool things. Honestly, I wish I had the time to read a paper every day. I have a huge list of random papers that I want to read but there’s just too much stuff to do. As a researcher, it’s kind of your job to read random papers to see what other people are doing and to learn about new techniques. I don’t really know if this is around for entrepreneurs. You have to watch your competition but I don’t think you’ll learn much about their core technology. I’m not sure about this (and feedback would be awesome) but my impression is that you won’t experience the same state of perpetually learning in a startup.

Actually, I want to emphasize that last point. The constant learning really keeps me going. I don’t choose my classes because their easy, I choose them because I’ll learn a lot and because they sound interesting. I get really bored by easy classes because I don’t learn anything. I’m taking one of the hardest classes offered at my school this semester, and although it’s a ton of work, I love it because I’m learning so much.

So yeah, over this past year, the classes I’ve taken have pushed me in the direction of research. I’ve become involved in a couple of projects and I’ll be spending my summer exclusively doing research. Not that the dream of success as an entrepreneur has completely faded, but it’s definitely been put on the back-burner while I try to become a successful researcher.