Cryptographic hardness of distribution-specific learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cryptographic hardness of distribution-specific learning

Full text

Pdf (1.12 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 372 - 381

Year of Publication: 1993

ISBN:0-89791-591-7

Author

Michael Kharitonov

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 41, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167197 What is a DOI?

Warning: The download time has expired please click on the item to try again.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
	2	D. Angluin. Lecture notes on the complexity of some problems in number theory. TeclmJcal report, Yale University, Report No. TR-243, 1982.
	3	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	4	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
	5	Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
	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.
	7	L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
	8	J. L. Carter and M. N. Wegman. Universal Classes of Hash Functions. JCSS, 18:143-154, 1979.
	9	A. K. Chandra, L. J. Stockmeyer, U. Vishkin. Constant depth reducibility. SIAM J. on Compuling, 13:423-432, 1984.
	10	Merrick L. Furst , Jeffrey C. Jackson , Sean W. Smith, Improved learning of AC0 functions, Proceedings of the fourth annual workshop on Computational learning theory, p.317-325, August 05-07, 1991, Santa Cruz, California, United States
	11	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	12	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	13	J. Hastad. Computational limitations }or small depth circuits. MIT Press, 1986. Ph.D. thesis.
	14	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	15	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	16	Michael Kharitonov, Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.29-36, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130388]
	17	W. LeVeque. Fundamentals of Number Theory. Addison- Wesley, 1977.
	18	L. Levin. Manuscript.
	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.
	20	Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
	21	Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130391]
	22	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	23	J. Reif. On threshold circuits and polynomial computation. In Proc. of the 2d IEEE Structures, pages 118-123. IEEE, 1987.
	24	R. E. Schapire. The strength of weak learnability. In Proc. of the 30th FOGS, pages 28-33. IEEE, 1989.
	25	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	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.

CITED BY 20

	Ronald L. Rivest , Yiqun Lisa Yin, Being taught can be faster than asking questions, Proceedings of the eighth annual conference on Computational learning theory, p.144-151, July 05-08, 1995, Santa Cruz, California, United States
	Jeffrey C. Jackson , Adam R. Klivans , Rocco A. Servedio, Learnability beyond AC⁰, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Marc Fischlin, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, Theoretical Computer Science, v.268 n.2, p.199-219, 17 October 2001
	Moni Naor, Evaluation may be easier than generation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.74-83, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Scott Decatur , Oded Goldreich , Dana Ron, Computational sample complexity, Proceedings of the tenth annual conference on Computational learning theory, p.130-142, July 06-09, 1997, Nashville, Tennessee, United States
	Amos Beimel , Francesco Bergadano , Nader H. Bshouty , Eyal Kushilevitz , Stefano Varricchio, Learning functions represented as multiplicity automata, Journal of the ACM (JACM), v.47 n.3, p.506-530, May 2000
	Shai Ben-David , Nadav Eiron , Philip M. Long, On the difficulty of approximately maximizing agreements, Journal of Computer and System Sciences, v.66 n.3, p.496-514, May 2003
	Moni Naor , Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, Journal of the ACM (JACM), v.51 n.2, p.231-262, March 2004
	Adam R. Klivans , Ryan O'Donnell , Rocco A. Servedio, Learning intersections and thresholds of halfspaces, Journal of Computer and System Sciences, v.68 n.4, p.808-840, June 2004
	Maria Luisa Bonet , Carlos Domingo , Ricard Gavaldà , Alexis Maciel , Toniann Pitassi, Non-automatizability of bounded-depth frege proofs, Computational Complexity, v.13 n.1/2, p.47-68, January 2004
	Haim Kaplan , Eyal Kushilevitz , Yishay Mansour, Learning with attribute costs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Nader H. Bshouty , Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning DNF from random walks, Journal of Computer and System Sciences, v.71 n.3, p.250-265, October 2005
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu, Learning a circuit by injecting values, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada
	Ariel Elbaz , Homin K. Lee , Rocco A. Servedio , Andrew Wan, Separating Models of Learning from Correlated and Uncorrelated Data, The Journal of Machine Learning Research, 8, p.277-290, 5/1/2007
	Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, The complexity of properly learning simple concept classes, Journal of Computer and System Sciences, v.74 n.1, p.16-34, February, 2008
	Dana Angluin , James Aspnes , Jiang Chen , Lev Reyzin, Learning large-alphabet and analog circuits with value injection queries, Machine Learning, v.72 n.1-2, p.113-138, August 2008
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu, Learning a circuit by injecting values, Journal of Computer and System Sciences, v.75 n.1, p.60-77, January, 2009
	Lance Fortnow , Adam R. Klivans, Efficient learning algorithms yield circuit lower bounds, Journal of Computer and System Sciences, v.75 n.1, p.27-36, January, 2009
	Adam R. Klivans , Alexander A. Sherstov, Cryptographic hardness for learning intersections of halfspaces, Journal of Computer and System Sciences, v.75 n.1, p.2-12, January, 2009