Optimal cryptographic hardness of learning monotone functions

DOI10.4086/TOC.2009.V005A013MaRDI QIDQ3002813zbMATH OpenOpenAlexFDO

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

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2009.v005a013

zbMATH Keywords

analysis of Boolean functionscomputational learning theorycryptographyhardness amplificationlower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32) Cryptography (94A60)

Recommendations

• Optimal Cryptographic Hardness of Learning Monotone Functions
• Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
• Learning Monotone Decision Trees in Polynomial Time
• Learning circuits with few negations
• Cryptographic limitations on learning Boolean formulae and finite automata

Cited in

(6)

• On the nonlinearity of monotone Boolean functions
• Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
• Optimal Cryptographic Hardness of Learning Monotone Functions
• scientific article; zbMATH DE number 1024063 (Why is no real title available?)
• The uniform hardcore lemma via approximate Bregman projections
• 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 Q3002813)