Direct Sums for Parity Decision Trees

2024/12/09 by Besselman, Tyler, Göös, Mika, Guo, Siyao +2
#Computational Complexity (cs.CC) #F.2.2 #F.2.3 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2412.06552

Abstract

Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds whenever (1) the lower bound for parity decision trees is proved using the discrepancy method; or (2) the lower bound is proved relative to a product distribution.

Related

• Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity
• Fourier Growth of Parity Decision Trees
• An inequality for the Fourier spectrum of parity decision trees
• The Decision Tree Complexity for k-SUM is at most Nearly Quadratic
• Near-optimal linear decision trees for k-SUM and related problems