Edinburgh Research Explorer

Measuring the likelihood of numerical constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions



Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2019
Subtitle of host publicationAugust 10-16, 2019, Macao
PublisherInternational Joint Conferences on Artificial Intelligence Organization
Number of pages7
ISBN (Electronic)978-0-9992411-4-1
Publication statusPublished - 31 Aug 2019
Event28th International Joint Conference on Artificial Intelligence - Convention Center of the Venetian Macao Hotel Resort, Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28


Conference28th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI-19
Internet address


Our goal is to measure the likelihood of the satisfaction of numerical constraints in the absence of any prior information. Intuitively, the likelihood of x>y is 0.5, if we know nothing about x and y. We study expressive constraints, involving arithmetic and complex numerical functions, and even quantification over numbers. Such problems arise in processing incomplete data, or estimating the likelihood of conditions in programs without a priori bounds on variables.We show that for constraints on n variables, the proper way to define such a measure is as the limit of the part of the n-dimensional ball that consists of points satisfying the constraints, when the radius of the ball increases. We prove that the existence of such a limit is closely related to the notion of o-minimality from model theory. For example, for constraints definable with the usual arithmetic and exponentiation, the likelihood is well defined, but adding trigonometric functions is problematic. We then look at computing and approximating such likelihoods for order and linear constraints. We prove an impossibility result for approximating with multiplicative error, even for order constraints. However, as the likelihood is a number between 0 and 1, an approximation scheme with additive error is acceptable, and we give such a scheme for arbitrary linear constraints.


28th International Joint Conference on Artificial Intelligence


Macao, China

Event: Conference

Download statistics

No data available

ID: 93478437