Time-space lower bounds for two-pass learning

DOI10.4230/LIPICS.CCC.2019.22MaRDI QIDQ5091773zbMATH OpenOpenAlexFDO

Authors Sumegha Garg, Ran Raz, Avishay Tal

Publication date 27 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10844/pdf/LIPIcs-CCC-2019-22.pdf/

zbMATH Keywords

branching programlower boundsPAC learningtime-space tradeoffstwo-pass streaming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Extractor-based time-space lower bounds for learning
• Fast learning requires good memory: a time-space lower bound for parity learning
• Memory-sample lower bounds for LWE
• Multiple pass streaming algorithms for learning mixtures of distributions in \(\mathbb R^d\)
• Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in ${\mathbb R}^d$

Cites work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Entropy samplers and strong generic lower bounds for space bounded learning
• Extractor-based time-space lower bounds for learning
• Interactive channel capacity
• Time-space hardness of learning sparse parities
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(2)

• scientific article; zbMATH DE number 7087310 (Why is no real title available?)
• Memory-sample lower bounds for LWE

This page was built for publication: Time-space lower bounds for two-pass learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091773)