We live on an island surrounded by a sea of ignorance. As our island of knowledge grows, so does the shore of our ignorance. John Archibald Wheeler
Most of my research history has been in algorithmic information theory (AIT), with a focus on finding valid computable complexity measures. AIT is a specific branch of computational complexity and is concerned with the randomness and complexity of finite and infinite bit-strings, also known as binary strings and sequences. Thus far, the main complexity measure is the (prefix) descriptive complexity, also known as Kolmogorov complexity. This complexity is based on Turing machines. Although the former has brought forth many theoretical results, it is incomputable because it is confronted by the Halting problem - a problem entwined with Turing machines. My work has primarily been focused on finding and proving a computable complexity measure, analogue to Kolmogorov's complexity. We have been successful in this with the finite-state descriptional complexity (FSC). We have also implemented several successful algorithms which are mainly brute-force at this stage. Now my interest is focused on the properties of this complexity and how much it defers from - or follows - its 'parent' complexity. Furthermore, I am highly interested in investigating the properties concerning infinite (binary) sequences in relation to the finite-state complexity.
Algorithmic information theory (AIT) is the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously. Gregory J. Chaitin
My PhD project has moved away from the AIT subfield and into database theory. Specifically, database constraints and probabilistic databases. Our goal is to adapt the well-known and useful concept of cardinality constraints from the standard relational model into the probabilistic model. Cardinality constraints are a concept born from the entity-relationship (ER) model. They were originally designed as a component of the ER diagram to represent the number of instances of one entity that can or must be associated with each instance of another entity. Probabilistic databases are a fairly new model designed to manage uncertain data.
So far, we have looked into max cardinality constraints (as they are called in the standard relational model), of the form $card(X) \leq b$, and introduced them to the probabilistic model by adding a bound on the marginal probability. For each type of bound, we developed a GUI. The first, named Fortuna, handles lower bounds on the marginal probability of a cardinality constraint, denoted $(card(X) \le b, \ge p)$, and constructs a probabilistic Armstrong database given a set of these probabilistic cardinality constraints with lower bounds (l-pCCs, or l-CCs). If you would like to see screenshots of it working or try out the current version of that GUI yourself: click here. The second, named Tyche, is Fortuna's counterpart, handling probabilistic cardinality constraints with upper bounds (u-pCCs, or u-CCs), denoted $(card(X) \le b, \le p)$. Finally, Urd combines the work of both Fortuna and Tyche to handle cardinality constraints with probabilistic intervals (pCCs). For screenshots and a downloadable version of Urd: click here.
For further reading on computational complexity (from either a computer science or a mathematical point of view), I direct you to the following:
For further reading on database theory and probabilistic databases I direct you to the following:
I am also interested in Anytime Algorithms. These are a specific type of Artificial Intelligence search algorithms, which consist of providing a sub-optimal solution at any point of the computation. The longer the algorithm is run, the better the solution. These algorithms are usually used in planning but some in-class research (in collaboration with Sonny Datt) has suggested that pairing anytime algorithms with Hierarchical planning would give promising and desirable results.
My other interests lie in Graph Theory, History of Computing and Computer Science Education.
Success is not final, failure is not fatal: it is the courage to continue that counts. Sir Winston Churchill
I have worked as an Undergraduate General Lab demonstrator and as a Teaching Assistant for the following courses, categorised below by role (note that there is some overlap).
I never see what has been done; I only see what remains to be done. Marie Curie
Honours Dissertation supervised by Prof. Cristian S. Calude and Assoc. Prof. André Nies.
This dissertation is an original work in the field of AIT; offering both a review of the work on depth and an analogue complexity to Kolmogorov complexity, finite-state complexity. Depth was first introduced by Bennett and further explored by Doty and Moser. It uses the complexity measure to introduce this notion of depth, a more intuitive measure of strings and sequences. The original research in this dissertation is the finite-state complexity, which is a computable complexity measure and which is founded on generalised finite-state transducers as opposed to Turing machines as with Kolmogorov complexity. We offer both the proof of its computability and a brute-force algorithm for its computation.
Masters Thesis supervised by Prof. Cristian S. Calude and Dr. Michael J. Dinneen.
This thesis is an original work in the field of AIT which furthers the work first introduced in my Honours dissertation, Finite-State Descriptional Complexity. In this thesis, we propose a new variant to Algorithmic Information Theory. This new theory is constructed around finite-state complexity, a computable counterpart to Kolmogorov complexity based on finite transducers rather than Turing machines.
The greatest appeal to this new complexity measure is its computability, which we prove and begin to exploit thanks to our main algorithm-presented in this thesis. We also explore concepts such as incompressibility and state-size hierarchy. This thesis also covers a first attempt at applying the finite-state complexity in a practical setting: the approximative measure of DNA's finite-state complexity. In sight of the practical limitations we currently face with measuring the finite-state complexity of sequences of such great length, we compromise with an approximative measure of the finite-state complexity of DNA sequences. We achieve this through using the results of a DNA-focused grammar-based compressor, Iterative Repeat Replacement Minimal Grammar Parsing, and converting the resulting `smallest' straight-line grammars into transducers. We also explore ways in which to optimise our conversion algorithms by heuristic means.
Science is a way of thinking much more than it is a body of knowledge. Carl Sagan