Towards practical universal search

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

10 Scopus citations


Universal Search is an asymptotically optimal way of searching the space of programs computing solution candidates for quickly verifiable problems. Despite the algorithm's simplicity and remarkable theoretical properties, a potentially huge constant slowdown factor has kept it from being used much in practice. Here we greatly bias the search with domain-knowledge, essentially by assigning short codes to programs consisting of few but powerful domain-specific instructions. This greatly reduces the slowdown factor and makes the method practically useful. We also show that this approach, when encoding random seeds, can significantly reduce the expected search time of stochastic domain-specific algorithms. We further present a concrete study where Practical Universal Search (PUnS) is successfully used to combine algorithms for solving satisfiability problems.
Original languageEnglish (US)
Title of host publicationArtificial General Intelligence - Proceedings of the Third Conference on Artificial General Intelligence, AGI 2010
PublisherAtlantis Press
Number of pages6
ISBN (Print)9789078677369
StatePublished - Jan 1 2010
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2022-09-14


Dive into the research topics of 'Towards practical universal search'. Together they form a unique fingerprint.

Cite this