自动学习随机化归约，让机器发现复杂函数的自纠错方法。
Learning Randomized Reductions
- 用线性回归等多后端结合，自动寻找函数归约路径。
- 在80个函数中发现54个归约式，包括首个sigmoid归约。
- 引入大模型生成新查询函数，准确率远超纯神经方法。
随机化自归约（RSRs）通过在相关随机点上评估函数f，来表达f(x)，可用于自校正程序、实例隐藏协议以及复杂度理论与密码学中的应用。然而，过去40多年来发现RSR始终依赖人工专家推导，限制了其实际应用。本文提出Bitween，实现自动化RSR学习。首先，我们在相关采样下对样本复杂度进行了形式化分析；其次，开发Vanilla Bitween，整合线性回归、遗传编程、符号回归和混合整数规划等多种后端。其中线性回归后端表现最佳，在我们提出的基准测试集RSR-Bench中的80个函数里成功发现43个（54%）归约式，包括首个已知的sigmoid函数归约。第三，提出Agentic Bitween，一种神经符号方法，由大语言模型代理生成超越传统固定查询函数集（x+r, x−r, x·r, x, r）的新查询函数。Agentic Bitween在80个函数中发现64个（80%），在归约发现与验证准确率上均优于纯神经基线。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。