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

TR25-031 | 19th March 2025
Shuichi Hirahara, Nobutaka Shimizu

Error-Correction of Matrix Multiplication Algorithms

Given an efficient algorithm that correctly computes a tiny fraction of the entries of the matrix multiplication of a small fraction of two matrices, can one design an efficient algorithm that computes matrix multiplication exactly for all the matrices? In this paper, we present such ``worst-case exact to average-case approximate'' ... more >>>


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



previous PreviousNext next


ISSN 1433-8092 | Imprint