Algorithmic stagnation

I can get as excited about an n log n solution as anyone, but I don’t pretend to be a real expert in algorithmic analysis. But I’m interested.

One upon a time, I remember people claiming that more of the tremendous increase in speed of computations was due to improved algorithms than faster hardware. It wasn’t a ridiculous claim.

Moore’s law is slowing down, but surely the rate of algorithm improvement has as well. Hard to see how you trump the FFT.

Posted in Uncategorized | 64 Comments

The Road From Morocco


It never hurts to look at the map. Back around the glacial maximum, the world was a crappy place, with fewer inhabitable areas. Some of the high genetic differentiation in early Holocene populations may have been caused by climate-induced barriers: glaciers, bigger deserts, glacial lakes, etc.

The Basal Eurasians had low Neanderthal admixture while still leaving sub-Saharan Africa. North Africa might fit this scenario. If they made it to North Africa when conditions were not so bad, they might have been trapped there for a long time when the Sahara was at its max, and would only have entered the Middle East after the Neanderthals had already been displaced. But this means that they probably ran into and admixed with the locals, either not AMH or some fairly divergent branch of AMH.

Posted in Uncategorized | 29 Comments


There are lots of toxic ideas that haven’t been implemented solely because I have kept my own counsel – the dark forces that would have enthusiastically welcomed them could never have thought of them by themselves.

This is the only reason that the Wall Street Journal isn’t already campaigning to turn Social Security into a tontine.

Posted in Uncategorized | 74 Comments

First Farmers

There’s a new paper (by Iosif Lazaridis and others) out on the genetics of the world’s first farmers in the Middle East. There are a number of interesting points.

They find that early farming populations are about half descended from the somewhat mysterious “Basal Eurasians”, who apparently split off from other Eurasians before they separated from each other. Those Basal Eurasians appear to have little or no Neanderthal admixture, but they are no closer to sub-Saharan Africans than other Eurasians. Which they means that they probably left sub-Saharan Africa a long time ago – but where then did they go? Somewhere without any Neanderthals? North Africa might work: we have no evidence that there were ever any Neanderthals there. But if the Basal Eurasians didn’t mix with Neanderthals, they likely mixed with someone else. Someone lived in North Africa before modern humans: we might see a trace of that in populations with Basal Eurasian ancestry. With luck and some ancient DNA from North Africa (or possibly South Arabia?), we might find the answer.

Genetic differentiation was much stronger back in those days. Fst between Natufians and the hunter-gatherers in the Zagros mountains ( western Iran) was comparable to that between Germans and Chinese today. You can bet that their languages were highly differentiated as well.

The first farmers seem to be descended from the hunter-gatherers that immediately preceded them. All the groups that picked up farming expanded outward: early Anatolian farmers into Europe (LBk and Cardial cultures), Levantine farmers into Africa (so Hamito-Semitic must have originated in the Middle East). it looks as if ur-Georgians mixed with eastern hunter-gatherers that were closely related to ANE (75%) to form the proto-Indo-Europeans, which means that pre-PIE was spoken by those eastern hunter-gatherers, and the similarities between Kartvelian languages like Georgian and Indo-European may boil down to pillow talk and lullabies.

By the Bronze age Natufians and Zagros mountaineers and Anatolian farmers were mixing a lot – but before agriculture, such mixing must have been very rare for a long time, in order to generate that big Fst. There was probably more trade with the advent of agriculture ( more mixing) , and later, technical developments like ships and wheeled vehicles probably favored mixing. Farmers can have specialists, who may make use of exotic materials ( like tin or lapis lazuli) than are imported over long trade routes. Eventually there were empires, some of which seem to have shuffled ethnic groups around the chess board simply because they could. Probably the horrible Ice Age climate played a role in keeping populations isolated before the Holocene.

But back before the Holocene, it seems that, more often than not hunter-gatherers either didn’t mix or exterminated each other. It looks as if there were two waves of replacement ( with little admixture) in Europe after modern humans replaced Neanderthals and before Anatolian farmers largely replaced the last population of European hunter-gatherers!
We see a couple of cases in which new populations are found almost entirely with males from one population and females from another: early Indo-Europeans and Amerindians.

Posted in Uncategorized | 51 Comments

Who’s on first?

There’s a new paper out on the people of the Americas, by Pontus Skoglund and David Reich. The main picture is solidifying:

The main Amerindian migration consists of a population that is approximately 40% ancient Siberian and 60% Han-like. Calculations that assumed a simple split between the ancestors of the Han and Amerindians are wrong and probably placed too far back (~23,000 years BP). They don’t mention it, but the uniparental lineages suggest that ANE guys ran off with some sobbin’ proto-Han women, much like the formation story for the Indo-Europeans.

There was some substructure: the two main streams are the Amerindians of South and Central America and northern Amerindians like Cree and Algonquins. Interestingly, the only Clovis skeleton we have is genetically closer to the southerners.

The paleo-Eskimos (Dorset culture) come from a later, separate migration (~4500 years ago), similar to Koryak and Chukchi, but were completely replaced by the Thule culture (current Eskimos) ~1000 years ago.

The Na-Dene (Navajo for example) also came late: they might be from the same stream that led to the Dorset, but they might stem from another migration. Better samples from more populations should soon resolve this. Since Na-Dene languages can be related to Ket using standard methods, it can’t have been all that long ago – more like 4 or 5 thousand, rather than 8 or 9.

According to this paper, the Andamanese-like admixure is found only east of the Andes in South America, apparently concentrated in the Tupi language family. Not in the Eskimos, not in central America, not in Canada, not in the one Clovis skeleton we have, which has affinities to the Central/South America branch. Not in Tierra del Fuego, not in Baja California.

I think this strong pattern significantly increases the probability of the scenario in which a vaguely Andamanese-like population gets to the Americas first, maybe 18k years ago, came by sea and settled Brazil, which was decent hunter-gatherer territory (savannahs and open woodland), not ice/polar desert/taiga like North America. Then was replaced, with a little admixture, by a classic Amerindian population. I would guess that the authors think so too: they’re treating this scenario with more respect than in the earlier paper. They mention the odd-looking early skeletons in Brazil.

We need ancient DNA to seal the deal, but that may come.

Why didn’t these Andamanese-like guys drive extinctions? Cause the megafaunal extinctions are a good deal later. I’m guessing that they were originally fishermen and beachcombers, not hard-case hunters of big mammals like the Amerindians in Beringia. Modern humans didn’t cause instant extinctions in Africa (only some things) but the animals there had a long time to adapt to people, while sleeping sickness eventually created people-free zones. . South America wasn’t like that – why didn’t these Andamanese wipe out the big game? Well, from what we know they weren’t very good at dealing with Amerindians – and related populations in Southeast Asia, the Philippines, and Indonesia also lost out to Han-like invaders.

Yet even the Australian aborigines seemed to have wiped out the Australian megafauna pretty rapidly… In our scenario, why didn’t the pseudo-Andamanese?

Something limited their ecological dominance.

Posted in Uncategorized | 155 Comments

In a handbasket

It strikes me that in many ways, life was gradually getting harder in the Old World, especially in the cradles of civilization. We know that every now and then a new infectious disease was added to the mix: smallpox probably shows up in the classical world around 180 AD, bubonic plague in 641, syphilis in 1494, cholera around 1830, HIV in the 1970s. Those we know – but many other infectious diseases must have arrived at some time since the beginning of the Holocene – certainly those like measles whose critical community size was too large for it to have existed among hunter-gatherers. Ancient DNA & molecular phylogeny should elucidate this negative trend. Bet you a dollar that typhus didn’t exist in the old days.

What, if anything, countered this gradually increasing disease burden? I would say selection – medicine was useless until quite recently. But selection is slow. Now and then an infectious disease seem to have disappeared (English sweat) or become milder (scarlet fever) but that was a coincidental outcome of some kind of ecological change – people didn’t plan it.

In the same way, farming should have gotten harder in some ways: the burden of weeds, blights, and insects should have increased with time. There, though, selection acted faster than it did in humans: crops have high effective population size and short generations. Of course, so do weeds… I know that chickpea, one of the original founder crops of the Middle East, disappeared for about 3,000 years because of a fungus – until a version that grew in the (dryer) summer showed up. Rye and oats started out as weeds and developed such effective mimicry that they became crops…

Then there’s environmental degradation – deforestation, erosion, soil salinization, exhaustion of ores useful to available techniques. Worse in fairly dry areas, worse with irrigation as opposed to rain-fed agriculture.

Technical innovations pushed in the other direction – decent horse harnesses, three-field cultivation, water mills, Champa rice – but it could be a long time between innovations. In particular Classical civ seems to have been low on such innovations.

Posted in Uncategorized | 45 Comments

mtDNA, Y-chromosomes, autosomal DNA

Imagine that we take men from population A, with a distinct set of Y-chromosomes, and have them father children with women from Population C. And their male descendants keep marrying women from population C: eventually we have a population (D) with all Y-chromosomes originating in population A while their mtDNA and autosomal DNA are all from population C.

Now we take women from population B, with a distinct set of mtDNA haplotypes. They marry guys from population D, and their descendants continue to do so for a long time: so we eventually end up with a population (E) all of whose Y-chromosomes come from population A, all mtDNA from population B, all autosomal DNA from population C.

Posted in Uncategorized | 27 Comments