[DMO] Bram Bekker: Semidefinite programming bounds for distance-avoiding set problems on the sphere

27 June 2023 11:00 till 12:00 - Location: LB 01.040 Meeting room 1.1 | Add to my calendar

Witsenhausen’s problem asks for the set with largest area on the n-dimensional unit sphere such that no two points in this set are orthogonal. Distance-avoiding set problems are a broader class of of problems, where we want to find maximal subsets of the unit sphere that avoid a given set of inner products. By exposing these problems as maximal independent set problems on an infinite graph, we can use semidefinite programming to obtain upper bounds. We developed hierarchies of strengthenings of the Lovász theta-number to obtain the best upper bounds known. A result of theoretical significance is the proof that these hierarchies all converge to exactly the independence number of the graph.