Abstract

 

Understanding 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.

 

https://arxiv.org/pdf/2309.13133

https://arxiv.org/pdf/2205.02319

 

WebEX Link: https://nationaltaiwanuniversity-ksz.my.webex.com/nationaltaiwanuniversity-ksz.my/j.php?MTID=m126a6f5f3c92b47507cc4cef33f68736

Meeting number (access code): 2511 553 6422

Meeting password: cwJKy4u6hA3 

 

Organizers: Jhih-Huang Li (NTU), Wai Kit Lam (NTU)