Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions

DOI10.1016/S0304-3975(00)00271-1zbMath0983.68068MaRDI QIDQ5958646

Marc Fischlin

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

learning algorithmcoherent setsrandom-self-reductions

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact learning of formulas in parallel
• Prediction-preserving reducibility
• Learning regular sets from queries and counterexamples
• Learning in parallel
• On being incoherent without being very hard
• Noise-tolerant parallel learning of geometric concepts
• The power of adaptiveness and additional queries in random-self- reductions
• \(p\)-Selective sets and reducing search to decision vs. self-reducibility
• When won't membership queries help?
• Queries and concept learning
• Random-Self-Reducibility of Complete Sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A theory of the learnable
• Computational limitations on learning from examples
• Cryptographic limitations on learning Boolean formulae and finite automata
• An information-theoretic treatment of random-self-reducibility
• Cryptographic hardness of distribution-specific learning

This page was built for publication: Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions