דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: On Complexity of Closest Pair Problem
event speaker icon
Karthik C.S (מכון ויצמן למדע)
event date icon
יום רביעי, 16.1.2019, 12:30
event location icon
טאוב 201
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 dense bipartite graph 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.
[בחזרה לאינדקס האירועים]