{"486491":{"#nid":"486491","#data":{"type":"event","title":"ARC Colloquium: William Gasarch - University of Maryland at College Park","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EWilliam Gasarch \u2013 University of Maryland\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, February 17, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EAdvanced Results in the Theory of Languages and Computation which have Simple Proofs\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003Cbr \/\u003E\u003C\/strong\u003EAutomata theory is about the following: Given a language (a set of strings) how hard is it? Is it regular, context free, or decidable? We give three results that COULD be put in a course on such but are not!\u003C\/p\u003E\u003Col\u003E\u003Cli\u003ERegular, Context free, and Decidable languages are closed under many operations. Note the following: if L is regular (CFL) then SUBSEQ(L) is regular (CFL).\u0026nbsp; This is an easy exercise. But what if L is decidable? Is SUBSEQ(L) decidable? The answer may surprise you!\u003C\/li\u003E\u003Cli\u003EThere are languages L that are regular but the DFA for them is much smaller than the CFG for them. How much smaller? The answer may surprise you!\u003C\/li\u003E\u003Cli\u003EIt is easy to show that COL3 \\le COL4 (three-colorability \\le 4-colorablity). Is COL4 \\le COL3? You probably know that it is by going through the Cook-Levin Theorem. Is there an easier proof? The answer would surprise you if I didn\u0027t ask the question so I\u0027ll just say YES- I will show COL4 \\le COL3 with a simple proof.\u003C\/li\u003E\u003C\/ol\u003E\u003Cp\u003EThe answers may surprise you!\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 East at 1 pm"}],"uid":"27466","created_gmt":"2016-01-14 15:29:00","changed_gmt":"2017-04-13 21:17:07","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-17T12:00:00-05:00","event_time_end":"2016-02-17T13:00:00-05:00","event_time_end_last":"2016-02-17T13:00:00-05:00","gmt_time_start":"2016-02-17 17:00:00","gmt_time_end":"2016-02-17 18:00:00","gmt_time_end_last":"2016-02-17 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"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":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}