Math and TheoryBoolean functions and decision trees
1 research manuscript in theoretical computer science. Catalogue areas: Boolean functions and decision trees.
Results in Boolean functions and decision trees
Logarithmic influence bounds and variance counterexamples for Boolean decision-tree covariance
DisprovedWan–Wright–Wu log₂ k variance bound for read-k decision-tree covariance
Read-k decision trees with no repeated coordinate on a path have tree covariance at most I(f) log₂ k, sharp for k = 2^d, while exact read-3 trees refute the proposed bound Var(f) log₂ k.
Manuscript: Logarithmic influence bounds and variance counterexamples for Boolean decision-tree covarianceLean proof: Logarithmic influence bounds and variance counterexamples for Boolean decision-tree covarianceVerification: Logarithmic influence bounds and variance counterexamples for Boolean decision-tree covariance
Other subjects
Discrete analysis, tilings, probability and entropyOptimizationQuantum informationValuation theoryMatrix theoryMatroid theorySampling algorithms and information theoryGraph theory and graph polynomialsInteger sequences and combinatoricsFinite geometryQuadratic forms and number theoryInequalities and real analysisProof complexityFair divisionStochastic thermodynamics