If you read my earlier post you know that I am obsessed with the following open problem :
Is there a logspace algorithm for Graph Isomorphism of bounded treewidth graphs ?
This problem is at the intersection of three of my research interests (graph isomorphism, tree width and space-bounded computation. See my earlier posts (here, here, here, here). Finally, this open problem is put to rest. I proved the following theorem :
Theorem : Graph Isomorphism of graphs of treewidth >= 4 is
-hard.
As mentioned in my previous post Graph Isomorphism of graphs of treewidth <= 3 is known to be in Logspace. Hence the above theorem settles the open question in the negative (unless 
I proved these theorems three weeks back and still trying to motivate myself to write these results in Latex. I usually take my own sweet time to write my papers, especially the single-author ones. There are three stages of working on an open problem :
- Reading lots of related papers. (I enjoy this process)
- Finding new insights, proving new theorems and solving an open problem (I enjoy this more than stage 1)
- Converting the hand-written proofs into latex. (This is the most boring part of research) I hate this stage. It is very time-consuming with zero fun factor. Stage 1 and stage 2 are roller-coaster rides. Stage 3 is like a power cut.
I usually take photos of my hand-written proofs. These are the actual fun memories, not the final publications.
Update (Nov 16 7:00pm EST) : I added a proof of the above theorem in my follow-up post.
I would be very interested in reading this, so please write this down (even if writing it is boring).
I know other researchers who hate writing (“That’s what coauthors are for” is something I’ve heard), so you don’t seem to be alone.
Personally, I don’t find it boring at all (okay, except for the parts where I’m struggling with TikZ/Bibtex/ … or minor language issues, since I’m not a native English speaker), but then I’ve always enjoyed writing (whether it is research or not). I don’t need motivation, because I find that once I know exactly what I’m going to write (and I obviously do if I have already proved everything that’s going to be in the paper), I write very quickly. Moreover, I relish those moments when I realise that I’ve proved something worthy of publication, and that gives me a boost for shaping these ideas into something I can communicate to my peers.
Writing stuff as you go — that is, as soon as you have even a minor result, write it in LaTeX — may help smooth the process. Moreover, it forces you to be clearer from the start, and helps you double-check that your brilliant idea is correct. Also, you avoid putting your brilliant paper together in a rush because you just remembered that the deadline of that prestigious conference is two weeks from now.
Dear Shiva,
This result sounds very interesting. Do you prove this for graph isomorphism only or does the hardness result hold for canonization as well?
Looking forward to that manuscript, even though it will be a pain to write!
I don’t have any results for canonization. I will think about it.
P.S. Sorry, ignore that, obviously the hardness result holds for canonization as well! I guess I wasn’t fully awake when I read your post the first time
Yeah, writing is hard, frustrating work. The first 90% of the work takes 90% of the time, and the other 10% of the work takes the other 90% of the time.
So true
Write it up! I know it’s boring writing papers, rather than drawing on whiteboards
(cool examples, by the way – it is interesting to see the test cases used for working out a problem).
Congratulations!
(OTOH, sometimes having one proof all typed up helps me understand things better and prove new variants more efficiently.)
What about automorphism, bounded clique-width, etc.? If there are more theorems to prove with your techniques, you might give yourself a reprieve from writing that paper
I will start thinking about other width parameters.
You are certainly not the only one who finds writing boring. For example, Béla Bollobás (Princeton Companion to Mathematics, VIII.6.II) writes “Research should never be a chore (unlike writing up)”.
Congratulations, sounds like a great result.
I am most interested in treewidth <= 5, because of its relation to molecular graphs. Does parity-L hardness apply there, or something harder? (In other words, how small is "large" when you say that you prove stronger hardness for large treewidth?)
To be precise, I have the following theorem : “GI of graphs of treewidth = t is Mod_f(t)L hard”. Here t >= 4 and f(t) is a linear function of t. I am trying to improve f(t) to t-2.
Shiva, I am getting curiouser and curiouser to read about your result. Write it up when you can.
[...] Comments « Hardness of Graph Isomorphism of Bounded TreeWidth Graphs [...]
[...] Kintali has just announced a (cool!) carry out result that graph isomorphism for bounded treewidth graphs of width $geq 4$ is $oplus L$-hard. Informally, my query is, “How difficult is [...]