Products and Help Bits in Decision Trees

DOI10.1137/S0097539795282444zbMath0918.68026OpenAlexW2126244834MaRDI QIDQ4229422

Noam Nisan, Steven Rudich, Michael E. Saks

Publication date: 22 February 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795282444

zbMATH Keywords

decision treeshelp bits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Extremal combinatorics (05D99)

Related Items (10)

The cell probe complexity of succinct data structures ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Derandomized parallel repetition theorems for free games ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Sharing one secret vs. sharing many secrets. ⋮ Improved direct product theorems for randomized query complexity ⋮ The value of help bits in randomized and average-case complexity ⋮ Unnamed Item ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ On Yao’s XOR-Lemma

This page was built for publication: Products and Help Bits in Decision Trees