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:

TR25-030 | 15th March 2025
Oliver Korten, Toniann Pitassi, Russell Impagliazzo

Stronger Cell Probe Lower Bounds via Local PRGs

In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... 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 >>>




ISSN 1433-8092 | Imprint