Zur Startseite der Abteilung Theoretische Informatik

We deal with frequency computations in polynomial time, or more general with resource bounded frequency computations. We investigate the first non-trivial case of the Hinrichs-Wechsung conjecture, which states that as soon as we have at least 2^d+d inputs to be queried, it does not become harder to get an answer with at most d errors, if we increase the number of inputs to be queried. This conjecture can easily be seen to hold for cases d less than 3, and it seems very hard to prove in general. We solve the problem affirmatively in the case d=3.

The paper

The executable file

The program's output

The program in pseudo-code