Memory-Sample Lower Bounds for Learning Parity with Noise

DOI10.4230/lipics.approx/random.2021.60arXiv2107.02320OpenAlexW3202425833MaRDI QIDQ6090918

Pengda Liu, Sumegha Garg, Ran Raz, Pravesh K. Kothari

Publication date: 20 November 2023

Full work available at URL: https://arxiv.org/abs/2107.02320

zbMATH Keywords

branching programspace lower boundmemory-sample tradeoffslearning parity under noise

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

This page was built for publication: Memory-Sample Lower Bounds for Learning Parity with Noise