BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1580
DTSTAMP:20250731T100935Z
SUMMARY:Quality Control on Random Graphs in Sublinear Time
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Poulson School of Enginee
 ring and Applied Sciences)\n\nAbstract: \nMany algorithms have lately been
  designed to work well on average (i.e.\, on inputs coming from some distr
 ibution D)\, but then when running this algorithm on a specific input x\, 
 we are forced to ask the question — can we really trust the algorithm on
  this input?\nIn this work we define a class of problems — that we call 
 quality control problems\, whose definition allows the algorithm to exploi
 t the randomness of instances\, while still being safe to use on a specifi
 c input. A quality control problem is given by a pair (rho\,D) where rho i
 s a real valued quality parameter and D a distribution on inputs. We assum
 e that inputs from D are "high quality" (i.e.\, have rho(x) close to 1) wi
 th high probability. An algorithm A is said to solve the problem if it sat
 isfies (1) Completeness - it accepts inputs from D w.h.p. and (2) Soundnes
 s - if rho(x) is far from 1\, it rejects (w.h.p. over internal randomness)
 . [This definition is inspired by Feige's work on refutation of random CSP
 s and also by Rubinfeld and Vasilian's work on testable learning.] So the 
 algorithm does not accept every high quality input\, but does accept most 
 of them\; while rejecting every poor quality input w.h.p.\nQuality control
  problems get technically interesting when the condition "rho(x) ~= 1" is 
 not easily certifiable. We consider a natural class of such problems - nam
 ely counting constant sized subgraphs in an Erdos-Renyi random graph (G(n\
 ,p)) where edges appear independently with probability p. Among our result
 s we give quality control algorithms that make (1/p)^O(k) queries to the a
 djacency matrix of a graph G to confirm that the number of k-cliques is ro
 ughly the expected number in G(n\,p). In contrast it is known that a subli
 near algorithm solving this problem on worst case inputs would require (1/
 p)^Theta(k^2) queries. \nOur proofs highlight the nice composability feat
 ures of quality control problems while also invoking tools from probabilit
 y theory and quasirandomness of graphs that may be of general interest.\nJ
 oint work with Cassandra Marcussen (Harvard) and Ronitt Rubinfeld (MIT).\n
 Short Bio: Madhu Sudan is Gordon McKay Professor at Harvard's John A. Paul
 son School of Engineering and Applied Sciences. He got his B.Tech. from II
 T Delhi and Ph.D. from UC Berkeley and  previously held positions at IBM 
 Research\, MIT\, and Microsoft Research. His research focuses on the mathe
 matical foundations of communication and computation in general\, and in p
 articular on questions about probabilistically checkable proofs\, list dec
 oding of error correcting codes\, property testing\, sublinear time algori
 thms and communication in the presence of uncertainty. \n
URL:https://www.tcs.tifr.res.in/web/events/1580
DTSTART;TZID=Asia/Kolkata:20250805T160000
DTEND;TZID=Asia/Kolkata:20250805T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR