BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//prob.tw//NTU Seminars V2//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
UID:2024-05-31-dylan-altschuler-zero-one-laws-for-random-feasibility-problems@seminars.prob.tw
DTSTAMP:20261014T103502Z
DTSTART:20240531T020000Z
DTEND:20240531T030000Z
SUMMARY:Zero-one Laws for Random Feasibility Problems
DESCRIPTION:Dylan Altschuler\nUnderstanding when a high-dimensional polytope contains integer points is a fundamental problem in a wide variety of fields including combinatorial optimization\, computer science\, Banach geometry\, statistical physics\, and information theory.  We introduce a general random model of this problem that encodes: the closest vector problem\, linear feasibility\, integer linear feasibility\, perceptron problems\, and combinatorial discrepancy in any norm. We study the \\"margin\\"\, the distance between a polytope and the nearest integer points. The margin acts as a quantitative measure for the \\"distance to feasibility\\" for random optimization problems. Our main result is a set of sufficient conditions for the margin to concentrate. Concentration of the margin implies a host of new sharp threshold results in the mentioned models\, and also simplifies and extends some key known results.\n\nReferences:\n[1] <a href=\\"https://arxiv.org/abs/2309.13133\\" target=\\"_blank\\">https://arxiv.org/abs/2309.13133</a>\n[2] <a href=\\"https://arxiv.org/abs/2205.02319\\" target=\\"_blank\\">https://arxiv.org/abs/2205.02319</a>
LOCATION:台大數學系天文數學館 440 室
URL:http://127.0.0.1:8123/?event=2024-05-31-dylan-altschuler-zero-one-laws-for-random-feasibility-problems
END:VEVENT
END:VCALENDAR