Happy New Year

Happy New Year to everybody. I am starting to a new blog on medium to discuss my entrepreneurial experiences and life. Check out my latest blog post titled ‘Happy New Year‘ discussing my life in 2015 and predictions for 2016. I will continue using this wordpress blog to post math-related posts. Follow me on twitter ( @kintali ) to get updates on my new blog posts on medium.

Forbidden Directed Minors and Directed Pathwidth

Today’s post is about the following paper, a joint work with Qiuyi Zhang, one of my advisees. Qiuyi Zhang is now a graduate student in the Mathematics department of Berkeley.

  • Shiva Kintali, Qiuyi Zhang. Forbidden Directed Minors and Directed Pathwidth. (Preprint is available on my publications page)

Undirected graphs of pathwidth at most one are characterized by two forbidden minors i.e., (i) K_3 the complete graph on three vertices and (ii) S_{2,2,2} the spider graph with three legs of length two each (see the following figure).

dpw_minors

Directed pathwidth is a natural generalization of pathwidth to digraphs. We proved that digraphs of directed pathwidth at most one are characterized by a finite number of forbidden directed minors. In particular, we proved that the number of vertices in any forbidden directed minor is at most 8*160000+7. Ahem !!

This paper falls in the “directed minors” part of my research interests. In an earlier theorem, proved in April 2013 (see this earlier post), we proved that partial 1-DAGs are characterized by three forbidden directed minors. In a similar vein, I conjectured that the digraphs with directed pathwidth at most 1 are characterized by a finite number of forbidden directed minors. I assumed that the number of forbidden directed minors is number is around 100. So we started this project in May 2013 and started making a list of carefully constructed forbidden directed minors and tried to extend our techniques from partial 1-DAGs. Here is an initial list of minors we found.

dpw_minors_list

All the forbidden minors we found, looked very cute and we assumed that a proof is nigh. Soon, we realized that the list is  growing quickly and none of our earlier techniques are applicable. After almost an year of patient efforts and roller coaster rides, we proved our finiteness theorem in May 2014, two weeks before Qiuyi Zhang’s thesis defense. It took us 10 more months to get the paper to its current status. So this is a two year long adventure.

I am hoping to prove more theorems in the “directed minors” area in the coming years. The current paper taught me that patience and focus are big factors to make consistent progress. There should be a nice balance between `proving new theorems’ and `writing up the existing results’.

Personalization in Polytopix

Today’s blog post is a quick announcement of “personalization” feature in Polytopix. We added a new feature that allows users to add their (possibly multiple) twitter accounts in Polytopix. The user’s twitter stream is used to personalize and rank the news articles on Polytopix. More importantly, our semantic similarity algorithms will display contextual explanatory articles along-side the news articles in the user’s feed.

Polytopix

Weekly news digest from Polytopix

On popular demand, we added a new feature called “weekly news digest” in Polytopix. Our ranking algorithm picks the top (at most 10) news articles (along with the contextual explanatory articles) from the last one week and emails them every Friday midnight. I will post the details of our ranking algorithm in a future blog post.

If you want to receive this weekly digest, subscribe on polytopix.com

Here is an example from the week  01/24/2015 – 01/30/2015

polytopix-digest

Starting a Startup: Polytopix

I am inaugurating this year’s blogging with some very exciting news. I am starting a startup called Polytopix. I will be finishing my spring semester teaching responsibilities at Princeton and moving to Bay Area this summer to work full-time on Polytopix.

 

Meanwhile, I am actively designing, coding and deploying new algorithms, hiring R&D engineers, working on legal aspects and many more related action items. For the first time, I am using a book (instead of post-it’s) to keep track of my to-do list.

 

I can hear the clock ticking louder and faster than usual, perhaps because I am behind my schedule. According to my original plan (enthusiastically devised during my final semester of PhD), this blog post was supposed to appear in January 2013 !! A bunch of interesting (to say the least) events contributed generously to this delay.

 

What is Polytopix ?
Polytopix is aimed at adding context to news articles by analyzing the semantics of the news events. Polytopix’s algorithms retrieve news articles, categorize them, analyze their semantics and augment them with contextual explanatory articles.

 

Why Startup ?
The main idea of ‘semantic analysis of news’ is in my mind since my undergraduate senior thesis defense in 1999. Back then, I developed a summarization engine using lexical cohesion and information retrieval algorithms. See my very first publication here. Starting from the final semester of my PhD (Spring 2011), I started developing a semantic engine to understand and analyze news, especially financial news. I used it as a stock picker to invest my savings. It performed much better than my mutual funds. This is my first realization of the potential of ‘semantic analysis’. Polytopix applies semantic analysis to daily news articles. I am planning to “spin-off” the ‘financial news analysis’ as a separate startup. More on this, in a later blog post.

 

You probably heard the advice “Do not do a PhD just for the sake of doing it”. The same advice applies (with much more emphasis) to starting a startup. You should only start a startup if you are really passionate to solve a particular problem and you are strongly convinced that starting a company is the best way to solve it. I have all the right reasons to start Polytopix.

 

How do I feel now ?
Well, I am feeling very excited and energetic. The roadmap looks very challenging.
polytopix5