Learning Randomized Reductions

Created by W.Langdon from gp-bibliography.bib Revision:1.9085

@InProceedings{Erata:2026:ICML,

• author = "Ferhat Erata and Orr Paradise and Thanos Typaldos and Timos Antonopoulos and ThanhVu Nguyen and Shafi Goldwasser and Ruzica Piskac",
• title = "Learning Randomized Reductions",
• booktitle = "Proceedings of the 43rd International Conference on Machine Learning",
• year = "2026",
• editor = "Alekh Agarwal and Miro Dudik and Martin Jaggi and Sharon Li",
• address = "Seoul, South Korea",
• month = jul # " 6-11",
• keywords = "genetic algorithms, genetic programming, GPLearn, PySR, Vanilla Bitween, LLM, ANN",
• URL = "https://icml.cc/virtual/2026/poster/62376",
• URL = "https://arxiv.org/abs/2412.18134",
• code_url = "https://github.com/ferhaterata/learning-randomized-reductions",
• size = "78 pages",
• abstract = "Randomized self-reductions (RSRs) express using 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 formalise 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 percent) 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 (, , , , ) in prior work. Agentic Bitween discovers RSRs for 64 of 80 functions (80 percent), outperforming pure neural baselines in both RSR discovery and verification accuracy.",
• notes = "ICML 2026 https://icml.cc/virtual/2026",

}

Genetic Programming entries for Ferhat Erata Orr Paradise Thanos Typaldos Timos Antonopoulos ThanhVu Nguyen Shafi Goldwasser Ruzica Piskac

Citations