Michael Kharitonov
- 1.W. Alexi, B. Chor, O. Goldreich, and C. Schnorr. RSA and Rabin functions:certain parts are as hard as the whole. SIAM J. on Com#uting, 17:194-209, 1988. Google Scholar
Digital Library
- 2.D. Angluin. Lecture notes on the complexity of some problems in number theory. TeclmJcal report, Yale University, Report No. TR-243, 1982.Google Scholar
- 3.D. Angluin. Leaxning regular sets from queries and counterexaxnples. Information and Computation, 75:87--106, 1987. Google ScholarDigital Library
- 4.D. Angluin and M. Kharitonov. When Won't Membership Queries Help? In Proc. o} the 23d STOC, pages 444--454. ACM, 1991. Google ScholarDigital Library
- 5.P. W. Beame, S. A. Cook, and H. J. Hoover. Log depth circuits for division and related problems. SIAM J. on Comporting, 15:994-1003, 1986. Google ScholarDigital Library
- 6.A. Blum. Separating Distribution-Free and Mistake- Bounded Learning Models over the Boolean Domain In Proc. of the 31st FOGS, pages 211-218. IEEE, 1990.Google Scholar
- 7.L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random number generator. SIAM J. Comput., 15:364-383, 1986. Google ScholarDigital Library
- 8.J. L. Carter and M. N. Wegman. Universal Classes of Hash Functions. JCSS, 18:143-154, 1979.Google Scholar
- 9.A. K. Chandra, L. J. Stockmeyer, U. Vishkin. Constant depth reducibility. SIAM J. on Compuling, 13:423-432, 1984.Google ScholarCross Ref
- 10.M. Furst, J. Jackson, and S. Smith. Improved learning of AC~ functions. In Proc. o} the dth COLT, pages 317-325. Morgan Kaufmann, 1991. Google ScholarDigital Library
- 11.O. Goldreich, S. Goldwasser, and S. Micali. How to constJruct random functions. J. A CM, 33:792-807, 1986. Google ScholarDigital Library
- 12.O. Goldreich and L. Levin. A hard-core predicate fox' all one-way functions. In Proc. of the 21st STOC, pages 25--32. ACM, 1989. Google ScholarDigital Library
- 13.J. Hastad. Computational limitations }or small depth circuits. MIT Press, 1986. Ph.D. thesis.Google Scholar
- 14.R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random Number Generation from Any One-way Function. In Proc. 21st STOC, pages 12-24. ACM, 1989. Google ScholarDigital Library
- 15.M. Kearns and L. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proc. 21st STOC, pages 433-444. ACM, 1989. Google ScholarDigital Library
- 16.M. Kharitonov. Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution In Proc. o} the 5th COLT. Morgan Kaufmann, 1992. Google ScholarDigital Library
- 17.W. LeVeque. Fundamentals of Number Theory. Addison- Wesley, 1977.Google Scholar
- 18.L. Levin. Manuscript.Google Scholar
- 19.N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. In Proc. of the 30th FOGS, pages 574-579. IEEE, 1989.Google ScholarDigital Library
- 20.M. Luby. Pseudo-randomness and Applications. Princeton University Press, to appear. Google ScholarDigital Library
- 21.Y. Maxtsour. An O(nl~g log n) Learning Algorithm for DNF under the uniform distribution. In Proc. of the 5th COLT. Morgan Kaufmarm, 1992. Google ScholarDigital Library
- 22.L. Pitt and M. Warmuth. Prediction-preserving reducibility. JCSS, 41:430-467, 1990. Google ScholarDigital Library
- 23.J. Reif. On threshold circuits and polynomial computation. In Proc. of the 2d IEEE Structures, pages 118-123. IEEE, 1987.Google Scholar
- 24.R. E. Schapire. The strength of weak learnability. In Proc. of the 30th FOGS, pages 28-33. IEEE, 1989.Google ScholarDigital Library
- 25.L. (3. Valiant. A theory of the learnable. C. A CM, 27:1134- 1142, 1984. Google ScholarDigital Library
- 26.U. V. Vazirani and V. V. Vaziraxti. Efficient and seeare pseudo-random number generation, in Proc. of ghe 25#h FOGS, pages 458-463. IEEE, 1984.Google Scholar
Index Terms
- Cryptographic hardness of distribution-specific learning
Recommendations
Cryptographic hardness for learning intersections of halfspaces
We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which ...
Order-Revealing Encryption and the Hardness of Private Learning
TCC 2016-A: Proceedings, Part I, of the 13th International Conference on Theory of Cryptography - Volume 9562An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC ...
Comments