Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Direct Sums for Parity Decision Trees
 
conference paper

Direct Sums for Parity Decision Trees

Besselman, Tyler
•
Göös, Mika  
•
Guo, Siyao
Show more
Srinivasan, Srikanth
•
Srinivasan, Srikanth
July 29, 2025
40th Computational Complexity Conference (CCC 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.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
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

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés