The theory of computability was launched in the 1930s by a group of logicians who proposed new characterizations of the ancient idea of an algorithmic process. The theoretical and philosophical work that these thinkers carried out laid the foundations for the computer revolution, and this revolution in turn fuelled the fantastic expansion of scientific knowledge in the late twentieth and early twenty-first centuries. 

The 1930s revolution was a critical moment in the history of science: ideas conceived at that time have become cornerstones of current science and technology. Since then, many diverse computational paradigms have blossomed, and still others are the object of current theoretical enquiry - massively parallel and distributed computing, quantum computing, real-time interactive asynchronous computing, relativistic computing, hypercomputing, nano-computing, DNA computing, neuron-like computing, computing over the reals, computing involving quantum random-number generators. The list goes on; few of these forms of computation were even envisaged during the 1930s' analysis of computability.

The fundamental question tackled by the group is: do the concepts introduced by the early pioneers provide the logico-mathematical foundation for what we call computing today, or is there a need to overhaul the foundations of computing to fit the twenty-first century?

 

 

The last decade has seen the emergence and growth of a new interdisciplinary field of research often termed "Algorithmic Game Theory". This field lies at the crossroads of computer science, game theory, and economics; a combination which is necessary for addressing many of the challenges posed by the Internet. Not only is this field full of intellectual excitement internally, and not only has it already begun to intellectually influence the three parent disciplines, but it also has significant implications for the Internet, as evidenced by the large number of researchers in the field hired by Google, Yahoo, and Microsoft.

At the approximate age of ten years, it seems that the field of Algorithmic Game Theory is maturing. The goal of this group is to elucidate the main challenges of the field and attempt to chart the future course of the field for the next decade.

Some research topics that will be explored:

- Networks with contagious risk, the different aspects of how the evaluation of the Generalized Second Price mechanisms are used for selling ads on the Internet, and the understanding of the performance of simple auctions and modeling auctions used in practice (Eva Tardos)

- Interviewing in stable matching problems and cost-sharing mechanisms (Nicole Immorlica)

- Sketching valuation functions, the equilibria of simple market mechanisms, and optimal multi-item auctions (Noam Nisan)

- Auction design for agents with uncertain, private values (Anna Karlin)

- A general framework for computing optimal correlated equilibria in compact games, computing Nash equilibria of action-graph games via support enumeration, mechanical design and auctions, and computational equilibrium analysis of voting games (Kevin Leyton-Brown)

- Envy-free mechanisms for multiunit auctions with budgets, cost sharing games with capacitated network links, and game theoretic perspectives of the facility location problem (Michal Feldman)

- Bargaining in networks (Amos Fiat)

 

The concept of computation plays a major role in the current research of brain function. As Peter Stern and John Travis wrote in "Of Bytes and Brains" in Science (2006:75), "Computational neuroscience is now a mature field of research. In areas ranging from molecules to the highest brain functions, scientists use mathematical models and computer simulations to study and predict the behaviour of the nervous system". Another typical statement of the centrality of computation to the study of the brain can be found in Christof Koch's introduction to his book, The Biophysics of Computation: "The brain computes! This is accepted as a truism by the majority of neuroscientists engaged in discovering the principles employed in the design and operation of nervous systems".

However, the instrumental and explanatory role of the notion of computation in neuroscience is still in need of analysis and clarification. There are various different ways in which computational models and the notion of computation are applied in the study of the brain, and it is important for these to be distinguished and assessed. For example, as attested by the two quotations in the previous paragraph, the term "computational neuroscience" may refer to two different enterprises: Stern and Travis talk of the extensive use of computer models and simulations in the study of brain functions, while Koch gives expression to the view that the modelled system itself, i.e. the brain, computes. Both perspectives are part of what is one of the major scientific projects of our time -- the effort to explain how the brain, as a physical systme, works. However, together these two perspectives manifest a duality that is not found in other sciences, where e.g. stomachs, planetary systems, and tornadoes are studied through the use of computational models and simulations, but are not perceived as computing systems.

Thus what is called for is a systematic, philosophical analysis of the role of computation in neuroscience. What is the exact role of computer models and simulations in brain research? What is the explanatory role of the view that the brain itself performs computations? How are the two enterprises (of using computer models in brain research, and of viewing the brain as a computer) related: Do they employ the same concept of computation? Are they components of a wider exaplanatory framework? These are the questions that our research group set out to consider, discuss, and offer answers to.