BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20261025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260918T084723Z
UID:6aa7cc7f86cf5144155787@ist.ac.at
DTSTART:20260924T140000
DTEND:20260924T150000
DESCRIPTION:Speaker: Pavel Arkhipov\nAbstract: Continual counting under pur
 e differential privacy is one of the simplest and most well-studied proble
 ms in the continual observation model. Given a binary stream $x_1\, \\ldot
 s\, x_n \\in \\{0\,1\\}$\, the goal is to release\, at each time $t$\, an 
 approximation to the prefix sum $\\sum_{i=1}^t x_i$. The entire output seq
 uence must satisfy $\\epsilon$-differential privacy\, while making the acc
 uracy as good as possible. We consider the maximum expected squared error 
 over all times $t$ as our accuracy score. Very recently\, it was shown tha
 t the correct asymptotics for this error is $\\Theta(\\epsilon^{-2} \\log^
 3 n)$ for factorization-based mechanisms.We give a construction using a ge
 neral matrix factorization mechanism\, improving the leading constant for 
 the mean squared error. The mechanism starts from a good-quality low-dimen
 sional factorization and lifts this factorization to arbitrarily large dim
 ensions.On the lower-bound side\, we show a very simple $\\Omega(\\epsilon
 ^{-2}\\log^3 n)$ lower bound for the special case of factorizations whose 
 matrices have entries in {0\, 1}.This talk covers a subset of our paper wi
 th Nikita Kalinin (https://arxiv.org/abs/2607.08963)
LOCATION:Mondi Seminar Room 3\, Central Building\, ISTA
ORGANIZER:joanders@ist.ac.at
SUMMARY:Pavel Arkhipov: TCS Seminar - Differentially Private Continual Coun
 ting via Matrix Factorization: Constructions and Lower Bounds
URL:https://talks-calendar.ista.ac.at/events/6619
END:VEVENT
END:VCALENDAR