Open Research Index

Satisfiability and freezing in random integer programs

Dylan J. Altschuler, Ruben Ascoli, Will Perkins

arXivarxiv/2610.14085Oct 8, 2026math.PRscore 0

We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the location of a sharp threshold for the existence of these integer points, a characterization of the typical empirical distribution of their coordinates, and showing that near the feasibility threshold these integer points are almost always totally isolated --- at linear Hamming distance to the nearest other integer point in the polytope. The behavior of these random integer programs is related to that of the symmetric…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.14085
curl -X POST /api/v1/records/arxiv/2610.14085/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.14085/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'