Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution

DOI10.1006/jcss.1995.1046zbMath0837.68096OpenAlexW3142725347MaRDI QIDQ1894721

Michael Kharitonov

Publication date: 29 April 1996

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1046

zbMATH Keywords

learning \(AC^ 1\) circuitspseudo-random function generator

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25)

Related Items (7)

Order-Revealing Encryption and the Hardness of Private Learning ⋮ Pac-learning non-recursive Prolog clauses ⋮ Computational sample complexity and attribute-efficient learning ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Pseudorandom Functions: Three Decades Later

This page was built for publication: Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution