BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/155
DTSTAMP:20230914T125912Z
SUMMARY:A Unified Framework for Testing Linear-Invariant Properties
DESCRIPTION:Speaker: Arnab Bhattacharya\nMassachusetts Institute of Technol
 ogy\n32 Vassar St.\, Room G696\nCambridge\, MA 02139\nUnited\n\nAbstract: 
 \nIn a sequence of recent papers\, Sudan and coauthors have investigated t
 he relation between testability of properties of Boolean functions and the
  invariance of the properties with respect to transformations of the domai
 n. Linear-invariance is arguably the most common such symmetry for natural
  properties of Boolean functions on the hypercube. Hence\, it is an import
 ant goal to find necessary and sufficient conditions for testability of li
 near-invariant properties. This is explicitly posed as an open problem in 
 a recent survey of Sudan. We obtain the following results:\n\n1. We show t
 hat every linear-invariant property that can be characterized by forbiddin
 g induced solutions to a (possibly infinite) set of linear equations can b
 e tested with one-sided error.\n\n2. We show that every linear-invariant p
 roperty that can be tested with one-sided error can be characterized by fo
 rbidding induced solutions to a (possibly infinite) set of systems of line
 ar equations.\n\nWe conjecture that our result from item (1) can be extend
 ed to cover systems of linear equations. We further show that the validity
  of this conjecture would have the following implications:\n\n1. It would 
 imply that every linear-invariant property that is closed under restrictio
 ns to linear subspaces is testable with one-sided error. Such a result wou
 ld unify several previous results on testing Boolean functions\, such as t
 he results on testing low-degree\npolynomials and results on testing Fouri
 er dimensionality.\n\n2. It would imply that a linear-invariant property P
  is testable with one-sided error *if and only if* P is closed under restr
 ictions to linear subspaces\, thus resolving Sudan's problem (joint work w
 ith Elena Grigorescu and Asaf Shapira).\n
URL:https://www.tcs.tifr.res.in/web/events/155
DTSTART;VALUE=DATE:20110131
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR