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