SMS-årsmötet i Lund 1-2 juni 2007: abstracts

On solving over-determined linear systems in small fields
Johan Håstad, KTH

Consider a system of linear equations over the integers modulo a prime p. If there is a solution that satisfies all equations it is easy to find an assignment that indeed satisfies all the equations. This can be done by Gaussian elimination. If there is no such assignment we might be interested in satisfying as many equations as possible. This problems turns out to be computationally difficult in a very strong sense. Even if we are guaranteed that there is an assignment that satisfies 99% of the equations it turns out to be computationally difficult to find an assignment that satisfies substantially more than a fraction 1/p of the equations. Note that satisfying a fraction 1/p of the equations is not very impressive as a random assignment satisfies this number of equations on the average.

The mathematics of making decisions
David Sumpter, Uppsala universitet

What is the first thing you do when deciding what brand of mobile phone to buy? For many people, the answer is that they ask their friends and are more likely than not make the same choice as they did. Animals use similar rules in their decisions about what to do, the more individuals that have made a particular choice about where to live or where to eat, the more likely others are to copy them. Decision-making can thus be described as positive feedback with the probability of performing a particular action an increasing function of those making the choices before. Depending on the shape of this function there are different outcomes for decisions. For example, I show that bi-stability can arise where the chosen option is determined by a few initial choices and when we introduce different qualities to the options it is not always the best one that is chosen. I also look at the case where the two options change quality in time and identify the best strategy for either exploring new options or exploiting known choices. Finally, I look at ways of weighting the actions of others so as to be able to detect arbitrarily small changes in the quality of the choices. Mathematically, the talk will lead take us from positive feedback and bifurcations to the 'one-sided' Ising model.