Paper Info
Title
Reimer's inequality and tardos' conjecture
Abstract
(MATH) Let f: {0,1}n → {0,1} be a boolean function. For ε&roe; 0 De(f) be the minimum depth of a decision tree for f that makes an error for &xie;ε fraction of the inputs &khar; &Egr; {0,1}n. We also make an appropriate definition of the approximate certificate complexity of f, Cε(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 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.
Year
DOI
Venue
2002
10.1145/509907.509942
STOC
Keywords
Field
DocType
decision tree,boolean function
Boolean function,Discrete mathematics,Decision tree,Combinatorics,Existential quantification,Conjecture,Mathematics,Certificate
Conference
ISBN
Citations 
PageRank 
1-58113-495-9
3
0.52
References 
Authors
3
1
Name
Order
Citations
PageRank
Clifford Smyth1246.91