tkrauckland.ac.nz

Doctoral Candidate in

Supervised by

Co-supervised by

Office

Room 576, Building 303SScience Building

Department of Computer Science

38 Princes Street

The University of Auckland

Postal Address

Department of Computer ScienceThe University of Auckland

Private Bag 92019

Auckland, New Zealand

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

2012-Present

PhD Candidate, Computer Science

University of Auckland, New Zealand

2011

MSc with First Class Honours, Computer Science

University of Auckland, New Zealand

Sep 2010 - Oct 2010

Internship (8-weeks) under the supervision of Dr. François Coste

INRIA Rennes, France

2010

BSc(Hons) Second Class First Division, Computer Science

University of Auckland, New Zealand

2010

Faculty of Science Masters Scholarship, University of Auckland

2009

Faculty of Science Summer Scholarship, University of Auckland

2008

Senior Prize in French, University of Auckland

2007

Faculty of Science Summer Scholarship, University of Auckland

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 the CS approach

M. Sipser. *Introduction to the Theory of Computation*. Course Technology, second edition, 2005. [undergraduate textbook]

S. Arora and B. Barak. *Computational Complexity: A Modern Approach*. Cambridge University Press, 2009. [beginners graduate textbook]

For the Math approach

S. B. Cooper. *Computability Theory*, Chapman and Hall/CRC, 2004. [undergraduate textbook]

A. Nies. *Computability and Randomness*. Oxford University Press, 2009. [advanced graduate textbook - nicely ties in with CS foundation]

R. G. Downey and D. R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer, 2010. [advanced text - currently the bible of both computability and complexity theory]

For further reading on database theory and probabilistic databases I direct you to the following:

S. Abiteboul, R. Hull and V. Vianu. *Foundations of Databases*. Addison-Wesley, 1995.

D. Suciu, D. Olteanu, R. Christopher and C. Koch. *Probabilistic Databases*. Morgan & Claypool Publishers, 2011.

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

- C. S. Calude, K. Salomaa and T. K. Roblot.
*Finite State Complexity*. Theoretical Computer Science, vol. 412, 41, 2011, 5668--5677. - C. S. Calude, K. Salomaa and T. K. Roblot.
*Finite-State Complexity and Randomness*. CDMTCS Research Report 374, 2009. Revised June 2010. Extended abstract presented at CiE 2010. - Cristian S. Calude, Kai Salomaa, Tania K. Roblot.
*Finite-State Complexity and Randomness*, in F. Ferreira, H. Guerra, E. Majordomo, J. Rasga (ed.s). In Proceedings of the Sixth Conference on Computability in Europe: Programs, Proofs, Processes (CiE 2010), Ponta Delgada, Azores, Portugal, University of Azores, 2010, 73--82. - C. S. Calude, K. Salomaa and T. K. Roblot.
*Finite-State Complexity and the Size of Transducers*, in I. McQuillan and G. Pighizzini (eds.). In Proceedings of the 12th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), EPTCS 26, 2010, 38--47. - C. S. Calude, K. Salomaa, and T. K. Roblot.
*State-size hierarchy for FS-complexity*. International Journal of Foundations of Computer Science, Vol. 23, Issue 01, 37, 2012. DOI: 10.1142/S0129054112400035. - T. K. Roblot.
*An Algorithm Computing The Finite-State Complexity*. In Proceedings of the New Zealand Computer Science Research Student Conference (NZCSRSC 2010), 2010. - T. K. Roblot and S. Link.
*Probabilistic cardinality constraints*. CDMTCS Research Report 481, 2015. - T. K. Roblot and S. Link.
*Probabilistic cardinality constraints*. In Proceedings of the 34th International Conference on Conceptual Modeling (ER 2015), Stockholm, Sweden, 2015. - T. K. Roblot and S. Link.
*Possibilistic cardinality constraints and functional dependencies*. In Proceedings of the 35th International Conference on Conceptual Modeling (ER 2016), Gifu, Japan, 2016. (To appear)