# Achievements of Research Area L

## Efficient Algorithms for Combinatorial and Geometric Optimisation.

Karpinski and Schudy [L:KS09] have resolved the computational status of the well-known Gale-Berlekamp game optimisation problem, answering a long time open question. As an application of the method, the first linear time approximation schemes have been designed for a general class of fragile minimisation problems including the nearest codeword problem, Unique Games, constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code [L:KS09]. Using similar methods, we have also constructed the currently best exact algorithms for feedback arc set and Kemeny rank aggregation [L:KS10].

Karpinski and co-authors designed the first polynomial-time algorithm for the perfect matching problem [L:KRS10] and the Hamiltonian cycle problem in dense k-uniform hypergraphs.

In [L:GJK10], we have considered Metropolis Glauber dynamics for sampling proper colorings of regular trees and proved almost tight (upper and lower) bounds on the mixing time. We obtained new results on sequential Markov Chain Monte Carlo methods and the bounds on their approximation errors. New geometric path coupling methods were introduced for counting independent sets and colorings in hypergraphs.

## Efficient Algorithms in Pure Mathematics.

Karpinski and Saxena [L:IKRS, L:IKS09] have intensively studied the deterministic computational complexity of the well-known problem of factoring polynomials over finite fields and its intimate connection to the generalised Riemann hypothesis (GRH). Factoring occupies a central place in computational complexity and is connected to the famous question whether BPP = P, i.e. whether randomised polynomial-time and deterministic polynomial-time classes are identical. In [L:IKRS] we developed a general technique to eliminate the GRH from various deterministic polynomial factoring algorithms over finite fields. These results represent the first progress in this direction for more than 25 years.

Implementations of Number Field Sieve methods were used by Franke and collaborators for breaking records in the field of integer factorisation, like the factorisation of a 768-Bit RSA number [L:KAF+10]. Recently, the first practical implementation of an analytic method, assuming the Riemann hypothesis, for calculating the prime counting function p(x) has been achieved and the largest known values of p(x) have been determined.

In the Naproche project (Natural language proof checking), Koepke and collaborators from computational linguistics connect ordinary mathematical texts with fully formal mathematics, using automatic provers to supply implicit arguments. Efficient automatic checking of proof steps requires the selection of small sets of possible premises. We have studied selection algorithms based on metrics within proofs graphs and on clues provided by the natural language input [L:CKKS10]. Parts of Landau’s Grundlagen der Analysis and Euclid’s Elements have been reformulated into human readable and computer checked formats.

## Structural and Computational Complexity.

Saxena joined ongoing research by Karpinski on circuit complexity and the problems of derandomisation. In particular, Saxena obtained new, interesting results related to the algebraic version of the P = NP question.

Several new results were obtained by Saxena and co-authors on the polynomial identity testing (PIT) problem for depth-3 circuits, e.g. [L:SS11]. In [L:BKS07] Karpinski and co-authors have answered an open problem of Iwama and Takaki by designing a polynomial-time algorithm for restricted instances of 3SAT which are syntactically very close to instances known to be NPhard. Very recently, a number of improved upper and lower approximation bounds have been established for subdense instances of problems like Vertex Cover, Set Cover, and Steiner Tree.

## New Models of Computation.

The concept of computability on ordinals has lead to a unifying spectrum of computabilities parametrised by bounds on ordinal time and space [L:Koe09]. Classical classes of hyperarithmetic, D1/2-, Gödel-constructible sets and others could be characterised by Ordinal Register Machines and Ordinal Turing Machines. Typical properties of the classes could be recast and proved in terms of transfinite computations [L:KS09]. The ‘Bonn InternationalWorkshop on Ordinal Computability’ (January 2007) brought together researchers in ordinal computability with eminent logicians from other fields, exploring new ways to ordinalise classical computation mechanisms.

## Further Activities.

Jointly with Research Area G, we hosted the workshop on ‘Stochastic Processes and Algorithms’ at HIM in September 2007, organised by Chayes, Eberle and Karpinski, and a workshop partially supported by HCM and BIGS on ‘Design and Analysis of Randomised and Approximation Algorithms’ at Dagstuhl in May 2008, organised by Dyer, Jerrum, and Karpinski. Several worldwide leading researchers contributed to the success of these workshops.