Time-space lower bounds for two-pass learning

DOI10.4230/LIPIcs.CCC.2019.22OpenAlexW2965505417MaRDI QIDQ5091773

Avishay Tal, Sumegha Garg, Ran Raz

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

lower boundsPAC learningbranching programtime-space tradeoffstwo-pass streaming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Unnamed Item

Cites Work

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

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