Babai’s Updated Results–Graph Isomophism Still Solved in Quasipolynomial Time

Many days overdue on this post but I felt obligated to post this for posterity’s sake (even at woefully so late a time) because the previous post on my blog no longer holds. Laszlo Babai has (since 9 days ago…) posted a fix to his timing analysis so that his graph isomorphism test now once again runs in quasipolynomial time. You can see the announcement here and the updated paper here.

Here are also a short blog post written by Harald Helfgott and his article on Babai’s algorithm for solving GI in quasipolynomial time. The article is currently written in French but it looks like it might be translated into English soon.

Posted in Algorithms, Math | Tagged , | Leave a comment

Babai’s Result: Still a Breakthrough — Gödel’s Lost Letter and P=NP

Even after today’s retraction of quasi-polynomial time for graph isomorphism László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasi-polynomial time. Today Laci posted a retraction of this claim, conceding that the proof has a […]

via Babai’s Result: Still a Breakthrough — Gödel’s Lost Letter and P=NP

The original letter explaining the retraction of the quasipolynomial claim can be found here. As explained in the blog post above and in the letter, the modified subexponential result is still very significant.

Posted in Algorithms, Math | Tagged , | Leave a comment

Where has the time gone? (Part 2)

It is once again that time where I bemoan all the months that have passed since my last blog post. True to character, it has again been 8 months! 8 months! I think along these 8 months, I’ve lost some of my original motivation for starting this blog in the first place, which is wanting to share things I find interesting (mostly TCS but I swear I have other interests also). But here’s to bringing it back and here’s to introducing some new topics that are (*gasp*) not math! Here’s the intended changes for the new year, that will be soon upon us.

  1. More math! I just started being a PhD student…finally! With everyday bringing in more exciting topics and things I learn. So expect more rigor and more math. And hopefully still simplicity (or pseudo-simplicity…).
  2. What I’m reading. Here’s to experimenting something different. I’ve never really posted anything about what I’m currently reading. But I like to read. And I have opinions. And this is a blog. So these things seem to complement each other in ways I haven’t considered before. I’ve recently started reading Blind Spot: Hidden Biases of Good People which I’ve heard mixed reviews about (mainly whether it offers more insight than what’s standardly known by people interested in this topic). I guess we’ll see what my opinions are shortly!
  3. Athletics. Music. Art. I have this unfortunate penchant for learning new things much more than mastering old subjects (which I’m also trying to be better at this new upcoming year…) Seems like resources I find helpful in learning said new subjects might be useful to other people. In this aspect, I’ve started learning the ukulele–maybe also guitar–so expect good ukulele tutorials from the web. Also, as I try to hone my very mediocre skills at the drums, piano, and viola–also expect things on these topics. Also, I’m trying out the bootcamp life (or pseudo-one-hour-long-bootcamp) so perhaps I’ll also post some exercise things.
  4. Life. Maybe I’ll talk a bit about life as a PhD student. And maybe thoughts about the process and the institution.
  5. MIT. It’s about time I write a bit (just a tad bit) about the place I’ve now spent close to 6 years at! And still loving every minute of it.

So now that I’m setting a goal to discuss all and everything that is interesting to me at the moment (and hopefully also interesting to you or you wouldn’t be here, would you?), I’ll hopefully be able to keep a more regular posting schedule. Here’s once again to a new year and a new blogging initiative!

 

Posted in Thoughts | Tagged | 1 Comment

Where has the Time Gone?

Hello 2016! As WordPress politely informed me today, it’s been 8 months since my last post! 8 months! Where has the time gone? I would say I’m again making a New Year’s resolution to blog more, but it’s no longer January…no, not even close. It’s already April!

On my end, the past 8 months was full of agonizing over grad school essays, mad rush towards writing results, mad rush to submitting applications, and, finally, a month of waiting and more waiting, which I say is probably worse than all the rushing and stress of the months prior. But it’s April! And I have a host of amazing, amazing schools to choose for grad school. But then, in typical fashion, comes a month of worrying over choices, of comparing every minute detail between the schools. But no more! I will be going to the place that will best fit my research interests, where I will hear about problems and solutions from some of the best researchers in the field. Where the feeling of excitement over solving hard challenges doesn’t fade, where people work and sleep at odd hours, and where nerdiness prevails. I hope that wherever I end up will make me feel with absolute certainty that I made the right decision by turning my back to the allure of Silicon Valley with all its sparkling glory two summers ago, exchanging that lifestyle for a different type of fun and a different type of nerdy.

But enough about me, to ring in my new New Year’s Resolution (hey, it’s snowing outside so we could believe it’s New Year’s if we try reaaaally hard), I’m going to talk about some of my favorite blogs. You might have heard of some of them:

  1. Shtetl-Optimized: This is probably the blog you have heard of/read before. But there’s a reason why it’s so popular and a reason why it’s on the top of my list. Scott Aaronson’s humor, very candid discussions, eloquence, and breadth of scientific discussion on his blog is unparalleled. Here’s a snippet of a post he made in January (regarding his daughter’s third birthday): 

    Lily: Why is the world spinning?
    Me: Because of the conservation of angular momentum.
    Lily: Why is the … consibation of amomomo?
    Me: I suppose because of Noether’s Theorem, and the fact that our laws of physics are symmetric under spatial rotations.
    Lily: Why is…
    Me: That’s enough for today Lily!  Link to post

  2. Gödel’s Lost Letter and P=NP: I think I’ve quoted several articles from this blog already. If there is a major scientific breakthrough in computing, then an article will appear on this blog within the next few hours and it is usually one of the most comprehensible and yet informative articles on the topic. This blog has a combination of news-like topics which discussions of esoteric problems in computing. It has a bit of everything, all discussed in an engaging and readable way. Plus lots of puzzles!
  3. FiveThirtyEight: I guess some would say this is more website than blog but it has that blog feel to me. Nate Silver’s great. His analysis is great. I’ve been reading his analysis for the primaries when I should have been working on my thesis.
  4. Terence Tao’s Blog: I usually don’t like very technical blogs (ironic isn’t it?) But Terence Tao explains concepts wonderfully, especially if you want a summary of a long and intricate paper (like the explanation of Zhang Yitang’s work on the Twin Prime Conjecture and related background). Beware, not for the faint of heart.
  5. Theory, Evolution, and Games: I had an interest in evolutionary game theory at some point in the past. I still do, and this blog has some interesting articles.
Posted in Uncategorized | 1 Comment

Four Weddings And A Puzzle

Interesting post about fair scoring with stakes involved. As it is, given rational players, I don’t think the show should exist at all. At least, I don’t see a rational incentive for players to rate other weddings any score other than 0. But perhaps, there’s a way to amend the voting scheme so that there is an incentive for non-zero voting.

Gödel's Lost Letter and P=NP

“Four Weddings” is a reality based TV show that appears in America on the cable channel TLC. Yes a TV show: not a researcher, not someone who has recently solved a long-standing open problem. Just a TV show.
22258_4W_302_Group_1

Today I want to discuss a curious math puzzle that underlines this show.

The show raises an interesting puzzle about voting schemes:

How can we have a fair mechanism when all the voters have a direct stake in the outcome?

So let’s take a look at the show, since I assume not all of you are familiar with it. I do admit to watching it regularly—it’s fun. Besides the American version there are many others including a Finnish version known as “Neljt Ht” (Four Weddings), a German version called “4 Hochzeiten und eine Traumreise” (4 Weddings and one dream journey), and a French version called “4 Mariages pour 1 Lune de Miel”…

View original post 902 more words

Posted in Uncategorized | Leave a comment

Paper and Puzzle a Day 8

Again, I’ve been slightly lax on posting a puzzle and paper a day. Here I am picking up the slack once again. First, a paper. I’ve been reading up on cache-oblivious algorithms recently. Cache-oblivious algorithms are optimal algorithms that do not depend on hardware parameters such as cache size. The paper that introduced such algorithms was presented at FOCS 1999. The paper presents among other popular cache-oblivious algorithms, funnelsort, which stands out the most in my mind. The paper is somewhat math intensive but is a pretty easy read.

Now, the puzzle:

One hundred prisoners just arrived in prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst themselves. Each cell has a window so the prisoners will be able to count the days. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The light bulb is initially switched off. The prisoner may observe the current state of the light bulb. If he wishes, he may toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a strategy that will guarantee their freedom?

The answer to Day 7’s puzzle is the following (highlight to show the answer):

The prisoner who is determined first to go will declare “Red” if she sees 4 blue hats. Otherwise, she declares “Pass.” If she declares “Pass,” then the rest of the prisoners will know that at least one of them has a red hat. Then, the next prisoner will declare “Red” if the prisoner sees all blue hats among the remaining prisoners. Otherwise, the prisoner will declare “Pass.” In this way, only the first prisoner will declare wrong for the only case when all prisoners have blue hats.

Posted in Paper and Puzzle | Tagged , , , | 1 Comment

Paper and Puzzle a Day 7

I’ve been reading up more about hinged dissections and came across a shorter paper than the one I mentioned in my previous post. This paper proves that hinged dissections are PSPACE-hard using a reduction from NCL with some neat gadgets.

Now, the puzzle. This is a puzzle I heard from Rachael Harding and is another variant of the prisoner’s hats puzzles:

Suppose you have 5 prisoners. Each prisoner gets a hat with equal probability of being either a red or a blue hat. The prisoners must guess the color of their own hat. They may choose to say “Red,” “Blue,” or “Pass.” If at least one of the 5 prisoners guesses correctly and no prisoner guesses incorrectly (i.e. guesses the wrong color: “Pass” does not mean the prisoner guesses correctly and it does not mean she guesses incorrectly), then they go free. The friendly warden again allows them to discuss a strategy beforehand. However, before the warden hands them their hats, they must choose an order to be asked what hat is on their heads. Then, the warden will give them their hats and ask the prisoners according to the specified order. The prisoners may hear the answers of the prisoners who answered before them.

What is their optimal strategy for being released with high probability?

The answer to the previous puzzle is explained below (highlight to see):

 

Some figures may be found at http://www.archimedes-lab.org/workshoptangram4.html. The idea is that although the shapes look similar, if you zoom in, the proportions are slightly different. I guess some of you might not like the puzzle as much because the original puzzle figures may not be to scale.

Posted in Paper and Puzzle | Tagged , , , | Leave a comment