BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/848
DTSTAMP:20230914T125940Z
SUMMARY:Estimating the Capacity of the 2-D Hard Square Constraint Using Gen
 eralized Belief Propagation
DESCRIPTION:Speaker: Navin Kashyap (Indian Institute of Science\nDepartment
  of Electrical and\nCommunication Engineering\nBangalore 560012)\n\nAbstra
 ct: \nA binary m x n array is said to satisfy the two-dimensional (2-D) ha
 rd square constraint if no row or column of the array contains ones in con
 secutive positions. Let N(m\,n) denote the number of such arrays. The capa
 city of the hard square constraint is the limit\, as m\, n go to infinity\
 , of the quantity (1/mn)*(log N(m\,n)). Determining this capacity exactly 
 is a long-standing open problem\; its numerical value is known up to ten d
 ecimal places. Recently\, Sabato and Molkaraie demonstrated via simulation
 s that the capacity of the hard square constraint can be approximated extr
 emely well using the generalized belief propagation (GBP) algorithm. They 
 did not\, however\, give an analytical explanation for their observations.
  In this talk\, we outline an approach for analyzing GBP with a view to gi
 ving guarantees on the accuracy of the GBP estimate of the capacity of the
  hard square constraint. More generally\, our approach provides a means of
  analyzing the performance of GBP in estimating the partition function of 
 any binary pairwise model on 2-D grids. Our main result at this point is t
 hat the GBP estimate is always a lower bound on the true partition functio
 n of any such model on a 2-D grid of size 3xn\, 4x4\, or 5x5 (this is join
 t work with Eric Chan\, Sidharth Jaggi and Pascal Vontobel at the Chinese 
 University of Hong Kong).\n
URL:https://www.tcs.tifr.res.in/web/events/848
DTSTART;TZID=Asia/Kolkata:20180118T113000
DTEND;TZID=Asia/Kolkata:20180118T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR