Memory-sample lower bounds for LWE

DOI10.1007/978-3-031-68388-6_7MaRDI QIDQ6652965zbMATH OpenFDO

Authors Mingqi Lu, Junzhao Yang

Publication date 13 December 2024

zbMATH Keywords

learning with errorsbranching programspace lower boundmemory-sample tradeoffs

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• Extractor-based time-space lower bounds for learning
• Fast learning requires good memory: a time-space lower bound for parity learning
• Classical hardness of learning with errors
• Revisiting the hardness of binary error LWE
• Time-space lower bounds for two-pass learning

Cites work

• Extractor-based time-space lower bounds for learning
• Fast learning requires good memory: a time-space lower bound for parity learning
• Memory-sample tradeoffs for linear regression with small error
• Pseudorandom functions and lattices
• Simple schemes in the bounded storage model
• Time-space hardness of learning sparse parities
• Time-space lower bounds for two-pass learning

This page was built for publication: Memory-sample lower bounds for LWE

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