Date:
Mon, 29/04/201911:00-13:00
Location:
CS B-500, Safra campus
Speaker: Karthik C. Srikanta (Weizmann Institute)
Title: On Closest Pair Problem and Contact Dimension of a Graph
Abstract: Given a set of points in a metric space, the Closest Pair problem asks to find a pair of distinct points in the set with the smallest distance. In this talk, we address the fine-grained complexity of this problem which has been of recent interest. At the heart of all our proofs is the construction of a family of dense bipartite graphs with special embedding properties and are inspired by the construction of locally dense codes.
The talk is based on a joint work with Pasin Manurangsi and a preprint is available at http://eccc.weizmann.ac.il/report/2018/210.
Title: On Closest Pair Problem and Contact Dimension of a Graph
Abstract: Given a set of points in a metric space, the Closest Pair problem asks to find a pair of distinct points in the set with the smallest distance. In this talk, we address the fine-grained complexity of this problem which has been of recent interest. At the heart of all our proofs is the construction of a family of dense bipartite graphs with special embedding properties and are inspired by the construction of locally dense codes.
The talk is based on a joint work with Pasin Manurangsi and a preprint is available at http://eccc.weizmann.ac.il/report/2018/210.