Reproduce “Decision Tree Complexity versus Block Sensitivity and Degree” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Rahul Chugh, Supartha Podder, Swagato Sanyal
New research establishes quadratic upper bounds for deterministic decision tree complexity in relation to block sensitivity and polynomial degree for classes of Boolean functions, including graph properties, zebra functions, and functions with bounded alternation number. The work also demonstrates that proving general quadratic bounds can be reduced to proving similar bounds in communication complexity, offering a new strategic approach.
Key insights
- The cubic upper bounds on deterministic decision tree complexity (D(f)) in terms of block sensitivity (bs(f)) and polynomial degree (deg(f)) are not universally tight for all Boolean functions.
- Specific classes of Boolean functions, including graph properties, 'zebra functions,' and functions with bounded alternation number, demonstrate quadratic relationships (D(f) = O(bs(f)^2) and D(f) = O(deg(f)^2)).
- The challenge of establishing general quadratic bounds for D(f) can be approached by demonstrating similar bounds for communication complexity of composed functions, utilizing lifting theorems.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.