Algorithms and Complexity
Solving a computational problem requires resources and the fundamental question studied in this research area is to determine, as closely as possible, the computational difficulty of basic problems. This general question has many flavors as there are many different types of resources and many different computational problems. As larger instances of the same problem are harder to solve the key object to study is how resources consumed grow as a function of the size of the input.
The best known resource is time, which is measured as the number of elementary operations needed to solve the problem at hand. A theoretical notion, that mostly agrees well with practice, is that a problem is efficiently solvable if and only if it can be solved by an algorithm with running time that grows as a polynomial function of the size of the inputs. The most famous problem in complexity theory is whether NP equals P. In every day terms this is the question whether for any problem where a good solution can be verified efficiently can such a solution can also be found efficiently.
Results in algorithms and complexity comes in two different forms. Algorithmic results where algorithms are designed and analyzed and hardness results, where a proof, possibly using a well established conjecture such as NP is not in P, is given that a computational problem requires large resources.
Approximation algorithms
For problems where it is known that it is hard to find the globally optimal solution it is possible to have efficient algorithms that finds a solution of provably good quality. One example is to find a solution that is only 10% worse than the optimal solution. We are interested in proving both the existence and noneexistence of such algorithms. In some other situations it is interesting to look for algorithms running in mildly exponential time.
Dynamic and distributed algorithms
Modern information is hard for computers to process because it scatters in many places and changes rapidly, among other reasons. We are studying mathematical questions that might lead to better ways (algorithms) for computers to handle such information.
When information changes we speak of dynamic algorithms and when each processor only controls a small fraction of the input we call this distributed computation. Somewhat surprisingly there are similarities between these situations and we are currently exploring these.
Activities
Every summer we organize and attend the Swedish Summer School in Computer Science (https://s3cs.eecs.kth.se/), with two mini-courses by world-class experts in the beautiful Stockholm archipelago. All are welcome to apply. The application deadline is typically the first week of March.
About
Researchers
This group consists of researchers from the TCS department and the mathematics department.
Awards and Honors
Current and previous group members have received
- Knuth Prize (Håstad 2019),
- ERC starting grants (Nanongkai 2017-2021, Nordström 2012-2018),
- Gödel prizes (Håstad 2011 & 1994),
- FOCS best paper (Mömke & Svensson 2011),
- ERC advanced grant (Håstad 2009-2014),
- FOCS best student paper award (Austrin 2007), and
- STOC best student paper award (Nordström 2006).
Funding
ERC, KAW, VR