В Петербурге

[griffon]

За две недели удалось сделать запланированное:

• Встретиться с друзьями. Спасибо всем, кто пришел на вечеринку в Radiobaby!
  
  
• Сделать доклады про differential privacy в Computer Science клубе и на семинаре в ПОМИ. Надеюсь, было интересно :)
  
  В клубе сейчас Lektorium.TV записывает лекции на видео, что очень круто. Более того, говорят, что там скоро

Comments

[griffon]

Это забавная история. Дело в том, что вот эту статью авторы отправили на STOC 2011, основной результат там $\tilde O(n^{2/3})$- приближенный алгоритм для directed k-spanner. Независимо мы и Константин Макарычев (IBM Research) и Arnab Bhattacharya (MIT) улучшили до $O\tilde O(\sqrt n)$ и сделали препринты с разницей в день :) Видимо, будем объединяться, потому что техника по сути одинаковая.

А откуда ты про их статью узнал, просто архив просматриваешь?

[griffon]

Если интересно, можешь почитать. Там довольно интересное линейное программирование с вероятностным округлением, использующее max-flow/min-cut анализ.

Мне кажется, что у нас несколько понятнее записано, так что наш текст проще смотреть, во всяком случае в ИТМО довольно быстро удалось все технические детали рассказать так, чтобы люди поняли.