Deutsche Forschungsgemeinschaft (DFG)

36 months

The past decades have seen an enormous growth of stored data, posing a huge challenge to computational power. Moreover, these data are often stored remotely, making access costly. In this context, even just reading the whole input once may be infeasible, and many algorithms that were traditionally classified as ‘efficient’ become intractable. Often in practice, heuristics are used that have a feasible running time but sacrifice all guarantees on the accuracy of the solution.

This project proposes a foundational approach, via the area of property testing, using a novel combination of methods including logic and graph structure, towards the design of classes of highly efficient algorithms with guarantees on accuracy and performance, as well as proving lower bounds.

Property Testing aims at designing algorithms that derive global information on the structure of the input by only exploring local parts of it. These algorithms are randomised and allow for a small error. 
Nevertheless, they come with guarantees. The complexity measure that is predominantly used is the query complexity, i.e. the number of accesses to the input that the algorithm makes, depending on the input size, and the aim is to obtain sublinear or even constant query complexity. 
Property testing can be seen as solving relaxed decision problems. The goal is to determine with high probability correctly, whether the input has a given property or is (structurally) far from having it.

Property testing of dense graphs is well understood via Szemeredi's regularity lemma. The starting point of this project is property testing on sparse and general graphs. This area is much less understood. A variety of models have been proposed, the most prominent being the bounded degree graph model. Despite some effort, a characterisation of the properties testable in this model still remains elusive. We will work towards this.

Newman and Sohler proved a general result, showing that every property of planar graphs (and, more generally, of hyperfinite graphs) is testable with constant query complexity in this model. This theorem can be seen as a meta-theorem, as it treats many properties simultaneously. 
However, it does not take into account the running time. Indeed, there are uncomputable properties that are testable by the theorem. However, in practice bounding the running time is very desirable. Moreover, many testing algorithms for individual properties have sublinear or even constant running time. This project aims to explain why and when this is the case. Using the approach through logic, we will provide meta-theorems for properties on classes of inputs with sublinear and even constant time algorithms. We will study testability in different models, propose new models, and extend research from graphs to relational structures (that include e.g. hypergraphs and relational databases) and beyond, including initiating property testing for graph databases.