Home » Uncategorized » Graph Isomorphism in Quasipolynomial Time talk, DNA Replication Pictures, and Disappointed Linus

Graph Isomorphism in Quasipolynomial Time talk, DNA Replication Pictures, and Disappointed Linus

Lazlo Babai, U.Chicago Seminar, 10 Nov., Graph Isomorphism in Quasipolynomial Time, here. See Aaronson as well, here.

We outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylog n)) time.

Gen, Decades Old DNA Replication Models Called into Question, here.

“This work is a continuation of our long-standing research using electron microscopy to understand the mechanism of DNA replication, an essential function for every living cell,” explained co-senior author Huilin Li, Ph.D., biologist with joint appointments at Brookhaven Lab and Stony Brook University. “These new images show the fully assembled and fully activated ‘helicase’ protein complex—which encircles and separates the two strands of the DNA double helix as it passes through a central pore in the structure—and how the helicase coordinates with the two ‘polymerase’ enzymes that duplicate each strand to copy the genome.”

The image and implications from this study were described in a paper entitled “The architecture of a eukaryotic replisome,” published recently through Nature Structural & Molecular Biology.

Simon Sharwood, The Register, Linus Torvalds fires off angry ‘compiler-masturbation’ rant, here.

“This is the old code in net/ipv6/ip6_output.c:

mtu -= hlen + sizeof(struct frag_hdr);
and this is the new “improved” code that uses fancy stuff that wants magical built-in compiler support and has silly wrapper functions for when it doesn’t exist:

if (overflow_usub(mtu, hlen + sizeof(struct frag_hdr), &mtu) ||
mtu <= 7)
goto fail_toobig;
and anybody who thinks that the above is

(a) legible (b) efficient (even with the magical compiler support) (c) particularly safe

is just incompetent and out to lunch.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: