{"156671":{"#nid":"156671","#data":{"type":"event","title":"Theory Seminar: Stephen Young, University of Louisville, Kentucky","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Braess\u0027s Paradox in Expanders\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EExpander graphs are known to facilitate effective routing and most real-world networks have expansion properties. At the other extreme, it has been shown that in some special graphs, removing certain edges can lead to more efficient routing. This phenomenon is known as Braess\u00b9s paradox and is usually regarded as a rare event. In contrast to what one might expect, we show that Braess\u00b9s paradox is ubiquitous in expander graphs. Specifically, we prove that Braess\u00b9s paradox occurs in a large class of expander graphs with continuous convex latency functions. Our results extend previous work which held only when the graph was both denser and random and for random linear latency functions. We identify deterministic sufficient conditions for a graph with as few as a linear number of edges, such that Braess\u00b9s Paradox almost always occurs, with respect to a general family of random latency functions.\u0026nbsp; (Joint work with Fan Chung and Wenbo Zhao.)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-09-25 09:25:32","changed_gmt":"2016-10-08 02:00:10","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-10-08T14:05:00-04:00","event_time_end":"2012-10-08T14:05:00-04:00","event_time_end_last":"2012-10-08T14:05:00-04:00","gmt_time_start":"2012-10-08 18:05:00","gmt_time_end":"2012-10-08 18:05:00","gmt_time_end_last":"2012-10-08 18:05:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}