# Learning Randomized Reductions

Source: [Learning Randomized Reductions](<https://www.sota2.com/research/paper/68fa7ba01e209131cea896d2>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-06-05T05:00:04.417Z

Authors: Ferhat Erata, Orr Paradise, Thanos Typaldos, Timos Antonopoulos, ThanhVu Nguyen, Shafi Goldwasser, Ruzica Piskac

Published: 2024-12-24T03:42:53.000Z

## Abstract

Randomized self-reductions (RSRs) express $f(x)$ using $f$ evaluated at random correlated points, enabling self-correcting programs, instance-hiding protocols, and applications in complexity theory and cryptography. Yet discovering RSRs has required manual expert derivation for over 40 years, limiting their practical use. We present Bitween for automated RSR learning. First, we formalize RSR learning with sample complexity analysis under correlated sampling. Second, we develop Vanilla Bitween, which integrates multiple backends (linear regression, genetic programming, symbolic regression, and mixed-integer programming). The linear regression backend outperforms the others, discovering RSRs for 43 of 80 functions (54%) in RSR-Bench, our benchmark suite, including the first known reduction for sigmoid. Third, we introduce Agentic Bitween, a neuro-symbolic approach where LLM agents propose novel query functions beyond the fixed set ($x+r$, $x-r$, $x \\cdot r$, $x$, $r$) in prior work. Agentic Bitween discovers RSRs for 64 of 80 functions (80%), outperforming pure neural baselines in both RSR discovery and verification accuracy.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Randomized Reductions Discovery on RSR-Bench](<https://www.sota2.com/research/sota/randomized-reductions-discovery-on-rsr-bench.md>): Randomized Reductions Discovery; RSR-Bench; RSR Count: 793.

- [Randomized Symbolic Reduction on RSR-BENCH Algebraic Structures v1.0 (17 functions)](<https://www.sota2.com/research/sota/randomized-symbolic-reduction-on-rsr-bench-algebraic-structures-v1-0-17-functions.md>): Randomized Symbolic Reduction; RSR-BENCH Algebraic Structures v1.0 (17 functions); RSR Count: 170.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2412.18134>)

[PDF](<https://arxiv.org/pdf/2412.18134.pdf>)