{"560081":{"#nid":"560081","#data":{"type":"event","title":"ARC Colloquium: David Zuckerman (UT Austin)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/56062\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/56062\u003C\/a\u003E\u003C\/p\u003E\r\nFull collection of talk videos are available at:  \r\n\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\r\n\r\n\u003Cbr\u003E\r\n\u003Cbr\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Ca href=\u0022https:\/\/www.cs.utexas.edu\/~diz\/\u0022\u003E\u003Cstrong\u003EDavid Zuckerman \u0026ndash; UT Austin\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 14, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003EExplicit Two-Source Extractors and Resilient Functions\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u0026nbsp;\u003Cbr \/\u003E\r\nWe explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.\u003Cbr \/\u003E\r\nA key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta\u0026gt;0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1\/2 - \\delta}.\u003Cbr \/\u003E\r\nOur explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.\u003Cbr \/\u003E\r\nJoint work with Eshan Chattopadhyay.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u0026nbsp;\u0026nbsp;\u003C\/strong\u003E\u003Cbr \/\u003E\r\nDavid Zuckerman holds an Endowed Professorship in the Computer Science Department at the \u003Ca href=\u0022http:\/\/www.cs.utexas.edu\u0022\u003EUniversity of Texas at Austin\u003C\/a\u003E. He received an A.B. in Mathematics from Harvard University in 1987 and a Ph.D. in Computer Science from U.C. Berkeley in 1991. He was a postdoctoral fellow at MIT from 1991-1993, and at Hebrew University in the Fall of 1993. He has been with the University of Texas since then, visiting U.C. Berkeley from 1999-2000, Harvard University from 2004-2005, and the Institute for Advanced Study from 2011-12.\u003Cbr \/\u003E\r\nHis research focuses primarily on pseudorandomness and the role of randomness in computing. He is best known for his work on randomness extractors and their applications. His other research interests include coding theory, distributed computing, cryptography, inapproximability, and other areas of complexity theory. His research awards include a \u003Ca href=\u0022https:\/\/www.simonsfoundation.org\/mathematics-and-physical-science\/simons-investigators\/simons-investigators-awardees\/\u0022\u003ESimons Investigator Award\u003C\/a\u003E, a Best Paper Award at STOC 2016, ACM Fellow, a Guggenheim Fellowship, a Packard Fellowship for Science and Engineering, a Sloan Research Fellowship, and an NSF Young Investigator Award.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/www.cs.utexas.edu\/~diz\/\u0022\u003Ehttp:\/\/www.cs.utexas.edu\/~diz\/\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Explicit Two-Source Extractors and Resilient Functions (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-08 10:35:24","changed_gmt":"2017-04-13 21:15:12","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-11-14T11:00:00-05:00","event_time_end":"2016-11-14T12:00:00-05:00","event_time_end_last":"2016-11-14T12:00:00-05:00","gmt_time_start":"2016-11-14 16:00:00","gmt_time_end":"2016-11-14 17:00:00","gmt_time_end_last":"2016-11-14 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003C\/p\u003E\r\n\r\n\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}