I am working towards a research qualification in the Computing Laboratory at the University of Oxford. Visit the academic homepage of Andras Salamon for more information about my current research in constraint satisfaction.
My current work mostly relates to the mathematics of constraint satisfaction. A good representative paper in this area is Classifying the Complexity of Constraints Using Finite Algebras by Andrei Bulatov, Peter Jeavons, and Andrei Krokhin, or see the preprint for the freely available version of this document.
A BibTeX file of bibliography entries for my published research is available.
From 1990 to 1994 I investigated stochastic properties of task graphs at the University of the Witwatersrand, initially as a final-year undergraduate, and then as an MSc student in Computer Science. A technical report is available summarising some of the results of this work.
The most interesting result of this work is: with work-preserving scheduling and infinite processors, if a subgraph relation between task graphs holds, then their execution time distributions are pointwise comparable. It then trivially follows that the expected mean execution times are also comparable. This gives simpler derivations for several known results.
Changing focus from a stochastic to a deterministic model emphasizing the poset structure of task graphs, I was awarded an MSc (with distinction) in April 2001 for a dissertation on task graph performance bounds (PDF format, 141 pages; abstract).
The dissertation considers the relationship between the structure of a task graph (activity-on-node network), and its execution time (makespan). It turns out that two task graphs are makespan-comparable for all workloads precisely when one is a reorder-extension of the other. (This occurs precisely when the underlying comparability graphs are comparable by the subgraph relation.)
A best series-parallelisation is formed by adding precedence constraints to a task graph, so that the resulting task graph is series-parallel and has minimal makespan among all such series-parallelisations, for a given set of task durations (workload). A bounded slowdown conjecture is posed: is it always possible to add precedence constraints to a task graph so that the new graph is series-parallel and has makespan at most 4/3 times that of the original? This bound is shown to be the best possible, and the conjecture is shown to be true for 4-node graphs. Using modular decompositions, a theory is also developed which allows the 5-node case to be reduced to considering only three cases.In 2003, I confirmed the 4/3 bounded slowdown conjecture for the cases with 5 and 6 nodes, by applying the constraint solver clp(q,r) to the systems of inequalities obtained by enumerating all possible cases.
The number of candidate posets is very large even for 6 nodes, so I am working on techniques to reduce the size of the candidate set using additional domination properties. The software to exhaustively check all possible cases also needs further work, since its complexity makes it difficult to demonstrate its correctness.
The 7-node case should be especially interesting, since that is the minimum number of nodes required for an N-poset composed with another N-poset, for which my current modular decomposition results can only be used to prove a 16/9 bound.
The complexity of producing 4/3 series-parallelisations appears to be NP-hard. This seems quite difficult to prove. The form of the problem is quite different to most existing NP-complete problems, so modelling the reduction along the lines of existing reductions has not proved useful.