Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOM LOCAL FUNCTIONS:
Reports tagged with random local functions:
TR25-139 | 3rd October 2025
Kel Zin Tan, Prashant Nalini Vasudevan

Improved Search-to-Decision Reduction for Random Local Functions

A random local function defined by a $d$-ary predicate $P$ is one where each output bit is computed by applying $P$ to $d$ randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich as candidates for low-complexity one-way ... more >>>




ISSN 1433-8092 | Imprint