Can I read Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution on EtoBox?
Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution by M. Kharitonov is a Computer Science article available to read on EtoBox.
What is Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution about?
We investigate cryptographic lower bounds on the number of samples and on computational resources required to learn several classes of boolean circuits on the uniform distribution. Under the assumption that solving \(n \times n^{1+\epsilon}\) subset sum is hard, we construct (using the results of Impagliazzo and Naor and Goldreich, Goldwasser, and Micali) a pseudo-random function generator that can be computed by shallow boolean circuits. From this we conclude that learning \(A C^{1}\) circuits on the uniform distribution requires \(\Omega\left(n^{\log \log n}\right)\) different samples, or, alternatively, that learning \(A C^{1}\) circuits on the uniform distribution with a polynomial number of samples is as hard as solving \(n \times n^{\prime+4}\) subset sum. We also show that no algorithm can learn \(N C^{1}\) circuits on the uniform distribution with a polynomial number of samples. Using the weaker assumption that solving \(n \times(1+\epsilon) n\) subset sum is hard, we show that the class of \(N C\) circuits can not be learned with \(n^{\log ^{\prime} n}\) samples for any constant \(c\). c 1995 Academic Press, Inc.
Who reads Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- M. Kharitonov
- Publisher
- Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)
- Published
- 1995
- Language
- EN
- Field
- Computer Science (Physical Sciences)