Combinatorial Search and Computational Complexity

Gabriel Currier, Colin Okasaki, Liljana Babinkostova, Marion Scheepers

Research output: Contribution to conferencePresentation

Abstract

Many practical problems have the goal of identifying, with limited resources, a small number of objects from a large collection - be it a faulty circuit in a complex device, an infected individual in a population, a cryptographic key in a cyber attack, or a person of interest in a series of crimes. Although some such search problems are believed to require exhaustive search in general, many practical instances have yielded to carefully designed efficient search strategies.

Our research focuses on the design and analysis of such efficient search techniques using combinatorial structures called splitting systems. The smaller a splitting system is, the more efficiently large-scale searches based on it can be executed. We hope to identify techniques for creating very small splitting systems in an attempt to speed up these processes. The methods used in this investigation stem from the fields of discrete mathematics and combinatorics.

Original languageAmerican English
StatePublished - 12 Jul 2015

EGS Disciplines

  • Algebra
  • Discrete Mathematics and Combinatorics
  • Information Security

Fingerprint

Dive into the research topics of 'Combinatorial Search and Computational Complexity'. Together they form a unique fingerprint.

Cite this