Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

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


TR25-029 | 14th March 2025
Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach ... more >>>


TR25-028 | 12th March 2025
Satyadev Nandakumar, Subin Pulari, Akhil S, Suronjona Sarma

One-Way Functions and Polynomial Time Dimension

This paper demonstrates a duality between the non-robustness of polynomial time dimension and the existence of one-way functions. Polynomial-time dimension (denoted $\mathrm{cdim}_\mathrm{P}$) quantifies the density of information of infinite sequences using polynomial time betting algorithms called $s$-gales. An alternate quantification of the notion of polynomial time density of information is ... more >>>



Next next


ISSN 1433-8092 | Imprint