Title: Automating the Discovery of Randomized Reductions

Abstract:

Randomized self-reductions (RSRs) allow a function $f(x)$ to be expressed through evaluations of $f$ at random, correlated points. This capability facilitates self-correcting programs, instance-hiding protocols, and various applications within complexity theory and cryptography. However, for more than four decades, the discovery of RSRs has relied exclusively on manual derivation by experts, a bottleneck that has restricted their practical deployment. To address this, we introduce Bitween, a system designed for the automated learning of RSRs.

Our approach begins by formalizing the problem of RSR learning, including a sample complexity analysis under correlated sampling conditions. We then present Vanilla Bitween, a framework that leverages multiple computational backends, including linear regression, genetic programming, symbolic regression, and mixed-integer programming. Among these, the linear regression backend demonstrates superior performance, successfully identifying RSRs for 43 out of 80 functions (54%) in RSR-Bench, our newly established benchmark suite. Notably, this method discovered the first known reduction for the sigmoid function.

Furthermore, we propose Agentic Bitween, a neuro-symbolic method that utilizes Large Language Model (LLM) agents to generate novel query functions. This extends beyond the fixed sets of queries—such as $x+r$, $x-r$, $x \cdot r$, $x$, and $r$—used in previous research. Agentic Bitween achieves an 80% discovery rate, identifying RSRs for 64 of the 80 functions in the benchmark. This performance surpasses pure neural baselines in both the accuracy of RSR verification and the rate of successful discovery.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC