A Big Result On Graph Isomorphism

It’s not often that I see excitement from multiple friends in the world of academia. Everyone who appreciates these problems for what they are, and what solving them might bring to the world will be watching on with interest this week – including me!

Gödel's Lost Letter and P=NP


Lszl Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.

Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.

More exactly Lszl shows that Graph Isomorphism is in Quasipolynomial Time: that is time of the form

$latex displaystyle 2^{O(log(n))^{c}}, &fg=000000$

for some constant $latex {c}&fg=000000$. Polynomial time is the case when $latex {c=1}&fg=000000$, but any $latex {c}&fg=000000$ is a huge improvement over the previous best result.

Luca Trevisan already has made a post on this result, and Scott Aaronson likewise. Luca further promises to be in Chicago next Tuesday when Lszl gives his talk on the result—here is the abstract of the talk:

We outline an algorithm that solves the Graph Isomorphism (GI) problem and the…

View original post 555 more words

Visual note taking or data mapping – where’s the App?

brain-note-takingFor a while now I’ve been searching for a tool that doesn’t exist.  Well, at least I can’t seem to find it… yet. Perhaps you’ll join the dots here and let me know if you’ve found/built/seen it.

Let me begin with an outline of the problem that this tool would solve:

“You love giving recommendations to friends for Apps and other cool stuff online, but you always get that “oh, what was it again” moment.  Wouldn’t it be great if you could easily stash URL Bookmarks and simple notes in visual form for easy recall?”

Yes, I hear you scream, just use <insert something you’ve seen/used here>, so let me explain what I have used and why it doesn’t do what I want specifically for the above mentioned purpose.

  • Evernote – love it & use it, but it doesn’t allow you to create a tree, and it doesn’t have a visual interface.
  • Action Outline – bought it at least a decade ago, and is about as close to what I want without the visual interface; quick to use, great tree outliner.
  • Microsoft OneNote – like the other Office products I find it heavy and cumbersome, does too much and still no visual interface.
  • Trello – this is an incredible online “kanban” inspired collaborative tool, but it would be hard to incorporate a visual interface into.
  • Notepad & Text Editors – yes, I’m a hardcore Unix geek from way back, but ASCII art only stretches so far.

My vision for what I imagine to be the perfect software tool to solve this problem would be like this:

  • To understand what a visual map looks like, have a play with the Visual Thesaurus or Visuwords, then come back here.
  • Open your new notebook/datamap document, the first thing you see is a blank ‘node’ – a circle or oval shape that you can click on and type text into, just like iMindMap.
  • You can paste a URL into the node and maybe you’ll get some metadata from the page, like Title and Description, or maybe even a Thumbnail appear.
  • When you want to expand out from there, just double-click (or maybe there is a small + symbol) that creates a new node that is linked to the previous one (its parent).
  • As you add nodes to begin with it might not make sense, there’s no structure and that’s just okay.
  • But as you add more nodes, some will “match” existing ones, so you drag one onto another and are prompted to give that similarity a name, which creates a new parent and joins them underneath.
  • Grafting of entire sections of nodes is as easy as drag and drop.

My research notes on this, which I have re-visited several times over the last couple of years, reveal this collection of visual mapping and related websites, SDKs and APIs, so if you’re going to build this amazing tool maybe this is a head start for you 🙂

Now, as luck would have it, as I was writing this post I stumbled across a tool called “The Brain” which I am now trialling.  It is absolutely the closest thing to what I imagine so far, but it’s a bit on the expensive side.




Recycle Your Batteries at ALDI Supermarkets

A friend of mine recently told me that you can now recycle old batteries at ALDI Supermarkets, which is good to know.  Battery recycling is something all of us should be doing, and as more and more gadgets get replaced with new ones, the problem just keeps getting worse.

At the moment, apparently ALDI are only accepting rechargeable and non-rechargeable AA, AAA, C, D and 9V batteries, but if you have other types of batteries you’d like to recycle, there is some information available for households from resourceSmart an initiative of Sustainability Victoria.

Also, for more information about Battery Recycling check out what Planet Ark are doing as well. 


About Battery Recycling

Each year, over 300 million household batteries are thrown away with ordinary waste, meaning a staggering 8,000 tonnes of batteries end up in landfill.1

Over time, the chemicals in these batteries may be toxic to the environment, potentially harming wildlife and affecting surrounding soil or waterways.

That’s why ALDI, proudly supported by Planet Ark, has become the first supermarket in Australia to offer a free recycling service for household batteries in every store.

By supporting this program you’ll be doing your part to help reduce the thousands of tonnes of batteries which end up in landfill each and every year.

Thanks to @dabrown72 for providing me with this information.