Funded Research Projects at the Chair of Informatik 1
- UMIC - Ultra High-Speed Mobile
Information and Communication
funded by the DFG, Research Cluster in the Excellence Initiative (since November 2006)
The goal of this cluster is the interdisciplinary design of Ultra high-speed Mobile Information and Communication systems (UMIC) providing an order of magnitude improvement of the perceived quality of service. Concepts and demonstrators for smart, mobile, broadband, low-cost systems will be developed which support the demanding applications of the next-decade mobile Internet.
The research program is structured into four research areas: The Mobile Applications and Services area has its focus on demanding key application classes and their interplay with the wireless transport. Representative applications of Mobile Multimedia Processing and Peer-to-peer Mobile Information Processing will be developed. The core area Wireless Transport Platform comprises the mobile devices and the wireless network architectures. The Cognitive Radio paradigm will be pursued consistently. Adaptive re-configurability at the air interface, including multi-hop capabilities, will be provided, balancing between conflicting requirements concerning bit-rates, radio coverage, processing power, and power consumption. The goal is to achieve never seen spectrum efficiency, coexistence abilities, robustness and reliability, throughput capacities, and delay performance. In the research area RF Subsystem and SoC Design advanced integrated analog and digital circuits will be developed under the conflicting regimes of flexibility and energy efficiency, taking into account constraints of future technology such as current leakage and soft errors. The extreme complexity can only be handled by integrating large numbers of processors on a single chip. The UMIC approach will require new formal methods and software tools for design, optimization, verification, and operation of components and systems which will be supported by the research area Cross Disciplinary Methods and Tools.
- Graduiertenkolleg: Algorithmische Synthese reaktiver und diskret kontinuierlicher Systeme
funded by the DFG (since July 2006)
While methods of software validation and verification are by now well established, based on adequate formal models and tested in practical applications, the approach of automatic synthesis of software (and hardware) is as yet only developed in quite rudimentary form. On the other hand, in theoretical computer science as well as in engineering disciplines a rapidly increasing stock of techniques for the development of algorithmic synthesis procedures is emerging, triggered by the demand to decrease development costs by invoking algorithmics in formal modelling frameworks. However, the approach of program synthesis is only applicable in restricted scenarios, in particular in reactive (multi-agent-)systems with low data complexity and in control systems. Central issues in the area are the establishment of system models which allow an algorithmic solution of the synthesis problem, the combination of discrete and continuous parameters in hybrid systems (as this is also familiar from verification), and the exploration of the potential of applications. The aim of the Graduate School is to unify the expertise from Computer science, mathematics, and four engineering disciplines (processor architectures, automatic control, process control engineering, train traffic systems) and to push forward the desired integration of methods. The research will be carried out in four subject areas: Algorithmics for agent-based probabilistic and hybrid systems, formal methods of reactive systems and game-theoretic methods, software development and modelling languages, and finally applications and demonstrators.
- Generalized Congestion Games: Analysis, Computation, and Evolution
funded by the German Israeli Foundation (since Jan 2007)
The project proposes to bring together two disciplines - computer science and game theory - and by doing so to address some fundamental problems of computing in the Internet era. Combining our expertise we propose to handle several complementary issues in non-cooperative multi-agent systems. Since we can show that congestion and network games with player-specific payoff functions give us the set of all strategic games, while congestion games with player-symmetric payoff functions are the most popular type of games discussed in the computer science literature, the study of generalized congestion games is a most effective way to bridge the gap between computer science and game theory.
When referring to generalized congestion games we refer both to congestion games where agents may have different payoffs functions, as well as to congestion games with uncertainty (e.g. about the number of participants or other agents' costs). The nice graph-theoretic representation of general strategic games as player-specific congestion games enables to tackle the fundamental problem of existence of solution concepts (e.g. pure strategy equilibrium or strong equilibrium) as a function of the graph structure, as well as determine the complexity of computation and the speed of convergence to solutions as a function of the graph structure. In order to deal with congestion games with incomplete information, our aim is to tackle reasoning about uncertainty in multi-agent systems when exact probabilistic information is not available. For doing so, new equilibrium concepts are to defined and applied to congestion settings.
This is a joint project with Dov Monderer and Moshe Tennenholtz from the Technion.
- Dynamic Coordination in Large Networks
funded by the DFG (since June 2010)
Large networked systems usually exhibit a high degree of decentrality. Of central importance in these scenarios are local algorithms and protocols for solving coordination problems, e.g., for optimization in mobile communication networks or the analysis and use of social networks in personalized marketing. In this project, we develop protocols and distributed algorithms as solution methods for coordination problems with rational agents in large networks. We focus on the interaction and coordination of agents with local dependencies. In particular, we consider classes of local network design, graph coloring, and load balancing problems. They capture a variety of practical applications and phenomena, such as, for instance, spectrum distribution in mobile networks or viral dynamics in social networks. The design and analysis of protocols and algorithms concentrates on aspects arising from rational behavior and convergence properties of resulting dynamics. Recent hardness results in algorithmic game theory show intractability of prominent stability concepts, so our analysis must address and develop realistic and achievable convergence criteria.