In recent years, cloaking technology has taken the world of physics and engineering by storm. The possibility that any object can be hidden from incident waves has numerous applications, both practical and fantastical.

One of the more interesting is the possibility of protecting buildings from seismic waves. The idea here is to surround a building, or at least its foundations,  with a metamaterial that steers seismic waves around the structure. Various groups have explored ways of doing this.

Today, however, Sang-Hoon Kim at the Mokpo National Maritime University in South Korea and Mukunda Das at The Australian National University in Canberra, suggest another idea. They point out that while seismic cloaks can protect buildings, they steer waves towards other buildings. "The cloaked seismic waves are still destructive to the buildings behind the cloaked region," they say.

Instead, they suggest that metamaterials could instead dissipate the energy in seismic waves by converting them into evanescent waves, which die down exponentially as they travel.

They calculate the properties of such a metatmaterial and how it might be constructed with a basic repeating unit in the form of a concrete cylinder some 18 metres in diameter, with four perpendicular holes in its sides (see picture). 

These cylinders, perhaps varying in size to absorb a range of seismic wavelengths,  would need to surround the foundations of a building in cylindrical shells some 60 metres across.

That needn't be prohibitively expensive but it would be a big structure that could only be constructed around isolated buildings (thereby somewhat negating the supposed benefit that other buildings in the earthquake 'shadow' might also be protected).

That would be suitable, they say, for structures deemed vital for society, such as power plants, dams, airports, nuclear reactors, oil refining complexes and such like.

But the work leaves one important question unanswered: what happens to the seismic energy that is dissipated?  

Kim and Das suggest that the absorbed energy will turn into sound and heat. However, they offer no evidence to suggest that their concrete cloaks could cope with the energy releases involved in big earthquakes. How much sound and heat is this equivalent too? 

That's something they'll need to work on. A convincing argument that the metamaterials involved can cope with this kind of dissipation will be crucial if anybody is to run with this idea. 

Ref: arxiv.org/abs/1202.1586: Seismic Waveguide of Metamaterials

Virtual Parallel Computing And A Search Algorithm Using Matrix Product States

Topological P-N Junction

Bayesian Inference of Whole-Brain Networks

On The Influence Of Intelligence In (Social) Intelligence Testing Environments

Acoustic Communication for Medical Nanorobots

On 6 May 2010, shares on US financial markets suddenly dropped on average by around 10 per cent but in over 300 stocks by more than 60 per cent. Moments later the prices recovered.

The event mystified economists because they had never seen anything like it (and have enough trouble explaining the ordinary workings of markets). Econophysicists have since blamed this so-called flash crash on the automated behaviour of ultrafast computer trades, which take place in periods measured in milliseconds. 

These kinds of trades appear to generate emergent behaviour that has nothing to do with the actual value of a company. Instead, these events are unavoidable properties of the system itself.

That raises an important question: how can authorities prevent flash crashes and price spikes in which billions of dollars can be won and lost?

The answer is that nobody knows, not least because econophysicists do not yet understand the nature of flash crashes nor how they emerge in complex systems. 

Today, however, Neil Johnson at the University of Florida in Miami and a few pals reveal an important insight into what's going on. These guys have found evidence that the behaviour of financial markets changes dramatically on timescales shorter than a certain threshold level. This threshold, they say, is more or less exactly equal to the human reaction times.

The implication is clear. When humans trade and when they monitor the behaviour of machine trading, they can step in to override any unwanted behaviour. In that regime, markets behave in a specific way. 

But when human oversight becomes impossible, because the trades take place faster than humans can react, a different behaviour occurs. That's when flash crashes and rises set in. 

The evidence comes from Johnson and co's study of stock price movements between 2006 and 2011. These guys looked for extreme changes in a stock price, which they defined as a change greater than 0.8 per cent, over timescales shorter than 1.5 seconds.

Since human reaction times are about a second, this spans the regime when trades begin to occur faster than humans can monitor and react to them.

The first thing they discovered is that flash crashes and rises are not at all rare. Johnson and co found over18,000 of them, that's more than one a day on average. They call them black swan events, using the terminology developed by Nassim Nicolas Taleb in his book The Black Swan.

Curiously, they found that that change in the occurrence of crashes occurs at timescales shorter than 650 milliseconds, while the transition for price spikes occurs at 950 milliseconds.

Johnson and co say this can be explained if humans are more alert to crashes than to price rises.  They point out that 650 milliseconds is about the fastest a human can react to any warning sign, so it's no surprise that the transition occurs here for crashes. 

Price rises, on the other hand, are usually beneficial and so require no immediate action, which is why the transition in behaviour occurs at slightly longer timescales.

They also say that the ten stocks most susceptible to flash crashes and rises are international banks. This, they say, “hints at a hidden relationship between these ultrafast ‘fractures’ and the slow ‘breaking’ of the global financial system post-2006.”

The work also hints at a solution: to somehow reproduce the effect of human oversight at ultrafast scales. How that can be done with regulation alone isn't clear but there is no disputing the urgency with which this matter should be addressed.

The markets are clearly changing. The need to outperform competitors is currently driving a multibillion dollar investment in machine trading at rates even faster than milliseconds. In one project, traders are financing the construction of a dedicated transatlantic cable that will shave just 5 milliseconds off the time it takes to trade stocks. 

Unless it is tackled in the near future, just what kind of behaviour this race-to-the-bottom will generate, is anyone's guess. 

Ref: arxiv.org/abs/1202.1448: Financial black swans driven by ultrafast machine ecology

Distributed computing is all the rage these days. The idea is to break down computational tasks into convenient chunks and distribute them across a network to a number of computers. The benefits are clear, such as easy, on-demand access to huge computing resources. 

The conventional way to think about these systems is as independent Turing machines connected by a network that allows them to exchange large messages. This so-called 'message passing model' certainly applies to much of the distributed computing that takes place on the internet; projects such as the SETI@home and the Einstein @home programs.

But there is a growing awareness that many networks are much more limited, both in the size of the messages they can transmit and receive and also in the processing capacity at each node. 

A biological cell, for example, can transmit and receive only limited amounts of information and can perform only rudimentary processing tasks.  It's easy to imagine that a network of cells can perform only very simple distributed computing tasks. On the other hand, perhaps they can make up for their individual deficiencies by working as a group and so are just as capable as other networks.   

So an important question is how these limitations influence the classes of distributed computing tasks that groups of cells can perform. 

Today we have an answer thanks to the work of Yuval Emek, Jasmin Smula and Roger Wattenhofer at the Swiss Federal Institute of Technology in Zurich. "We believe that there is a need for a network model, where nodes are by design below the computation and communication capabilities of Turing machines," they say. 

These guys have modelled the computing behaviour of a network of these sub-Turing machines, which they call finite state machines. They show that far from being critically handicapped, a network of finite state machines is capable of solving many of the standard problems in conventional distributed computing, such as the 3-colouring of undirected trees . 

What's more, these networks can do the job just as efficiently--in a time that is poly-logarithmic with the number of cells.

That could turn out to have far reaching consequences. It may be a stretch to imagine a network of cells joining the SETI@home project. But it provides a framework in which to study how networks of cells might solve other common problems in biological systems such as forward planning, trajectory calculations and so on.

The new model can also be applied in more prosaic ways, such as predicting the performance of networks of sensors which are strongly constricted by power limitations.

Emek and co ask the question: "do tiny bio/nano nodes “compute” and/or “communicate” essentially [in] the same [way] as a computer?"

The answer, it would seem, is yes, which means it is an exciting time to be a distributed computing specialist working in biology. 

Ref: arxiv.org/abs/1202.1186: Stone Age Distributed Computing   

Twitter has revolutionised the way millions of people receive news and the type of news they get. So it's no surprise that there is huge interest in predicting what kind of stories are likely to spread furthest and fastest.

One way to make this kind of prediction is to study how a story spreads soon after it is released into the wild. Various groups have shown that this early popularity can be a good predictor of a story's later spread. 

A couple of years ago, Bernardo Huberman and pals at HP's Social Computing Lab in Palo Alto used this approach to predict the eventual box office revenues based on the rate of tweets about a film soon after it was released.   

The problem with this method is that the structure of the network can have a profound effect on the way tweets spread and this has little to do with the content and its appeal. 

So Huberman is now taking another approach. This time he wants to know whether there is something about the news stories themselves that determine their popularity. In other words, he's looking for factors that determine how popular a news story will be before it is even published.    

To find out, Huberman and his colleagues examined the content of news stories during  a single week in August last year as measured by the news feed aggregator Feedzilla. They scored each article based on four criteria: the news source that generates and posts the article; the category of news; the subjectivity of the language; and the people and things named in the article.

They then measured the way these news stories spread across the Twitter network to see which became popular and how quickly. They used this to work out how an article's score in each criterion is linked to its eventual popularity    

Finally, having worked out what factors make an article successful, they used this to predict how popular other articles would be. 

Here's their conclusion: "Our experiments show that it is possible to estimate ranges of popularity with an overall accuracy of 84% considering only content features."

So before anybody lays eyes on these articles, it's possible to work out in advance how popular they are likely to become. 

That's pretty impressive and may herald important changes in the way articles are written and edited. It's not hard to imagine an automated article checker—rather like the grammar checkers in word processing programs--that reads articles and predicts how popular they are likely to be when published.  

In a sense, that's what journalists do now when they choose topics to write about. But this process is entirely intuitive, based as much on gut feel as on a good understanding of the dynamics of the audience. Huberman's algorithm could automate this process. 

That would have profound effects on the generation of news stories. On the one hand, it could lead to the homogenisation of stories as news organisations focus on optimising their stories for this algorithm. 

Exactly that process happened in Hollywood a few years ago when story telling became homogenised in the manner outlined by Robin Mckee in his highly successful Story seminars. 

On the other hand, automation could lead to a new generation of more tightly written and better focused stories that  build on the new algorithm and better it. 

Interesting times. One way or another, the way we produce written content is changing. And rapidly.  

Ref: arxiv.org/abs/1202.0332: The Pulse of News in Social Media: Forecasting Popularity

One of the buzzwords in artificial intelligence research these days is 'embodiment', the idea that intelligence requires a body.

But in the last few years, a growing body researchers have begun to explore the possibility that this definition is too limited. Led by Rolf Pfeifer at the Artificial Intelligence Laboratory at the University of Zurich, Switzerland, these guys say that the notion of intelligence makes no sense outside of the environment in which it operates.

For them, the notion of embodiment must, of course, capture how the brain is embedded in a body but also how this body is embedded in the broader environment. 

Today, Pfeifer and Matej Hoffmann, also at the University of Zurich, set out this thinking in a kind of manifesto for a new approach to AI. And their conclusion has far reaching consequences. They say it's not just artificial intelligence that we need to redefine, but the nature of computing itself.

The paper takes the form of a number of case studies examining the nature of embodiment in various physical systems. For example, Pfeifer and Hoffmann look at the distribution of light-sensing cells within fly eyes.  

Biologists have known for 20 years that these are not distributed evenly in the eye but are more densely packed towards the front of the eye than to the sides. What's interesting is that this distribution compensates for the phenomenon of motion parallax.

When a fly is in constant forward motion, objects to the side move across its field of vision faster than those to the front.  "This implies that under the condition of straight flight, the same motion detection circuitry can be employed for motion detection for the entire eye," point out Pfeifer and Hoffmann.

That's a significant advantage for the fly. With any other distribution of light sensitive cells, it would require much more complex motion detecting circuitry. 

Instead, the particular distribution of cells simplifies the problem. In a sense, the morphology of the eye itself performs a computation. A few years a go, a team of AI researchers built a robot called Eyebot that exploited exactly this effect.

What's important, however, is that the computation is the result of three factors: simple motion detection circuitry in the brain, the morphology or distribution of cells in the body and the nature of flight in a 3-dimensional universe.   

Without any of these, the computation wouldn't work and, indeed, wouldn't make sense.

We've looked at examples of morphological computation on this blog in the past (here and here for example). And Pfeifer has been shouting from the roof tops for several years, with some success, about the role that shape and form play in biological computation. 

But today he and Hoffman go even further. They say that various low level cognitive functions such as locomotion are clearly simple forms of computation involving the brain-body-environment triumvirate. 

That's why our definition of computation needs to be extended to include the influence of environment, they say. 

For many simple actions, such as walking, these computations proceed more or less independently. These are 'natural' actions in the sense that they exploit the natural dynamics of the system.

But they also say it provides a platform on which more complex cognitive tasks can take place relatively easily. They think that systems emerge in the brain that can predict the outcome of these natural computations. That's obviously useful for forward planning.

Pfeifer and Hoffmann's idea is that more complex cognitive abilities emerge when these forward-planning mechanisms become decoupled from the system they are predicting. 

That's an interesting prediction that should lend itself to testing in the next few years. 

But first, researchers will have to broaden the way they think not only about AI but also about the nature of computing itself. 

Clearly an interesting and rapidly evolving field.  

Ref:  arxiv.org/abs/1202.0440 :The Implications of Embodiment for Behavior and Cognition: Animal and Robotic Case Studies 

Spatiotemporal Features Of Human Mobility

Prime Numbers, Quantum Field Theory And The Goldbach Conjecture

Gerbert Of Aurillac: Astronomy And Geometry In Tenth Century Europe

A Multiple Of 12 For Avogadro

The Direction of Gravity

Among the most impressive transportation networks on the planet are the complex trails that ants create around their nests. These networks arise through the ants' exploration of their environment and end up channelling the distribution of food for the colony and the daily movements hundreds of thousands of individuals.

What's more, these networks aren't just a random criss-crossing of space. Instead, they are a highly efficient solutions to the problem of searching and transporting food. Various groups have created ant-like foraging algorithms to do other types of virtual exploration.  

One question that has fascinated biologists is how ants build these networks. They've known for some time that ants leave small deposits of pheromones as they travel and that other ants follow these trails, leaving their own deposits. This increases the concentration of the pheromone, strengthening the trail. 

But the precise algorithm that governs the way ants respond to pheromones has been harder to pin down. Many experiments show that a trail can only be reinforced if ants have a disproportionately higher probability to follow a  trail with higher pheromone concentration.  

Biologists have always assumed that this disproportionate response means ants must have a non-linear response to the chemical. In other words, an ant's tendency to turn towards a pheromone deposit is related in a non-linear fashion to the concentration.

But that seems to conflict with one of the great triumphs of experimental biology--Weber's Law, which relates the perceived intensity of a stimulus to its physical magnitude. Biologists know this holds for the human perception of many stimuli, such as the intensity of sound, and have also verified it in many insects. So why not in ants?

Today, Andrea Perna at the Complex Systems Institute of Paris Ile de France and a few pals, resolve the issue. These guys have developed an entirely new way to image pheromone trails which allows them to study ant response to pheromones in more detail than ever before. 

They say the structure of ant trails can be entirely explained if the ants's response to a pheromone droplet concentration is linear. "One ant will turn to the left in proportion to the difference between the pheromone it has on its left side and the pheromone on its right," say Perna and co.

They also point out that this is exactly what Weber's law predicts.

So where does the non-linearity required to create trails come from? Perna and co say that ant behaviour is inevitably noisy.  "We show that the required non-linearity does not reside in the perceptual response of the ants, but in the noise associated with their movement," they say.

That's a fascinating result because it reveals how complexity in nature forms with the simplest of inputs. 

And it clearly has implications for the study of other complex structures that ants create, such as their nests. Just how ants create these huge vibrant structures has long puzzled biologists. 

Perna and friends hint at an answer in their conclusion. "We can imagine that other collective phenomena, such as group decision-making, could also be founded on coupling between Weber’s Law and simple feedback mechanisms."

In the case of nests, this mechanism would have to operate in three dimensions rather than two. But that shouldn't be too much of a challenge. Perhaps a problem that a relatively simple computer model could help solve.    

Ref: arxiv.org/abs/1201.5827 :Individual Rules For Trail Pattern Formation In Argentine Ants (Linepithema Humile)

Neutrinos are peculiar particles. They have little mass, no charge and come in three flavours. These flavours are not fixed. The strange thing about neutrinos is that once created, they change from one flavour to another as they travel. 

For a long time, that puzzled physicists. A neutrino's variety determines how it interacts with matter. Physicists built experiments to detect  the flavour coming out of the Sun only to find far fewer than they expected. 

In 2001, that mystery was solved when they discovered that the missing neutrinos had flipped, or oscillated from one flavour to another, during their journey from the Sun to the Earth.  

Since then physicists have scrambled to understand neutrino oscillations in more detail. It turns out that the effect is sensitive to the distance that the neutrinos have travelled and also to the amount of matter the particles have passed through.  

That's given Carlos Arguelles and pals at the Pontifical Catholic University of Peru in Lima an idea. These guys say that  neutrino oscillations ought to be sensitive to changes in the density of the Earth. 

So the oscillations in a beam of neutrinos created at one point on the Earth and beamed through the crust to another point, ought to reveal information about any change in density along the way.  

These guys aren't the first to suggest that a neutrinos beam can effectively x-ray the Earth. But they are the first to explore the size and shape of the density changes that ought to be visible using this method. 

They say the technique ought to be able to spot cavities some 200 km across or larger filled with water,  iron-based minerals or even regions of charge accumulations. They suggest that this might take as little as 3 months.

That's interesting because some seismologists suggest that earthquakes lead to the accumulation of charge in specific volumes of rock, so the technique might be useful for studying this. 

But there's a more significant factor driving interest in this work. This technique could also reveal geological formations likely to contain oil and so could attract considerable commercial investment.   

One important question, however, is whether Arguelles and co have made realistic assumptions in their model. One problem they face is that the beam of neutrinos must be intense enough to produce a result in a reasonable period of time--certainly less than 18 months. 

To achieve this, Arguelle and co have to assume that it is possible to create beams at a rate some 5000 times higher than is achievable today.

Since it's not at all clear how this could be done, that's a big fly in the ointment. 

So while this technique looks possible in theory, this kind of assumption places a big question mark over whether it will be possible in practice in the foreseeable future.

Ref: arxiv.org/abs/1201.6080 : Searching For Cavities Of Various Densities In The Earth’s Crust With A Low-Energy ν¯e β-Beam

Various studies have shown that the frequency of contact between individuals is a reliable indicator of the emotional link between them. So it should come as no surprise that the data from mobile phone calls is a potential treasure trove of information about the social lives of humans. 

But analyses of this data so far have been distinctly unspectacular. For example, the location data associated with phone calls has revealed various new intricacies in the movements of commuters. Interesting but hardly jaw-dropping.

That is set to change with the work of Vasyl Palchykov at the Aalto University School of Science in Finland and a few buddies including a couple of old hands in the form of Albert-László Barabási at Northeastern University and Robin Dunbar at the University of Oxford (of Dunbar's number fame). 

These guys have got hold of a corpus of mobile phone data relating to calls between 1.4 million women and 1.8 million men in an unspecified European country. Between them, these phone subscribers made almost 2 billion calls and sent almost half a billion text messages. In addition to the gender of each subscriber, Palchykov and co also managed to get their age as well. 

That's significant because it allows them to study not allow the pattern of calls between genders but the way this changes with age. 

They began by taking each subscriber and determining the age and gender of the person they werein contact with most frequently, second most frequently and so on. These, they assume, are the 'best' friend, second best friend and so on.

Then, they looked at how the 'best friends' changed as subscribers age. It turns out in general that between the ages of 18 and 40 or so, men and women have best friends of the opposite sex. Palchykov and co assume this reflects the general pattern of mating in society. Second best friends are generally of the same sex at this age.

But they tease the most interesting phenomena out of the fine detail in their dataset. They conclude for example that women are more focused on opposite-sex relationships than men are during the period of their lives when they are reproductively active. That indicates that women invest  more heavily in creating and maintaining their relationships than men.

As women age, their attention shifts from their spouse to younger females some 25 years or so younger. That's about equal to a generation gap and Palchykov and co assume these younger females are daughters. This attention shift also seems to equate to the arrival of grandchildren, when the older female again once again begins to invest more heavily.

While older women focus more heavily on younger females, older men maintain an even gender balance in the second best friends, presumably this reflects an equal attention between children of opposite sexes.

What's striking about this is how strongly female relationships are determined by their reproductive cycle. “Women’s gender-biases thus tend to be stronger than men’s, seemingly because their patterns of social contact are strongly driven by the changes in the patterns of reproductive investment across the lifespan,” say Palchykov and co.

Clearly, female reproductive strategies change more explicitly as they age, switching from mate choice to personal reproduction to parental investment and finally grandparental investment, particularly after they reach 40. 

However, the most dramatic conclusion from this work is about the pattern of social relationships that play the most important role in society. Palchykov and co say the tendency in the past has been to assume that father-son relationships dominate. 

By contrast, “our results tend to support the claim that mother-daughter relationships play a particularly seminal role in structuring human social relationships,” they say. 

This difference on the way the sexes invest in relationships is exactly what evolutionary biologists expect. But although previously suspected, it has proved particularly difficult to test. That's why this work is something of a landmark.

Clearly, the ability to study human relationships on such a vast scale opens up a host of new avenues for research in social and reproductive strategies.

In particular, this study looks only at the existence of links between people, not the the directional asymmetries in relationships or who initiates contact.  Palchykov and co leave that for another day.

There's a mountain of data ready to be mined on this. And clearly, there's gold in them thar hills.

Ref: arxiv.org/abs/1201.5722: Sex differences in intimate relationships 

One interesting way in which our cosmos may have formed is in a collision between two other universes with extra spatial dimensions called braneworlds. 

In this scenario, known as the ekpyrotic model of the universe, our cosmos is just a small four-dimensional corner of a much more complex space.  

The ekpyrotic model is interesting because it leads to a flat universe like our own without the need for inflation, the period just after the Big Bang in which our universe supposedly swelled by many orders of magnitude in the blink of an eye.

Without inflation, our universe is just too big to have been formed in a Big Bang-type event. But nobody knows what might cause such a dramatic increase in size. Hence the interest in another way of explaining our existence.

If you're wondering what actually collides in the ekpyrotic version of events, the answer is Minkowski domain walls, essentially the edges of universes with different spatial dimensions. 

It's easy to imagine that Minkowski domain walls are entirely theoretical. And indeed they were until now. 

Today, Igor Smolyaninov and Yu-Ju Hung at the University of Maryland, in College Park, say they've created Minkowski domain walls in the lab for the first time and even used them to simulate the collision of two braneworlds.

The trick these guys have used is a formal analogy between the mathematics of space time and of electromagnetic spaces. Physicists have known since Einstein's day that it is possible to bend and distort the fabric of spacetime—our universe appears to be distorted  in just this way on various cosmic scales.

But it is only in the last ten years or so that they've learnt how to do the same on a much smaller scale with electromagnetic spaces. What's triggered this is the development of metamaterials: artificial substances that can bend light in almost any way imaginable. 

Smolyaninov is fascinated  by one version of this stuff called hyperbolic metamaterial. Inside this substance, monochromatic light propagates in a similar way to massive particles in a Minkowski spacetime, where one spatial coordinate takes on the role of time.

Hyperbolic metamaterials are essentially a series of metal layers separated by a dielectric. Smolyaninov has used this stuff to simulate a number of interesting aspects of cosmology including the Big Bang itself.

The collision between universe's is a variation on this theme. “The “colliding universe" scenario can be realized as a simple extension of our earlier experiments simulating the spacetime geometry in the vicinity of big bang,” he says.

He simulates an expanding universe using concetric rings of gold separated by a dielectric. "When the two concentric ring  (“universe”) patterns touch each other (“collide”), a Minkowski domain wall is created, in which the metallic stripes touch each other at a small angle," he says.

Being able to recreate these exotic events in the lab is certainly interesting but it is beginning to lose its novelty. The problem is that this work is not telling us anything we didn't know--the universe behaves the same way inside a metamaterial as it does outside. 

What Smolyaninov needs is a way of using his exotic materials to do something interesting. In other words, he needs a killer app. Any ideas? 

Ref: arxiv.org/abs/1201.5348: Collision Of “Metamaterial Universes”: Experimental Realization Of Minkowski Domain Wall

Absorption Imaging Of A Single Atom

Phytoplankton Competition In Deep Biomass Maximum

Persistence of Single Spin Coherence above 600K in Diamond

Econophysics Of A Religious Cult: The Antoinists In Belgium [1920-2000]

The Sound Of An Evolving Floating Sculpture

Having been invented in the US in the mid-20th century, Scrabble is now available in dozens of languages and sells in numbers measured in hundreds of millions. That makes it one of the most popular games in the world.  

That has naturally piqued the interest of game theorists. "Since Scrabble is such a successful game, it becomes a natural question to determine the computational complexity of finding an optimal play," say Michael Lampis at the KTH Royal Institute of Technology in Sweden and a few pals. 

The same question has been successfully asked of many board games, such as chess, Go and Othello, which tend to be PSPACE or EXPTIME-complete. But Scrabble is trickier because players do not know the order in which the tiles will be drawn meaning that chance plays a greater role.

The question that Lampis and co attempt to answer is this: given a Scrabble position how hard is it to determine the best playing strategy? 

They point out that in any given round, a Scrabble player is confronted with two tasks: deciding which word to form and deciding where to place it on the board. These tasks are related because the words that can be formed depend on the position of letters on the board. 

But which of these task is it that makes Scrabble hard? What Lampis and co show is that both are hard and give a proofs of each to back up their claim. That's impressive because it allow us to 'see' why Scrabble is hard. 

"We establish that during the course of a game, Scrabble players need to perform not one, but two computationally hard tasks, which is probably the reason why Scrabble is so much fun to play," they write.

That's not to say computational complexity theorists are done and dusted with Scrabble. Their next task is to discover whether there is a polynomial-time algorithm to determine the move that would maximize the score achieved in this round.

Now that would be handy! 

Ref: arxiv.org/abs/1201.5298: Scrabble is PSPACE-Complete

In the last few years, a few dedicated mathematicians have begun to study the computational complexity of video games. Their goal is to determine the inherent difficulty of the games and how they might be related to each other and other problems.

Today, Giovanni Viglietta at the University if Pisa in Italy reveals a body of Herculean work in this area in which he classifies a large number of games from the 1980s and 90s including Pac-Man, Doom, Tron and many others.

Viglietta's work involves several steps. The first is to determine the class of computational complexity to which the game belongs. Next, he works out whether knowing how to solve the game also allows you to solve many other problems in the same class, a property that complexity theorists call 'hardness'. Finally, he determines whether the game is complete, meaning that it is one of the 'hardest' in its class. 

His approach is relatively straightforward. He first works through a number of proofs showing that any video game with specific game-playing properties falls into a certain complexity class. 

He then classifies the games according to game-playing properties they have. 

For instance, one type of game involves a player moving through a  landscape visiting a number of locations. He calls this 'location traversal' and an example would be a game in which certain items are strewn around a landscape and the goal is to collect them all. 

Some location traversal games allow each location to be visited only once. So-called single use path games might include downhill races. 

He then uses graph theory to prove that any game exhibiting both location traversal and single-use paths is NP-hard, that's the same class of complexity as the travelling salesman problem. 

It turns out that Pac-Man falls into this category (the proof involves distributing power pills around the maze in a way that enforces single use paths).

He shows how games fall into other complexity categories too. For example, games that feature pressure pads to open and close doors are PSPACE-hard if each door is controlled by two pressure plates. Doom falls into this category.

And so on.

The resulting list is impressive. Here are a few of his results:

Boulder Dash (First Star Software, 1984) is NP-hard.

Deflektor (Vortex Software, 1987) is in L.

Prince of Persia (Brøderbund, 1989) is PSPACE-complete.

Tron (Bally Midway, 1982) is NP-hard.

For the full list and reasoning, see the paper below.

That's clearly been a labour of love for Viglietta, given the title of his paper: "Gaming Is A Hard Job, But Someone Has To Do It!"

Interestingly, he says this kind of analysis is unnecessary for modern games. "Most recent commercial games incorporate Turing-equivalent scripting languages that easily allow the design of undecidable puzzles as part of the gameplay," he says.

In a way, that makes these older games all the more charming still.

Ref: arxiv.org/abs/1201.4995 :Gaming Is A Hard Job, But Someone Has To Do It!

The problem of sending messages securely has troubled humankind since the dawn of civilisation and probably before. 

In recent years, however, physicists have raised expectations that this problem has been solved by the invention of quantum key distribution. This exploits the strange quantum property of entanglement to guarantee the secrecy of a message.

Entanglement is so fragile that any eavesdropper cannot help but break it, revealing the ruse. So cryptographers can use it to send a secure key called a one time pad that can then be used to encrypt a message. If the key is intercepted, the sender simply sends another and repeats this until one gets through.

So-called quantum key distribution is unconditionally secure--it offers perfect secrecy guaranteed by the laws of physics.

Or at least that's what everyone thought. More recently, various groups have begun to focus on a fly in the ointment: the practical implementation of this process. While quantum key distribution offers perfect security in practice, the devices used to send quantum messages are inevitably imperfect.

For example, lasers that are supposed to send one photon at a time can sometimes send several and this allows information to leak to an eavesdropper. 

Last year, we discussed another trick used by a group of quantum hackers to eavesdrop on a commercial quantum cryptography system. This system, although theoretically secure, turned out to be embarrassingly vulnerable in practice. 

That led quantum theorists to begin the search for a device-independent protocol that would be free of the practical imperfections of everyday equipment. Such a system would offer guaranteed security regardless of any weaknesses in the equipment it relies on.  

Today, however, Jonathan Barrett at the Royal Holloway, University of London, and a few pals reveal a problem that looks to scupper this work. The worrying implication of their discovery is that there is no known way to guarantee the security of data sent on any quantum cryptographic system including those that are commercially available today. 

Here's the problem. Some groups claim to have made progress in developing  device-independent protocols but Barrett and co have found an issue that all others appear to have overlooked. These protocols all treat quantum cryptography as a single-shot process, as if the equipment is used only once. 

The question that Barrett and co consider is what tricks could a malicious manufacturer exploit in a device that is likely to be used more than ince. The answer is obvious: such a manufacturer could build in a memory that stores information before it is transmitted. This information would then be released when the device is reused.  

"In short, the problem is that an adversary can program devices to store data in one protocol and leak it in subsequent protocols, in ways that are hard or impossible to counter if the devices are reused," say Barrett and co.   

This is a particular worry, they say, because there is no general technique for identifying security loopholes in standard cryptography devices.

Of course, there are a couple of simple ways round this new problem. The most obvious is to discard a quantum cryptography device after it has been used; to actually make the equipment single-use like a disposable camera. 

But Barrett and friends think this impractical: "While these attacks can be countered by not reusing devices, this solution is so costly that we query whether it is generally practical."

Another is based on the fact that the security of message is guaranteed until the device is re-used. So quantum cryptography could still be used only for secrets that need to be kept only for a short period of time, until the equipment is re-used.

Neither of these is going to stop blood pressures rising at the various government and military organisations that have bet the farm on the guarantees that quantum cryptography was thought to provide. That's not to mention the commercial organisations offering quantum cryptography such as ID Quantique.

There may be other ways round this problem that have yet to emerge. Indeed, Barrett and co's ideas will be an important driver of future work. 

In the meantime, they conclude: "In our view, the attacks are generic and problematic enough to merit a serious reappraisal of the scope for device-independent quantum cryptography as a practical technology."

That'll mean more than few a few sleepless nights over this.

Ref: arxiv.org/abs/1201.4407: Prisoners Of Their Own Device: Trojan Attacks On Device-Independent Quantum Cryptography

Correction: 

The headline of this story was edited on 30 January to clarify the scope of the article, following a request from the authors that is reproduced below. 

Dear KFC,

Our attention was drawn to your post http://www.technologyreview.com/blog/arxiv/27522/ about our recent arXiv paper.  We are of course pleased that our work has received attention and has appeared on your site.  We appreciate that it’s difficult to summarize the content of technical papers while retaining a lively blog style, and we appreciate the obvious thought and effort that went into this article, which does a good job on many points.  However, we have to say that both the headline and the article inadvertently overstate the impact of our work and are likely to mislead readers.   

Our paper does not present any attacks on quantum cryptography in general.  We present cryptographic attacks specific to so-called device-independent quantum cryptography, a theoretical idea whose aim is to promise security without trusting anything at all about the quantum devices used in the protocol.    It might be reasonable to use the headline "Serious Flaw Emerges In Device-Independent Quantum Cryptography", but to suggest that quantum cryptography in general has been revealed to be a flawed technology is simply incorrect.  If one is willing to trust and/or verify properties of the quantum devices used – as many users, in many scenarios, reasonably may - our attacks do not apply.   In particular, our attacks do not affect the security guarantees offered by commercially available quantum cryptosystems, which do not promise device-independent security.   Notwithstanding our work, quantum cryptography can still solve the problem of perfect secrecy in ways that are classically impossible, modulo some level of trust in the quantum devices.

We would not lightly request a revision, even if there were minor inaccuracies.  In this case, though, we fear there is a clear risk that much good theoretical and experimental work may be unfairly tarnished by the suggestion that all of quantum cryptography is flawed.  We would therefore be very grateful if you could update your article along the lines suggested above.  If it would be helpful, we would be more than happy to help revise the article.   

On a more minor point, we would note that (as is pretty standard in our field) the authors of the paper were listed alphabetically, with no intended implication as to seniority or level of contribution to the paper.   In the interests of fairness, we would prefer that all our names be listed, for example by replacing “Jonathan Barrett at the Royal Holloway, University of London, and a few pals” by “Jonathan Barrett, Roger Colbeck, and Adrian Kent”.  

With thanks for your time and trouble, and best wishes,

Jonathan Barrett
Roger Colbeck
Adrian Kent

The behaviour and function of proteins is largely determined by their shape.  So one of the great ongoing quests in biology is to understand and model the structure of proteins. 

That's a tricky task. Biologists currently do it using techniques such as X-ray crystallography, which requires millions of protein chains to form into a crystal.  The trouble is that most proteins don't form crystals. And even when they do, not all the molecules will be in the same conformation and so the diffraction pattern can end up being a kind of average of several different shapes.

That's why biologists know the shape of less than 2 per cent of the proteins in humans.

What's needed, of course, is a way of imaging individual proteins. One idea is to us x-rays or electron beams to do the trick and indeed some groups have had some success with this technique. But the disadvantage is that beams with an energy of a few KeV tend to destroy biomolecules so it's not clear how accurate these images can be. Nether is it possible to view the molecules over time.

Today, Jean Nicholas Longchamp and pals at the University of Zurich in Switzerland have found a way round this. These guys make the entirely sensible suggestion of imaging proteins using low energy electron beams that don't destroy biomolecules. 

At this energy, electron beams have a wavelength of a nanometre or so, making them perfect not just for imaging with atomic resolution, but for holography. 

And that's exactly what these guys have done. They've created an electron hologram of a protein molecule called ferritin--that's the football-shaped protein that stores and releases iron and is found in almost all living things.

The technique is fairly straightforward. They mix ferritin and carbon nanotubes in water which they then allow to evaporate. This leaves carbon nanotubes with single ferritin proteins bonded to them.

The evaporation takes place in a sieve-like container and leaves some of the ferritin-carrying nanotubes suspended across the holes in the sieve. That allows Longchamp and co to send the low energy electron beam from one side of the hole and then record the interference pattern on the other. 

The result is the first atomic resolution electron hologram of ferritin ever made in a non-destructive way. "We have reported the very first non-destructive investigation of an individual protein by means of  low-energy electron holography," they say.

They've even compared their images to ones of ferritin imaged with high energy electrons and are able to show the damage that the high energy bombardment causes.

That's exciting news. The problem of accurately determining the structure, and therefore the function, of proteins is a major headache for biologists and one that low energy electron holography could help to solve quickly. "The sample preparation method can be applied to a broad class of molecules," say Longchamp and friends.

They now want to improve the resolution of their technique and have a number of tricks up their sleeves that they are no doubt investigating.

Given that the techniques is relatively straightforward and inexpensive, expect to see an explosion of interest in single molecule structural biology at atomic resolution.

Ref: arxiv.org/abs/1201.4300: Non-Destructive Imaging Of An Individual Protein

The idea that our universe is embedded in a broader multidimensional space has captured the imagination of scientists and the general population alike. 

This notion is not entirely science fiction. According to some theories, our cosmos may exist in parallel with other universes in other sets of dimensions. Cosmologists call these universes braneworlds. And among that many prospects that this raises is the idea that things from our Universe might somehow end up in another.

A couple of years ago, Michael Sarrazin at the University of Namur in Belgium and a few others showed how matter might make the leap in the presence of large magnetic potentials. That provided a theoretical basis for real matter swapping. 

Today, Sarrazin and a few pals say that our galaxy might produce a magnetic potential large enough to make this happen for real. If so, we ought to be able to observe matter leaping back and forth between universes in the lab. In fact, such observations might already have been made in certain experiments.

The experiments in question involve trapping ultracold neutrons in bottles at places like the Institut Laue Langevin in Grenoble, France, and the Saint Petersburg Institute of Nuclear Physics. Ultracold neutrons move so slowly that it is possible to trap them using 'bottles' made of magnetic fields, ordinary matter and even gravity.

One reason to do this is  to measure how quickly the neutrons decay by beta emission. So physicists measure the rate at which the neutrons hit the bottle walls and how quickly this drops.   

There are two processes at work here: the rate of neutron decay and the rate at which neutrons escape from the bottle. So in the case of an ideal bottle, the rate of decay should be equal to the beta decay rate. But the bottles are not ideal so the rate of decay is always faster. 

That leaves open the possibility that there might be a third process at work: that some of the extra decay might be the result of neutrons jumping from our universe to another. 

So Sarrazin and co have used the measured decay rates to place an upper limit on how often this can happen. 

Their conclusion is that the probability of a neutron jumping ship is smaller than about one in a million.

That doesn't really say anything about whether matter swapping actually takes place. Only that if it does, it doesn't happen very often.  

However, Sarrazzin and co also say it should be straightforward to take better data that places stricter limits.

According to their theoretical work, a change in the gravitational potential should also influence the rate of matter swapping. So one idea is to carry out a neutron trapping experiment that lasts for a year or more, allowing the Earth to complete at least one orbit of the Sun.

In that time, the gravitational potential changes in a way that should influence the rate of matter swapping. Indeed, there ought to be an annual cycle. “If one can detect such a modulation it would be a strong indication that matter swapping really occurs,” they say.

That would be one of the biggest and most controversial discoveries in modern physics and one that is possible with technologies available today. 

Anyone got an old neutron bottle lying around and a bit of spare time on their hands?

Ref: arxiv.org/abs/1201.3949: Experimental Limits On Neutron Disappearance Into Another Braneworld

Nanoscale Ear Drum: Graphene Based Nanoscale Sensors

Black Hole Remnants At The LHC

Measurement of Photon Statistics with Live Photoreceptor Cells

The Problem of Colliding Networks and its Relation to Cancer

Continuum Modeling Of The Equilibrium And Stability Of Animal Flocks

Nomads of the Galaxy

The price of gas is a puzzle. Monitor the average price in gas stations in a particular city and it will vary dramatically, sometimes in a matter of hours and often in ways that appear cyclical. 

Economist have long scratched their heads over this kind of pattern. One explanation is that this behaviour emerges when two competing companies change their pricing strategy at each stage by reacting to the other. The resulting behaviours are known as Edgeworth Price Cycles.

The problem is that gas station prices are not controlled by two competing players but many competing retailers. It's easy to assume that the many-body problem produces similar patterns but nobody has been able to show this. 

Until now. Today Tiago Peixoto and Stefan Bornholdt, physicists at the University of Bremen in Germany, show how a more complicated model with many buyers and sellers reproduces this kind of behaviour. 

But it also goes further. Peixoto and Bornholdt say that when condition are right, cartel-like behaviour emerges naturally without collusion between sellers.    

Theirs is an agent-based model where all players are both buyers and sellers. The buying behaviour is determined by a value for many criteria. So players buy from a certain number of sellers but can change a seller at each step if they find one offering better value for money.

The sellers can also change their value for money parameter at each step by looking at other sellers. If they find one offering better value for money, they match it. 

Peixoto and Bornholdt study this behaviour in a population of a million agents over time period of a billion iterations and more.

The results make interesting reading.  It turns out that a crucial factor is the speed at which buyers and sellers react to the market. When buyers react quickest, sellers are forced to match the best possible value for money and prices tend to drop.

By contrast, when sellers react quickest, they are quick to copy others offering poor value for money. This reduces the number of sellers offering good value for money in a vicious cycle that drives prices as high as possible. 

This is the emergence of a cartel and it happens in these guys' model without any collusion between sellers. Instead, it is an emergent property of the market place that happens when the sellers outperform buyers in the way they react to market conditions. 

"This cartel organization is not due to an explicit collusion among agents; instead it arises spontaneously from the maximization of the individual payoffs," say Peixoto and Bornholdt.

These guys are clearly studying a parameter space displaying a rich variety of patters. And the cartel-like  region of this space has its own patterns of behaviour. It is categorised by sudden and dramatic price variations, particularly moving suddenly upwards but decaying only slowly. These variations can also appear cyclical (but are actually aperiodic).

This more or less exactly matches the price behaviour at gas stations and many other economic areas, such as electricity and natural gas prices in Europe. It would be interesting to see if this kind of behaviour emerges in other markets such as eBay.

The big question of course is what to do. Cartels that form by collusion are illegal and clearly not in the interests of the general population. 

But this work muddies the waters somewhat. If cartel-like behaviour is an emergent property of an ordinary market, how should it be controlled, regulated and punished?

The good news is that various strategies could easily be tested using this kind of agent-based model. The bad is that new strategies may themselves lead to emergent properties that are hard to spot in advance.   

An interesting new puzzle for econophysicists.

Ref: http://arxiv.org/abs/1201.3798: No Need For Conspiracy: Self-Organized Cartel Formation In A Modified Trust Game

Some 15 years ago, the American political scientist Robert Axelrod put forward a remarkable model of the way cultural diversity persists in society. His idea was that people are more likely to interact with others like them. The more similar two people are, the more likely they are to adopt each other's traits. 

That's how traits spread but it is also why diversity persists. 

Since then, the power and simplicity of Axelrod's approach has led complexity theorists to study numerous variations on the original theme. The model lends itself to computer simulation because people can be modelled as nodes on a grid influenced by those closest to them. Whatever the starting conditions, a computer can go through through millions of iterations to see how traits spread. 

Consequently, Axelrod's approach has been used to simulate behaviours ranging from the spread of language to voting behaviour.

Today, Bartlomiej Dybiec and pals at the Center for Models of Life in Copenhagen use an Axelrod-like model to examine the way cultures might have spread throughout Europe. They think about culture as a collective term for rumours, stories, ideas and fashions which are shared by people at the same location.  

The culture spreads when people at a nearby location adopt a newer set of fashions. Cultural centres survive by rebroadcasting the same fashions or repackaging old ones as new. 

Where Dybiec and co differ from Axelrod is in assuming there is a small chance that a new fashion can spontaneously arise at any location and then spread like ripples across a pond. And instead of using a square grid (or some other regular shape) they superimpose their model onto a map of Europe.

Clearly, Europe's geography places strict limits on the way cultures can spread (assuming that fashions cannot jump across water). This has important implications.

For example, Dybiec and co's model suggests that the borders between regions dominated by different cultures can change very quickly. Their maps of Europe change over a period equivalent to 50 years or so. That's exactly as has happened, even in the recent past. 

But these guys' main conclusion is that cultural centres survive longest in geographically remote regions, particularly peninsulas such as Greece and Italy. That's because it is hard for new cultures to spread into these regions. 

So, it's of more than passing interest that these regions gave birth to two of the greatest and long-lived cultures in human history--the ancient Greek and Roman empires. It also backs the idea put forward by Jared Diamond in his book Guns, Germs and Steel that the fortunes of the western world are largely the result of an accident of geography. 

Of course, Dybiec and co's model is simplistic in the extreme. It makes no allowance for the possibility that culture might spread overseas and does not take into account the effects of other geographical constraints such as rivers, mountains and climate. 

But these are nuances that, presumably, can be added into the model as it becomes more complex.  

Dybiec and co describe their model as replaying the history of Europe. It'll be interesting to see what the next replay reveals. 

Ref: arxiv.org/abs/1201.3052: Information Spreading And Development Of Cultural Centers