Cryptographic hardness of distribution-specific learning

DOI10.1145/167088.167197zbMath1310.94155OpenAlexW2079866219MaRDI QIDQ5248506

Michael Kharitonov

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167197

Mathematics Subject Classification ID

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

Related Items (23)

Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Learning intersections and thresholds of halfspaces ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ Learning orthogonal F-Horn formulas ⋮ On the difficulty of approximately maximizing agreements. ⋮ The unbounded-error communication complexity of symmetric functions ⋮ The complexity of properly learning simple concept classes ⋮ Learning orthogonal F-Horn formulas ⋮ Optimally learning social networks with activations and suppressions ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Learning large-alphabet and analog circuits with value injection queries ⋮ Learning a circuit by injecting values ⋮ On ε‐biased generators in NC⁰ ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Learning DNF from random walks ⋮ Learning with queries corrupted by classification noise

This page was built for publication: Cryptographic hardness of distribution-specific learning