conference paper
Direct Sums for Parity Decision Trees
Srinivasan, Srikanth
•
Srinivasan, Srikanth
July 29, 2025
40th Computational Complexity Conference (CCC 2025)
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.
Loading...
Name
LIPIcs.CCC.2025.16.pdf
Type
Main Document
Version
Published version
Access type
openaccess
License Condition
CC BY
Size
1.04 MB
Format
Adobe PDF
Checksum (MD5)
0fa39f37cceeae6b8e3e210a1bae3b02