Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR24-203 | 9th December 2024
Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, Weiqiang Yuan

Direct Sums for Parity Decision Trees

Direct sum theorems state that the cost of solving $k$ instances of a problem is at least $\Omega(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 ... more >>>


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 >>>


TR24-201 | 4th December 2024
Marius Zimand

On one-way functions and the average time complexity of almost-optimal compression

Revisions: 1

We show that one-way functions exist if and only there exists an efficient distribution relative to which almost-optimal compression is hard on average. The result is obtained by combining a theorem of Ilango, Ren, and Santhanam [STOC 2022] and one by Bauwens and Zimand [JACM, 2023].

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint