{"71294":{"#nid":"71294","#data":{"type":"event","title":"ARC Colloquium: David Pritchard, NSERC","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EThis is a talk in two parts, linked by probabilistic methods and linear algebra. In the first half, we look at the problem of finding all 2-edge cuts in a graph. For this we give a simple algorithm based on uniformly sampling the graph\u0027s cycle space (all Eulerian subgraphs). Its distributed implementation is time-optimal on every graph. In the second half, we talk about partitioning set systems into set covers. Mainly, as a function of the minimum degree and maximum set size, how many disjoint covers can be obtained? The tools used to answer this include discrepancy theory and iterated linear programming.\u003C\/p\u003E\u003Cp\u003EThis is joint work with R. Thurimella; and with B. Bollobas, T. Rothvoss, \u0026amp; A. Scott.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EThis is a talk in two parts, linked by probabilistic methods and linear algebra.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Randomized Algorithms for Cuts and Colourings"}],"uid":"27263","created_gmt":"2011-10-14 15:07:38","changed_gmt":"2016-10-08 01:56:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-10-31T14:30:00-04:00","event_time_end":"2011-10-31T14:30:00-04:00","event_time_end_last":"2011-10-31T14:30:00-04:00","gmt_time_start":"2011-10-31 18:30:00","gmt_time_end":"2011-10-31 18:30:00","gmt_time_end_last":"2011-10-31 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"14737","name":"\u0026 A. Scott."},{"id":"14734","name":"graph\u0027s cycle space"},{"id":"14733","name":"linear algebra"},{"id":"14735","name":"R. Thurimella; and with B. Bollobas"},{"id":"14736","name":"T. Rothvoss"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali\u003Cbr \/\u003EDirector, Algorithms Research Center\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}