BEGIN:VCALENDAR
PRODID:-//SiteBuilder 2//University of ÌÇÐÄTV ITS Web Team//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-TIMEZONE:Europe/London
X-LIC-LOCATION:Europe/London
BEGIN:VTIMEZONE
TZID:Europe/London
LAST-MODIFIED:20201010T011803Z
TZURL:http://tzurl.org/zoneinfo/Europe/London
X-LIC-LOCATION:Europe/London
X-PROLEPTIC-TZNAME:LMT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+000115
TZOFFSETTO:+0000
DTSTART:18471201T000000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19160521T020000
RDATE:19170408T020000
RDATE:19180324T020000
RDATE:19190330T020000
RDATE:19200328T020000
RDATE:19210403T020000
RDATE:19220326T020000
RDATE:19230422T020000
RDATE:19240413T020000
RDATE:19270410T020000
RDATE:19300413T020000
RDATE:19330409T020000
RDATE:19340422T020000
RDATE:19350414T020000
RDATE:19380410T020000
RDATE:19390416T020000
RDATE:19400225T020000
RDATE:19460414T020000
RDATE:19470316T020000
RDATE:19480314T020000
RDATE:19490403T020000
RDATE:19530419T020000
RDATE:19540411T020000
RDATE:19570414T020000
RDATE:19600410T020000
RDATE:19680218T020000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19161001T030000
RDATE:19170917T030000
RDATE:19180930T030000
RDATE:19190929T030000
RDATE:19201025T030000
RDATE:19211003T030000
RDATE:19221008T030000
RDATE:19391119T030000
RDATE:19471102T030000
RDATE:19481031T030000
RDATE:19491030T030000
RDATE:19711031T030000
END:STANDARD
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19230916T030000
RRULE:FREQ=YEARLY;UNTIL=19240921T020000Z;BYMONTH=9;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19250419T020000
RRULE:FREQ=YEARLY;UNTIL=19260418T020000Z;BYMONTH=4;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19251004T030000
RRULE:FREQ=YEARLY;UNTIL=19381002T020000Z;BYMONTH=10;BYMONTHDAY=2,3,4,5,6,
 7,8;BYDAY=SU
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19280422T020000
RRULE:FREQ=YEARLY;UNTIL=19290421T020000Z;BYMONTH=4;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19310419T020000
RRULE:FREQ=YEARLY;UNTIL=19320417T020000Z;BYMONTH=4;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19360419T020000
RRULE:FREQ=YEARLY;UNTIL=19370418T020000Z;BYMONTH=4;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BDST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
DTSTART:19410504T020000
RDATE:19450402T020000
RDATE:19470413T020000
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
DTSTART:19410810T030000
RRULE:FREQ=YEARLY;UNTIL=19430815T010000Z;BYMONTH=8;BYMONTHDAY=9,10,11,12,
 13,14,15;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BDST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
DTSTART:19420405T020000
RRULE:FREQ=YEARLY;UNTIL=19440402T010000Z;BYMONTH=4;BYMONTHDAY=2,3,4,5,6,7
 ,8;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
DTSTART:19440917T030000
RDATE:19450715T030000
RDATE:19470810T030000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19451007T030000
RRULE:FREQ=YEARLY;UNTIL=19461006T020000Z;BYMONTH=10;BYMONTHDAY=2,3,4,5,6,
 7,8;BYDAY=SU
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19500416T020000
RRULE:FREQ=YEARLY;UNTIL=19520420T020000Z;BYMONTH=4;BYMONTHDAY=14,15,16,17
 ,18,19,20;BYDAY=SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19501022T030000
RRULE:FREQ=YEARLY;UNTIL=19521026T020000Z;BYMONTH=10;BYMONTHDAY=21,22,23,2
 4,25,26,27;BYDAY=SU
END:STANDARD
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19531004T030000
RRULE:FREQ=YEARLY;UNTIL=19601002T020000Z;BYMONTH=10;BYMONTHDAY=2,3,4,5,6,
 7,8;BYDAY=SU
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19550417T020000
RRULE:FREQ=YEARLY;UNTIL=19560422T020000Z;BYMONTH=4;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19580420T020000
RRULE:FREQ=YEARLY;UNTIL=19590419T020000Z;BYMONTH=4;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19610326T020000
RRULE:FREQ=YEARLY;UNTIL=19630331T020000Z;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19611029T030000
RRULE:FREQ=YEARLY;UNTIL=19671029T020000Z;BYMONTH=10;BYMONTHDAY=23,24,25,2
 6,27,28,29;BYDAY=SU
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19640322T020000
RRULE:FREQ=YEARLY;UNTIL=19670319T020000Z;BYMONTH=3;BYMONTHDAY=19,20,21,22
 ,23,24,25;BYDAY=SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:BST
TZOFFSETFROM:+0100
TZOFFSETTO:+0100
DTSTART:19681026T230000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19720319T020000
RRULE:FREQ=YEARLY;UNTIL=19800316T020000Z;BYMONTH=3;BYMONTHDAY=16,17,18,19
 ,20,21,22;BYDAY=SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19721029T030000
RRULE:FREQ=YEARLY;UNTIL=19801026T020000Z;BYMONTH=10;BYMONTHDAY=23,24,25,2
 6,27,28,29;BYDAY=SU
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:BST
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
DTSTART:19810329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19811025T020000
RRULE:FREQ=YEARLY;UNTIL=19891029T010000Z;BYMONTH=10;BYMONTHDAY=23,24,25,2
 6,27,28,29;BYDAY=SU
END:STANDARD
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19901028T020000
RRULE:FREQ=YEARLY;UNTIL=19951022T010000Z;BYMONTH=10;BYDAY=4SU
END:STANDARD
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
DTSTART:19960101T000000
END:STANDARD
BEGIN:STANDARD
TZNAME:GMT
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
DTSTART:19961027T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260501T033507Z
DTSTART;VALUE=DATE-TIME:20250124T110000
DTEND;VALUE=DATE-TIME:20250124T120000
SUMMARY:On Optimal Testing of Linearity (Vipul Arora\, National Universit
 y of Singapore)
TZID:Europe/London
UID:20250124-8ac672c69481e10101949219c20238c5@warwick.ac.uk
CREATED:20250123T074000Z
DESCRIPTION:Title: On Optimal Testing of Linearity Abstract: Linearity te
 sting has been a focal problem in property testing of functions. We comb
 ine different known techniques and observations about linearity testing 
 in order to resolve two recent versions of this task. First\, we focus o
 n the online manipulations model introduced by Kalemaj\, Raskhodnikova a
 nd Varma (ITCS 2022 \\& Theory of Computing 2023). In this model\, up to
  $t$ data entries are adversarially manipulated after each query is answ
 ered. Ben-Eliezer\, Kelman\, Meir\, and Raskhodnikova (ITCS 2024) showed
  an asymptotically optimal linearity tester that is resilient to $t$ man
 ipulations per query\, but their approach fails if $t$ is too large. We 
 extend this result\, showing an optimal tester for almost any possible v
 alue of $t$. First\, we simplify their result when $t$ is small\, and fo
 r larger values of $t$ we instead use sample-based testers\, as defined 
 by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A ke
 y observation is that sample-based testing is resilient to online manipu
 lations\, but still achieves optimal query complexity for linearity when
  $t$ is large. We complement our result by showing that when $t$ is very
  large\, any reasonable property\, and in particular linearity\, cannot 
 be tested at all. Second\, we consider linearity over the reals with pro
 ximity parameter $\\varepsilon$. Fleming and Yoshida (ITCS 2020) gave a 
 tester using $O(1/\\varepsilon\\ \\cdot \\log(1/\\varepsilon))$ queries.
  We simplify their algorithms and modify the analysis accordingly\, show
 ing an optimal tester that only uses $O(1/\\varepsilon)$ queries. This m
 odification works for the low-degree testers presented in Arora\, Bhatta
 charyya\, Fleming\, Kelman\, and Yoshida (SODA 2023) as well\, resulting
  in optimal testers for degree-$d$ polynomials\, for any constant degree
  $d$. Joint work with Esty Kelman and Uri Meir.
LOCATION:MB0.01
CATEGORIES:
LAST-MODIFIED:20250123T074000Z
ORGANIZER;CN=Ramanujan Maadapuzhi Sridharan:
END:VEVENT
END:VCALENDAR