{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:22Z","timestamp":1742600422259,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_31","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:13Z","timestamp":1330290253000},"page":"375-386","source":"Crossref","is-referenced-by-count":0,"title":["The action of a few random permutations on r-tuples and an application to cryptography"],"prefix":"10.1007","author":[{"given":"Joel","family":"Friedman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Roichman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacques","family":"Stern","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean -Pierre","family":"Tillich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f2s, E. Szemer\u00e9di, \u201cSorting in c log n parallel steps\u201d, Combinatorica 3 (1983), 1\u201319.","journal-title":"Combinatorica"},{"key":"31_CR2","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1978","unstructured":"D. Angluin. \u201cOn the complexity of minimum inference of regular sets\u201d, Information and Control 39 (1978), 302\u2013320.","journal-title":"Information and Control"},{"issue":"3","key":"31_CR3","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D. Angluin","year":"1983","unstructured":"D. Angluin and C.H. Smith. \u201cInductive inference, theory and methods\u201d, Computing Surveys 15(3) (1983), 237\u2013269.","journal-title":"Computing Surveys"},{"key":"31_CR4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N. Alon","year":"1985","unstructured":"N. Alon and V.D. Milman. \u201cgl1, isoperimetric inequalities for graphs and superconcentrators\u201d, J. Comb. Theory, Ser. B, 38, (1985), 73\u201388.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"L. Babai. \u201cTransparent proofs and limits to approximation\u201d, preprint, (1994).","DOI":"10.1007\/978-3-0348-9110-3_2"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"L. Babai, G. Hetyei, W.M. Kantor, A. Lubotzky, A. Seres. \u201cOn the diameter of finite groups\u201d, 31st annual Symposium on Foundations of Computer Science, (1990), 857\u2013865.","DOI":"10.1109\/FSCS.1990.89608"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, S. Goldwasser. \u201cRandomness in interactive proofs\u201d, 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, (1990), 563\u2013572.","DOI":"10.1109\/FSCS.1990.89577"},{"key":"31_CR8","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas. Random Graphs, Academic Press, London (1985)."},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0195-6698(88)80014-3","volume":"9","author":"B. Bollobas","year":"1988","unstructured":"B. Bollobas. \u201cThe isoperimetric number of random regular graphs\u201d, Europ. J. Combinatorics 9 (1988), 241\u2013244.","journal-title":"Europ. J. Combinatorics"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02579310","volume":"2","author":"B. Bollobas","year":"1982","unstructured":"B. Bollobas and W. F. de la Vega. \u201cThe diameter of random-regular graphs\u201d, Combinatorica, 2, (1982), 125\u2013134.","journal-title":"Combinatorica"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"A. Broder, E. Shamir. \u201cOn the second eigenvalue of random regular graphs\u201d, 28th annual Symposium on Foundations of Computer Science, (1987), 286\u2013284.","DOI":"10.1109\/SFCS.1987.45"},{"key":"31_CR12","unstructured":"C. Delorme. \u201cCounting closed paths in trees\u201d, Technical Report n.516, University of Paris-Sud, Laboratoire de recherche en informatique Orsay, September 1989 (in French)."},{"key":"31_CR13","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1214\/aoap\/1177005981","volume":"1","author":"J. Fill","year":"1991","unstructured":"J. Fill. \u201cEigenvalue bounds on convergence to stationarity for nonreversible Markov chains with an application to the exclusion processes\u201d Ann. Appl. Prob. 1, (1991), 62\u201387.","journal-title":"Ann. Appl. Prob."},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Y. Freund, M. Kearns, D. Ron, R. Rubinfeld, R.E. Schapire and L. Sellie. \u201cEfficient learning of typical finite automata from random walks\u201d, 25th ACM Symposium on the Theory of Computing (1993), 315\u2013324.","DOI":"10.1145\/167088.167191"},{"key":"31_CR15","unstructured":"J. Friedman,A. Joux,Y. Roichman,J. Stern,J.P. Tillich. \u201cThe action of a few permutations on r-tuples is quickly transitive\u201d, submitted."},{"issue":"4","key":"31_CR16","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01275669","volume":"11","author":"J. Friedman","year":"1991","unstructured":"J. Friedman. \u201cOn the second eigenvalue and random walks in random d-regular graphs\u201d, Combinatorica 11 (4) (1991), 331\u2013362.","journal-title":"Combinatorica"},{"key":"31_CR17","doi-asserted-by":"crossref","unstructured":"J. Friedman, J. Kahn, E. Szemeredi. \u201cOn the second eigenvalue in random regular graphs\u201d, 21st annual Symposium on Theory of Computing, ACM press, (1989), 587\u2013598.","DOI":"10.1145\/73007.73063"},{"key":"31_CR18","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"E.M. Gold. \u201cComplexity of automaton identification from given data\u201d, Information and Control 37 (1978), 302\u2013320.","journal-title":"Information and Control"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesen, D. Zuckerman. \u201cSecurity preserving amplification of randomness\u201d, 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, (1990), 318\u2013326.","DOI":"10.1109\/FSCS.1990.89550"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, D. Zuckerman. \u201cHow to recycle random bits\u201d, 30th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, (1989), 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"31_CR21","unstructured":"A. Joux, J. Stern, J.P. Tillich. \u201cInferring finite automata by queries of fixed length\u201d, Preprint."},{"key":"31_CR22","doi-asserted-by":"crossref","unstructured":"N. Kahale. \u201cBetter expansions for Ramanujan graphs\u201d, 32nd Annual Symposium on Foundations of Computer Science (1991), 398\u2013404.","DOI":"10.1109\/SFCS.1991.185397"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"N. Kahale. \u201cOn the second eigenvalue and linear expansion of regular graphs\u201d, 33rd Annual Symposium on Foundations of Computer Science (1992), 296\u2013303.","DOI":"10.1109\/SFCS.1992.267762"},{"key":"31_CR24","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/10586458.1992.10504252","volume":"1","author":"J. Lafferty","year":"1992","unstructured":"J. Lafferty, D. Rockmore. \u201cFast Fourier analysis for SL 2 over a finite field, and related numerical experiments\u201d, Experimental Mathematics 1, (1992), 115\u2013139.","journal-title":"Experimental Mathematics"},{"key":"31_CR25","doi-asserted-by":"crossref","unstructured":"A. Lubotzky. Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, Vol. 125, Birkh\u00e4user 1994.","DOI":"10.1007\/978-3-0346-0332-4_10"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"A. Lubotzky. \u201cCayley graphs: eigenvalues, expanders and random walks\u201d, to appear in Survey in Combinatorics, 1995.","DOI":"10.1017\/CBO9780511662096.008"},{"key":"31_CR27","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0024-3795(81)90150-6","volume":"40","author":"B. McKay","year":"1981","unstructured":"B. McKay. \u201cThe expected eigenvalue distribution of a large regular graph\u201d, Linear Algebra and its Applications, 40, (1981), 203\u2013216.","journal-title":"Linear Algebra and its Applications"},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"M. Mihail. \u201cConductance and convergence of Markov chains\u2014a combinatorial treatment of expanders\u201d, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989.","DOI":"10.1109\/SFCS.1989.63529"},{"key":"31_CR29","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0095-8956(89)90029-4","volume":"B","author":"B. Mohar","year":"1989","unstructured":"B. Mohar. \u201cIsoperimetric number of graphs\u201d, Journal of Comb. Theory (B) (1989), 274\u2013291.","journal-title":"Journal of Comb. Theory"},{"key":"31_CR30","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0206022","volume":"6","author":"N. Pippenger","year":"1977","unstructured":"N. Pippenger. \u201cSuperconcentrators\u201d, SIAM J. Comput., 6, (1977), 298\u2013304.","journal-title":"SIAM J. Comput."},{"key":"31_CR31","doi-asserted-by":"crossref","unstructured":"R.L. Rivest and R.E. Schapire. \u201cDiversity based inference of finite automata\u201d Proceedings of the 28th Annual Symposium on the Foundations of Computer Science (1987), 78\u201387.","DOI":"10.1109\/SFCS.1987.21"},{"key":"31_CR32","doi-asserted-by":"crossref","unstructured":"R.L. Rivest and R.E. Schapire. \u201cInference of finite automata using homing sequences\u201d Proceedings of the 21st ACM Symposium on the Theory of Computing (1989), 411\u2013420.","DOI":"10.1145\/73007.73047"},{"key":"31_CR33","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0605030","volume":"5","author":"R.M. Tanner","year":"1984","unstructured":"R.M. Tanner. \u201cExplicit constructions of concentrators from generalized N-gons\u201d, SIAM J. Alg. Disc. Meth., 5, (1984), 287\u2013293.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"31_CR34","doi-asserted-by":"crossref","unstructured":"J.P. Tillich, G. Z\u00e9mor. \u201cGroup-theoretic hash functions\u201d, Proceedings of the 1st French-Israeli Workshop in algebraic coding 1993, Springer Verlag, Lecture Notes 781, 90\u2013110.","DOI":"10.1007\/3-540-57843-9_12"},{"key":"31_CR35","doi-asserted-by":"crossref","unstructured":"J.P. Tillich, G. Z\u00e9mor. \u201cHashing with SL2\u201d, Advances in Cryptology, Proceedings of CRYPTO94, Springer Verlag, Lecture Notes 839, 40\u201349.","DOI":"10.1007\/3-540-48658-5_5"},{"key":"31_CR36","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1090\/psapm\/044\/1141925","volume":"44","author":"U. Vazirani","year":"1991","unstructured":"U. Vazirani. \u201cRapidly mixing markov chains\u201d, Proceedings of Symposia in Applied Mathematics, Volume 44, (1991), 99\u2013121.","journal-title":"Proceedings of Symposia in Applied Mathematics"},{"key":"31_CR37","doi-asserted-by":"crossref","unstructured":"G. Z\u00e9mor. \u201cHash Functions and Cayley graphs\u201d, to appear in Design, Codes and Cryptography, of October 1994.","DOI":"10.1007\/BF01388652"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:38Z","timestamp":1742598638000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}