Reimer's inequality and tardos' conjecture

ABSTRACT

(MATH) Let f: {0,1}ⁿ → {0,1} be a boolean function. For &egr;&roe; 0 De(f) be the minimum depth of a decision tree for f that makes an error for &xie;&egr; fraction of the inputs &khar; &Egr; {0,1}ⁿ. We also make an appropriate definition of the approximate certificate complexity of f, C&egr;(f). In particular, D0(f) and C0(f) are the ordinary decision and certificate complexities of f. It is known that $D_0(f) \leq (C_0(f))^2$. Answering a question of Tardos from 1989, we show that for all $\Ge > 0$ there exists a $\Gd' > 0$ such that for all $0 \leq \Gd < \Gd'$, we have $D_\Ge(f) \leq K (C_\Gd(f))^2$ where $K = K(\Ge,\Gd) > 0$ is a constant independent of f. The algorithm used in the proof is modeled after those developed by R. Impagliazzo and S. Rudich for use in other problems.

REFERENCES

• 1: M. Blum and R. Impagliazzo. Generic oracles and oracle classes. In Proc. FOCS, pages 118--126. IEEE, 1987.
• 2: J. Hartmanis and L. Hemachandra. One-way functions, robustness, and nonisomorphism of np-complete sets. In Proc. Struct. Comp. Theory, pages 160--174. IEEE, 2000.
• 3: R. Impagliazzo and S. Rudich. personal communication.
• 4: Jeff Kahn , Michael Saks , Cliff Smyth, A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.98, July 04-07, 2000
• 5: David Reimer, Proof of the Van den Berg–Kesten Conjecture, Combinatorics, Probability and Computing, v.9 n.1, p.27-32, January 2000 [doi>10.1017/S0963548399004113]
• 6: S. Rudich. Limits on the provable consequences of one-way functions. Ph.D Thesis, Berkeley, 1983.
• 7: G. Tardos. Query complexity, or why is it difficult to separate npa π co-npa from pa by random oracles a? Comb natorica ,9:385--392, 1989.
• 8: J. van den Berg and H. Kesten. Ineq alities with applications to percolation and reliability. J. Appl. Probab., (22):556--569, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Theory

Keywords:
Reimer's inequality, certificate complexity, correlation inequalities, decision tree complexity, van den Berg--Kesten conjecture