Computational Sample Complexity

DOI10.1137/S0097539797325648MaRDI QIDQ4943849zbMATH OpenOpenAlexFDO

Authors Scott E. Decatur, Oded Goldreich, Dana Ron

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797325648

zbMATH Keywords

error correcting codescomputational learning theorypseudo-random functionswire-tap channelinformation vs. efficient computation

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computational complexity of counting and sampling
• Sample complexity for computational classification problems
• On the complexity of binary samples
• Sample complexity of the distinct elements problem
• scientific article; zbMATH DE number 863498
• scientific article; zbMATH DE number 3810920
• scientific article; zbMATH DE number 218387
• Computational complexity
• scientific article; zbMATH DE number 3888913
• scientific article; zbMATH DE number 3936518

Cited in

(12)

• A black-box construction of non-malleable encryption from semantically secure encryption
• Computational limitations on learning from examples
• A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
• Sample complexity for computational classification problems
• Optimal testing for planted satisfiability problems
• High-dimensional change-point estimation: combining filtering with convex optimization
• Improved, black-box, non-malleable encryption from semantic security
• Improper learning by refuting
• Fully-Simulatable Oblivious Set Transfer
• Computational sample complexity and attribute-efficient learning
• ZK-PCPs from leakage-resilient secret sharing
• On the complexity of learning a class ratio from unlabeled data

This page was built for publication: Computational Sample Complexity

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