Approximation algorithms
Efficient algorithms with guarantees on how close their answers are to an optimum.
7 problemsAlgorithms and data structures
Methods for efficient computation and organizing information.
Explore Algorithms and data structures
Collections
Browse collectionsLimits of computation
Algorithms, computational limits and the guarantees behind decisions.
49 problemsComputing with graphs
Graph structure, approximation, counting and coordination across a network.
11 problemsBases and transversals
Rearranging bases, choosing distinct symbols and listing minimal hitting sets.
4 problemsA few problems to explore
28 totalGraph isomorphism complexity
Two graphs can look different because their vertices have different names. Can we always decide efficiently whether they have the same connections?
Matrix multiplication exponent
Multiplying two square matrices seems to require more work than writing their answer. Is the best possible asymptotic exponent actually two?
Classical integer factorization
77 = 7 × 11 is easy to check. Can a classical computer find the complete prime factorization of every integer efficiently as its written length grows?
All-pairs shortest paths complexity
Can exact shortest-path distances between every pair of vertices in a general weighted graph be computed in truly subcubic time?
Splay tree dynamic optimality
A splay tree reorganizes itself after searches. Is its total cost always within a constant factor of the best search tree that knows all requests in advance?
3SUM hypothesis
Can finding three integers with a specified additive relation be done faster than essentially quadratic time?