Resource Bounded Frequency Computations with Three Errors
We deal with frequency computations in polynomial time, or more generally with resource bounded frequency computations. We investigate the first nontrivial case of the Hinrichs-Wechsung conjecture, which states that as soon as we have at least 2d + 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<3, and it seems very hard to prove in general. We solve the problem affirmatively in the case d=3 by a combination of theoretical reasoning with a highly optimized computer search.
Ulrich Hertrampf Christoph Minnameier
Abt. Theor. Informatik, University of Stuttgart, D-70569 Stuttgart, Germany Lst. Prakt. Informatik II, University of Mannheim, D-68131 Mannheim, Germany
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
72-81
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）