The Library
Geometric decision procedures and the VC dimension of linear arithmetic theories
Tools
Chistikov, Dmitry, Haase, Christoph and Mansutti, Alessio (2022) Geometric decision procedures and the VC dimension of linear arithmetic theories. In: 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), Haifa, Israel, 02–05 Aug 2022. Published in: LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science pp. 1-13. ISBN 9781450393515. doi:10.1145/3531130.3533372
|
PDF
WRAP-Geometric-decision-procedures-VC-dimension-2022.pdf - Accepted Version - Requires a PDF viewer. Download (1119Kb) | Preview |
|
PDF
copyright-12670_111_1.pdf - Permissions Correspondence Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (26Kb) |
Official URL: https://doi.org/10.1145/3531130.3533372
Abstract
This paper resolves two open problems on linear integer arithmetic (LIA), also known as Presburger arithmetic. First, we give a triply exponential geometric decision procedure for LIA, i.e., a procedure based on manipulating semilinear sets. This matches the running time of the best quantifier elimination and automata-based procedures. Second, building upon our first result, we give a doubly exponential upper bound on the Vapnik–Chervonenkis (VC) dimension of sets definable in LIA, proving a conjecture of D. Nguyen and I. Pak [Combinatorica 39, pp. 923–932, 2019].
These results partially rely on an analysis of sets definable in linear real arithmetic (LRA), and analogous results for LRA are also obtained. At the core of these developments are new decomposition results for semilinear and -semilinear sets, the latter being the sets definable in LRA. These results yield new algorithms to compute the complement of (-)semilinear sets that do not cause a non-elementary blowup when repeatedly combined with procedures for other Boolean operations and projection. The existence of such an algorithm for semilinear sets has been a long-standing open problem.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Computer logic, Machine learning, Computer arithmetic and logic units, Polyhedra -- Mathematical models | ||||||
Journal or Publication Title: | LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science | ||||||
Publisher: | ACM | ||||||
ISBN: | 9781450393515 | ||||||
Official Date: | 4 August 2022 | ||||||
Dates: |
|
||||||
Page Range: | pp. 1-13 | ||||||
Article Number: | 59 | ||||||
DOI: | 10.1145/3531130.3533372 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (LICS ’22), August 2–5, 2022, Haifa, Israel, https://doi.org/10.1145/3531130.3533372 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 17 June 2022 | ||||||
Date of first compliant Open Access: | 17 June 2022 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Haifa, Israel | ||||||
Date(s) of Event: | 02–05 Aug 2022 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year