From Sharov and Gordon's paper Life Before Earth at arXiv. The implication is clear from the figure - that life has followed a logarithmic complexity trajectory, which is cooler to refer to in terms of Moore's law, but that at 4.5 GA ago (the formation of Earth from the stellar accretion disc) the complexity is not 0. Their figure crosses that line at a complexity of about 10^4.5, meaning a 30,000 bp genome. For reference, the smallest chemical replicators in nature are viroids (RNA that reproduces in plants), mostly around 2,000 bases, although hepatitis D is a virus essentially parasitic on other viruses with a similar genome size. The smallest replicators with independent metabolism are the Mycoplasma (a medically important genus discovered by Leonard Hayflick), generally under a million bp. Your genome is about 3 billion base pairs.
The first question we should ask here is what we even mean when we say "genome size", and why we care (which the authors do somewhat address). There is a difference between absolute number of base pairs in each cell, non-repetitive DNA (information), and functional complexity. If you want to talk about plain old absolute number of base pairs by mass in the cell, then plants win that one hands down, because they sometimes have many many copies of each chromosome - 20 or more. Modern corn has 6. Fine then; you want to talk about non-repetitive DNA, i.e. the Kolmogorov complexity of genomes? If you want to make a compressed file of a genome, some organisms have long stretches of repeats that can be compressed by saying "[repeat] x a million"; I don't think that complexity is what we're talking about either. (For the record, humans have more non-coding repeat DNA than coding DNA. Coding is about 3% of our genome, and just the most common type of repeat, the Alu element, is 5%.) Even taking that into consideration, yes, vertebrates have bigger non-repeating genomes than most other organisms, but among the vertebrates, non-repeating genome size and behavioral complexity do not correlate. Unless you're willing to concede that fish are smarter than you, because they have bigger non-repeating genomes. (I'm not willing to concede that.)
I think what we're really talking about here is functional complexity - the phenotype that the DNA produces in extension - and the best approximation of this is the number of genes. The authors of this paper refer to functional non-redundant genome, and even then - are you ready? - by this measure, protozoans win. Yes, amoebas and giardia. The kicker is that Trichomonas, which causes an STD, holds the record for the most genes of any organism yet sequenced. (I debated including a picture of its effects but I decided against it. You're welcome.) So it's time to retire your vertebrate chauvinism, or at least find another justification for it, because you're not that complex. For more on this, see the C-value paradox.*
All hail Trichomonas, our genomic superior. This is the one that infects humans; another one in the same genus infected T. rex.
That said, functional non-redundant genome size may still not be a totally awful indicator of genome complexity over geological epochs, but there are still further issues worth pointing out: they assume a constant trend and argue for it based on several other provincial (terrestrial) examples of complexity. We can't really assume that an algorithmic approach to processor speed and scientific publication rates give us the correct start date, and therefore so does the origin of all life, especially when the chemical substrate must have been different early on (see the RNA World hypothesis). They also get a little greedy reducing things to big picture neat-o ideas; for example, the Singularity makes an appearance. I think it's worth pointing out that we're still working out the troublesome details of the origin of replicator chemistry under early-Earth conditions and there are some fairly good answers now, but if replicators predate the Earth that begs the question of under what conditions did they appear. I've made the argument repeatedly that replicators could spread on comets and asteroids but it's much less likely that they originated there. Too cold, too dry, boiling point of solvents too high under low pressure atmosphere.
Of course it's an interesting paper (link here) but that doesn't mean it's correct. If it is correct, it means the evolution of life elsewhere is even more certain than it was before, which makes the Great Filter all the more daunting.
*My own take on the the C-value puzzle is that it's actually not that puzzling, unless of course you assume behavioral complexity must mean genomic complexity. For one thing, those protozoans have very complex life cycles, and have managed to preserve a lot of the behavior of eukaryotes that their single-celled prokaryotic comrades never had; the vast majority of our own cells are coddled in a vast bureaucracy that protects them from the outside world, and even if they screw up and die or reproduce out of control, there are a trillion more of them and an immune system to kill them just in case. There is also very little pressure on multicellular eukaryotes not to let their genomes accumulate a lot of junk, much of which is likely to be non-coding repeat elements. The amount of extra energy it takes your cells to reproduce their Alu elements today is far, far less than the amount of energy it takes you to scratch your head, and you aren't starving because of that either.