{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T05:14:11Z","timestamp":1737695651632,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_39","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"439-451","source":"Crossref","is-referenced-by-count":0,"title":["Separating Populations with Wide Data: A Spectral Analysis"],"prefix":"10.1007","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[]},{"given":"Amin","family":"Coja-Oghlan","sequence":"additional","affiliation":[]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[]},{"given":"Shuheng","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1007\/11503415_31","volume-title":"Learning Theory","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas, D., McSherry, F.: On spectral learning of mixtures of distributions. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS (LNAI), vol.\u00a03559, pp. 458\u2013469. Springer, Heidelberg (2005), http:\/\/www.cs.ucsc.edu\/~optas\/papers\/"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"S.\u00a0Arora and R.\u00a0Kannan. Learning mixtures of arbitrary gaussians. In Proceedings of 33rd ACM Symposium on Theory of Computing, pages 247\u2013257, 2001.","DOI":"10.1145\/380752.380808"},{"key":"39_CR3","unstructured":"Chaudhuri, K., Halperin, E., Rao, S., Zhou, S.: A rigorous analysis of population stratification with limited data. In: Proceedings of the 18th ACM-SIAM SODA (2007)"},{"key":"39_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"A. Coja-Oghlan","year":"2006","unstructured":"Coja-Oghlan, A.: An adaptive spectral heuristic for partitioning random graphs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, Springer, Heidelberg (2006)"},{"key":"39_CR5","unstructured":"Cryan, M.: Learning and approximation Algorithms for Problems motivated by evolutionary trees. PhD thesis, University of Warwick (1999)"},{"issue":"2","key":"39_CR6","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/S0097539798342496","volume":"31","author":"M. Cryan","year":"2002","unstructured":"Cryan, M., Goldberg, L., Goldberg, P.: Evolutionary trees can be learned in polynomial time in the two state general markov model. SIAM J. of Computing\u00a031(2), 375\u2013397 (2002)","journal-title":"SIAM J. of Computing"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Dasgupta, A., Hopcroft, J., Kleinberg, J., Sandler, M.: On learning mixtures of heavy-tailed distributions. In: Proceedings of the 46th IEEE FOCS, pp. 491\u2013500 (2005)","DOI":"10.1109\/SFCS.2005.56"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"Dasgupta, S.: Learning mixtures of gaussians. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pp. 634\u2013644 (1999)","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"39_CR9","unstructured":"Dasgupta, S., Schulman, L.J.: A two-round variant of em for gaussian mixtures. In: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI) (2000)"},{"key":"39_CR10","unstructured":"Feldman, J., O\u2019Donnell, R., Servedio, R.: Learning mixtures of product distributions over discrete domains. In: Proceedings of the 46th IEEE FOCS (2005)"},{"key":"39_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","DOI":"10.1007\/11776420_5","volume-title":"Learning Theory","author":"J. Feldman","year":"2006","unstructured":"Feldman, J., O\u2019Donnell, R., Servedio, R.: PAC learning mixtures of Gaussians with no separation assumption. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol.\u00a04005, Springer, Heidelberg (2006)"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Fiedler, M.: Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 298\u2013305 (1973)","DOI":"10.21136\/CMJ.1973.101168"},{"key":"39_CR13","unstructured":"Fjallstrom, P.: Algorithms for graph partitioning: a survey. Technical report, Linkoping University Electroni Press (1998)"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Freund, Y., Mansour, Y.: Estimating a mixture of two product distributions. In: Proceedings of the 12th Annual COLT, pp. 183\u2013192 (1999)","DOI":"10.1145\/307400.307412"},{"key":"39_CR15","series-title":"Lecture Notes in Artificial Intelligence","volume-title":"Learning Theory","author":"R. Kannan","year":"2005","unstructured":"Kannan, R., Salmasian, H., Vempala, S.: The spectral method for general mixture models. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS (LNAI), vol.\u00a03559, Springer, Heidelberg (2005)"},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapir, R., Sellie, L.: On the learnability of discrete distributions. In: Proceedings of the 26th ACM STOC, pp. 273\u2013282 (1994)","DOI":"10.1145\/195058.195155"},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Latala, R.: Some estimates of norms of random matrices. In: Proceedings of the American Mathematical Society, vol.\u00a0133, pp. 1273\u20131282 (2005)","DOI":"10.1090\/S0002-9939-04-07800-1"},{"key":"39_CR18","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 529\u2013537 (2001)","DOI":"10.1109\/SFCS.2001.959929"},{"issue":"2","key":"39_CR19","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1016\/S0022-1236(03)00198-8","volume":"211","author":"M. Meckes","year":"2004","unstructured":"Meckes, M.: Concentration of norms and eigenvalues of random matrices. J. Funct. Anal.\u00a0211(2), 508\u2013524 (2004)","journal-title":"J. Funct. Anal."},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Mossel, E., Roch, S.: Learning nonsinglar phylogenies and hidden markov models. In: Proceedings of the 37th ACM STOC (2005)","DOI":"10.1145\/1060590.1060645"},{"key":"39_CR21","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1093\/genetics\/155.2.945","volume":"155","author":"J.K. Pritchard","year":"2000","unstructured":"Pritchard, J.K., Stephens, M., Donnelly, P.: Inference of population structure using multilocus genotype data. Genetics\u00a0155, 954\u2013959 (2000)","journal-title":"Genetics"},{"key":"39_CR22","unstructured":"Spielman, D.: The behavior of algorithms in practice, Lecture notes (2002)"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Vempala, V., Wang, G.: A spectral algorithm of learning mixtures of distributions. In: Proceedings of the 43rd IEEE FOCS, pp. 113\u2013123 (2002)","DOI":"10.1109\/SFCS.2002.1181888"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Vu, V.: Spectral norm of random matrices. In: Proceedings of 37th ACM STOC, pp. 423\u2013430 (2005)","DOI":"10.1145\/1060590.1060654"},{"key":"39_CR25","unstructured":"Zhou, S.: Routing, Disjoint Paths, and Classification. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, CMU Technical Report, CMU-PDL-06-109 (2006)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T08:11:25Z","timestamp":1737619885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_39","relation":{},"subject":[]}}