{"73013":{"#nid":"73013","#data":{"type":"event","title":"ARC Colloquium: Krzysztof Onak, Massachusetts Institute of Technology","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMy talk will focus on sublinear-time algorithms, which are my main research interest. As an example, I will address the following question. \u003C\/p\u003E\u003Cp\u003ECan computing the size of a solution to a combinatorial graph problem be faster than finding the solution itself? I will answer the question in the affirmative for multiple problems. For instance, I will present the first approximation algorithm that for the class of graphs with average degree bounded by d, computes the maximum matching size to within an additive epsilon*n in time that only depends on d and epsilon, and does not depend directly on n, where n is the number of vertices. \u003C\/p\u003E\u003Cp\u003EThe vertex cover size and the minimum dominating set size cannot be approximated this well in time that does not depend on the number of vertices. Nevertheless, I will show that this is possible for a certain important class of graphs, namely the hyperfinite class of graphs, which include planar graphs and graphs of subexponential growth. Our techniques imply a simple proof of the result of Benjamini, Schramm, and Shapira (STOC 2008) that every minor-closed property of constant-degree graphs can be tested in constant time, and also yield constant-time algorithms for approximating the distance to hereditary properties in hyperfinite graphs. Finally, I will briefly talk about a few other problems in the sublinear-time computation model. I will use them to advertise the sublinear-time computation model as a useful tool for solving classical problems and understanding their hardness, as well as a great source of inspiration for other computation models.\u003C\/p\u003E\u003Cp\u003EJoint work with multiple authors whose names will be mentioned in the talk.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Sublinear Graph Approximation Algorithms"}],"uid":"27263","created_gmt":"2011-11-23 12:55:48","changed_gmt":"2016-10-08 01:56:41","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2010-02-03T12:30:00-05:00","event_time_end":"2010-02-03T12:30:00-05:00","event_time_end_last":"2010-02-03T12:30:00-05:00","gmt_time_start":"2010-02-03 17:30:00","gmt_time_end":"2010-02-03 17:30:00","gmt_time_end_last":"2010-02-03 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}