BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6a215e425c90a
DTSTART;TZID=America/Toronto:20260330T123000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260330T133000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/co-reading-g
 roup-jacob-skitsko-simple-proof-hardness-matrix
SUMMARY:C&O Reading Group - Jacob Skitsko-A Simple Proof of Hardness of Mat
 rix\nCompletion
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n\n Jacob Skitsko\n\nAFFILIATION:\n University of Wate
 rloo\n\nLOCATION:\n MC 6029\n\nABSTRACT:\n\nIn the matrix completion probl
 em\, we are given an incomplete matrix A\nas input. Some entries are fille
 d in\, and some entries have the value\n\"*\". Our task is to fill in the 
 \"*\" entries so that the resulting\ncompleted matrix has minimum rank. We
 'll discuss a simple proof from\nShitov showing that it is hard to disting
 uish between an incomplete\nmatrix having a rank 3 completion\, or all com
 pletions requiring at\nleast rank 4. \nThe idea is to index the matrix by 
 vectors. These vectors will\nrepresent a circuit computing a family of pol
 ynomials\, f(x) in F. The\nhope is that any rank 3 completion will be forc
 ed to fill in the\nmatrix values according to these vector labels. Thus\, 
 the completion\nwill specify values for x_i\, x_j\, x_i + x_j\, x_i * x_j\
 , ... \, and so\non until it specifies values for our polynomials f(x). If
  we force the\nf(x) in F entries to be 0\, then this is exactly a solution
  to the\npolynomial system F. Seeing why any rank 3 completion should be f
 orced\nto operate in this way takes a bit of squinting\, but is overall qu
 ite\npleasant.
DTSTAMP:20260604T111514Z
END:VEVENT
END:VCALENDAR