Optimal Cryptographic Hardness of Learning Monotone Functions

DOI10.1007/978-3-540-70575-8_4MaRDI QIDQ3521906zbMATH OpenOpenAlexFDO

Authors Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Andrew Wan, Hoeteck Wee, Rocco A. Servedio

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_4

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Cryptography (94A60)

Recommendations

• Optimal cryptographic hardness of learning monotone functions
• Learning circuits with few negations
• Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
• Cryptographic limitations on learning Boolean formulae and finite automata
• Learning from satisfying assignments

Cited in

(6)

• Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Optimal cryptographic hardness of learning monotone functions
• Cryptographic limitations on learning Boolean formulae and finite automata
• Approximate resilience, monotonicity, and the complexity of agnostic learning
• Hardness of learning AES with gradient-based methods

This page was built for publication: Optimal Cryptographic Hardness of Learning Monotone Functions

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