Statement

In recent years, there was an emergence of algorithms that fundamentally influence our everyday lives, starting from the web search, through fast route planning used in GPS, and ending with automatic stock trading algorithms with whom human traders are unable to compete. As more and more aspects of our lives are stored digitally, algorithms for managing this data efficiently will grow in importance.

We already have witnessed many times a situation in which a single ingenious algorithm changed the whole landscape of an area and solve real life problems that seemed unsolvable before. Prominent examples here include Google’s PageRank algorithm that revolutionized the web search (and was a cornerstone of Google’s success), or the stable marriage algorithm that is guiding the National Resident Matching Program in the US.

In general, algorithms play a key role in breakthroughs in fundamental scientific questions as well as in high impact applications of them (e.g., sequencing, indexing and searching millions of individual genomes for treating cancer, or large physical simulations). Handling and processing any kind of digital information requires efficient algorithms as shown, e.g., by IGAFIT member Hannah Bast who developed a semantic full text search engine.1

This is why continuing the foundational research in algorithms and coping with big data is of critical importance and requires much more engagement than before. This importance has already been realized in many contexts. For instance, US National Science Foundation has launched the call Critical Techniques and Technologies for Advancing Big Data Science and Engineering (BIGDATA) that includes an explicit call for projects on foundations. Also, German Research Foundation (DFG) is funding research projects on algorithmic aspects of Big Data within the Schwerpunktprogramm 1736: Algorithms for Big Data. However, much more algorithmic research is funded in the US than in Europe as the following examples show.

In 2012, the Simons Foundation provided a grant of 60 million USD to fund at UC Berkeley the Simons Institute for the Theory of Computing2, a new research institute that focuses on scientific activities in theoretical computer science and related fields to “explore deep unsolved problems about the nature and limits of computation”. One of the key themes pursued by this institute is supporting fundamental research on algorithms, especially in the context of big data.3,4,5

Microsoft, Google, Yahoo, IBM and many other US high-tech companies provide substantial resources to support fundamental research in algorithms and their applications in their own research labs in Silicon Valley, New York, Boston, etc., with over a hundred researchers working on algorithmic problems and numerous research projects that bring the outcome of fundamental research to the frontier of modern technologies and directly impact our everyday life.

Fundamental research in algorithms and complexity is highly valued in the US as a central driver of modern innovations in the IT industry. Most (if not all) top 10 computer science departments in the US have 5 or more faculty working in this area (a number not seen at almost any place in Europe) and the influence of the advances in this field is demonstrated by awarding numerous prizes to such work, including most prestigious ones such as Turing awards, Nevanlinna prizes, Knuth prizes, Goedel prizes and the ACM Doctoral Dissertation Awards. Also, in the recent “Report to the President and Congress: Designing a Digital Future: Federally Funded R&D in Networking and IT” it was recognized that the progress in algorithms beats even the progress stemming from the Moore’s Law, and the report suggests that for next generation computer systems it is important to “conduct basic research in hardware, in hardware/software systems, in algorithms, and in both systems software and applications software”.7

One should observe that all these aspects make the US a very attractive place for the training and employment of algorithms researchers. This leads to a “brain drain” and a shortage of talent within Europe. Thus, it is currently more likely that the next Google or Akamai8 will be started in the USA rather than in Europe. We therefore need to reverse this trend by strongly encouraging research in the foundations of algorithms in Europe. For this reason we started IGAFIT, the Interest Group on Algorithmic Foundations of Information Technology, which aims to integrate the European algorithms community and to identify key research challenges and themes. The main scientific objectives of IGAFIT are:

  • Designing more efficient algorithmic solutions for real world driven applications.
  • Developing the use cases and usage guidelines for different algorithmic tools.
  • Creation of a modern algorithmic curriculum and textbooks that appropriately address current algorithmic challenges.
  • Training young scientists and PhD students with a proper understanding of the foundations of algorithms with stress on big data applications.
  • Raising awareness and visibility for the algorithmic challenges within other scientific communities that are end-users of algorithmic research, e.g., in the natural sciences the computational problems are more and more becoming the major obstacle.

Currently, IGAFIT has 36 members all of whom play a leading role in algorithmic groups around Europe. Three of our members have received ERC Advanced Grants: Fedor Fomin, Monika Henzinger, Elias Koutsoupias, and one has received an analogous national grant: Mikkel Thorup. Two of our members have received ERC Consolidator Grants: Nikhil Bansal and Rasmus Pagh. Four of our members have received ERC Starting Grants: Fabrizio Grandoni, Piotr Sankowski, Christian Sohler, and Ola Svensson. Our members are leading two Google Focused Research Awards, one Microsoft Research Grant and numerous national research grants. In particular, they lead the following national excellence research centres or programmes in algorithms: the Danish Center for Massive Data Algorithmics (MADALGO), the Israeli Center of Research Excellence in Algorithms (I-CORE), and the newly established German priority programme on algorithms for big data (DFG-SPP1736).

 

[1] http://broccoli.informatik.uni-freiburg.de

[2] http://simons.berkeley.edu

[3] http://simons.berkeley.edu/programs/bigdata2013

[4] http://simons.berkeley.edu/programs/spectral2014

[5] http://simons.berkeley.edu/programs/complexity2015

[6] for the best PhD thesis in computer science; http://awards.acm.org/doctoral_dissertation.

[7] p. 71-72 in http://www.whitehouse.gov/sites/default/files/microsites/ostp/pcast-nitrd-report-2010.pdf

[8] Akamai Technologies, Inc. is an Internet content delivery network headquartered in Cambridge, Massachusetts, in the United States. Akamai’s network is one of the world’s largest distributed-computing platforms, responsible for serving between 15 and 30 percent of all web traffic.