Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RUSSELL IMPAGLIAZZO:
All reports by Author Russell Impagliazzo:

TR24-202 | 6th December 2024
Farzan Byramji, Russell Impagliazzo

Lifting to Randomized Parity Decision Trees

We prove a lifting theorem from randomized decision tree depth to randomized parity decision tree (PDT) size. We use the same property of the gadget, stifling, which was introduced by Chattopadhyay, Mande, Sanyal and Sherif [ITCS'23] to prove a lifting theorem for deterministic PDTs. Moreover, even the milder condition that ... more >>>




ISSN 1433-8092 | Imprint