Пятница 25.09. Alexander Golovnev (Georgetown University, USA): "Polynomial Data Structure Lower Bounds in the Group Model"
PDMI seminars
Тема: Polynomial Data Structure Lower Bounds in the Group Model
Место: Zoom
Время: 25.09.2020, 18:00
Докладчик: Alexander Golovnev (Georgetown University, USA)
Abstract:
Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing---in particular, on the existence and partial derandomization of optimal \emph{binary} compressed sensing matrices in the polynomial sparsity regime ($k = n^{1-\delta}$). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.
Alexander V. Smal
Ссылка для семинара:
https://us02web.zoom.us/j/8141238054?pwd=Q2RMak9XU2dQSFlZcm5xV3VzZzdPZz09
Саша
> Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/000000000000c73c4405afc791c9%40google.com.
--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia