Complexity is a central topic both in mathematics and in computer science. It appears in vari-ous forms: there is combinatorial complexity (number) of mathematical structures; description complexity (the possibility of encoding a structure succinctly or visualizing it clearly); and al-gorithmic complexity (running time, storage). The goal of this interdisciplinary Research Train-ing Group is to integrate several aspects or facets of complexity into a unified research and training program. In recent years it has become apparent that the different approaches to complexity are interwoven, and significant new insights are possible by combining several viewpoints. The main educational goal of the Research Training Group is the training of a new generation of highly qualified scientists. We want to offer the students an exciting research arena and give them a broad and multi-faceted view on complexity. The group is conceived as an international Research Training Group throughout, regarding the prospective students, the postdoctoral researchers, as well as the research collaboration with foreign partners, the guest program and the lectures and classes (in Eng-lish). Several colleagues who treat essential aspects of complexity as part of their work have recently come to work in Berlin. Together with the already existing strong group of researchers in Discrete Mathemat-ics and Theoretical Computer Science, we have grasped the opportunity to design this new program. We have included a large number of researchers in order to ensure a broad coverage of the area. Additionally, we want the students as well as the junior faculty (early-career researchers) to play an active role in running and shaping the program.