BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/373
DTSTAMP:20230914T125922Z
SUMMARY:Lower Bound Techniques in Property Testing
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nAs with other area
 s of computer science\, lower bounds play an essential role in the field o
 f property testing. The question can be posed as follows. Given a black-bo
 x access to an arbitrary function which is to be tested against a property
 \, how many queries are necessary to be made to the function so that with 
 high probability the function can be distinguished between having the prop
 erty and $\\epsilon$-away from all the functions having the property.\nThe
  tester can be both adaptive and non-adaptive. The most efficient and gene
 ric tool for proving lower bounds for property testing was given by Yao. W
 e will look at the statement and proof of these tools and their applicatio
 n in proving lower bounds of the query complexity of testing\n$k$-linearit
 y and monotonicity.\nReferences:\n[BK12]  Eric Blais and Daniel M. Kane. 
 Tight bounds for testing k-linearity. In Anupam Gupta\, Klaus Jansen\, Jos
 ´e D. P. Rolim\, and Rocco A. Servedio\, editors\, APPROX-RANDOM\, volume
  7408 of Lecture Notes in Computer Science\, pages 435–446. Springer\, 2
 012.\n[FLN+02] Eldar Fischer\, Eric Lehman\, Ilan Newman\, Sofya Raskhodni
 kova\, Ronitt Rubinfeld\, and Alex Samorodnitsky. Monotonicity testing ove
 r general poset domains. In John H. Reif\, editor\, STOC\, pages 474–483
 . ACM\, 2002.\n[Yao77] Andrew Chi-Chih Yao. Probabilistic computations: To
 ward a unified measure of complexity (extended abstract). In FOCS\, pages 
 222–227. IEEE Computer Society\, 1977.\n
URL:https://www.tcs.tifr.res.in/web/events/373
DTSTART;TZID=Asia/Kolkata:20130607T143000
DTEND;TZID=Asia/Kolkata:20130607T160000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR