NVTI Theory Day 2007

Friday March 9, 2007, starting at 9:30
Hoog Brabant, Utrecht (close to Central Station)

Tom Ball (Microsoft)
Nitin Saxena (CWI)
Rineke Verbrugge (RUG)
Gerhard Woeginger (TU/e)

The Dutch Asssociation for Theoretical Computer Science (NVTI) supports the study of theoretical computer science and its applications.
Again, the organization has managed to compose an interesting program with excellent speakers from the Netherlands and abroad, covering important streams in theoretical computer science. Below you will find the abstracts. NVTI Theory Day 2007 is supported by several organizations, including the Dutch research School for Information and Knowledge Systems (SIKS). All SIKS-members are invited to participate.

The full programme will be made available in due course.
Speaker : Tom Ball (Microsoft)
Title : On the Design and Implementation of Static Analysis Tools
At Microsoft, we now regularly apply a new generation of static analysis tools that can automatically identify serious defects in programs. These tools examine millions of lines of code every day, long before the software is released for general use. With these tools, we catch more defects earlier in the software process, enabling Microsoft to deliver more reliable systems. A number of these tools have been released for general use through Microsoft's Visual Studio integrated development environment as well as freely available development kits.

In this talk I will address the question: "How does one design and implement a static analysis tool chain to help people effectively address a software reliability problem?" In particular, I will identify a set of basic techniques that have proven very useful in constructing static analysis tools and have shown their worth through numerous applications. Experience with these techniques suggests we are approaching an exciting time when more people can contribute to the design and implementation of static analysis tools.
Speaker : Rineke Verbrugge (RUG)
Title : Reasoning about others in multi-agent systems
Everyone reasons about others almost daily - when leading a team, negotiating a raise, deciding whether to send email to a group of colleagues with the `cc' or the `bcc' option, or deciding how to formulate feedback tactfully. Social cognition and cooperation are essential to success in human life and increasingly essential to modern computer science.

Multi-agent systems consist of dynamically cooperating computational systems, engineered to solve complex problems that require expertise and capabilities beyond the individual components. Investigations into cooperative interactions in the behavioral sciences and computer science show a marked convergence: after all, people cooperate, machines cooperate, and mixed teams consisting of software agents, robots and people cooperate, sometimes even better than people and machines separately.

The area of multi-agent systems has started in the early nineties from distributed artificial intelligence. In recent years fields like social psychology, game theory, logic, and argumentation theory have also contributed substantially to multi-agent systems in order to understand cooperation and to design effective computational and mixed human-machine multi-agent systems.

Understanding social interactions requires rich formal models of cooperation and social cognition, because multi-agent systems consist of several agents that can act and communicate autonomously, without central control. This talk will present some recent results about cooperation and social cognition in multi-agent systems, as seen from the logical point of view.
Speaker : GJ Woeginger, TU/e
Title : Division of a shared resource
The talk discusses various notions of "fairness" when n processes have to share a common resource.
We describe and analyze some simple protocols, and compare their various advantages and disadvantages. The quality of a protocol is usually measured in the worst-case number of queries that the protocol issues to the processes. We present some lower bound results on the number of these queries, and we discuss the trade-off between keeping this number small and reaching decent approximate fairness.