Optimal synthesis of reversible functions is a nontrivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16! ≈ 244functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present two algorithms: one, that synthesizes an optimal circuit for any 4-bit reversible specification, and another that synthesizes all optimal implementations. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of all optimal 4-bit permutations, synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, and synthesis of existing benchmark functions; we compose a list of the hardest permutations to synthesize, and show distribution of optimal circuits. We further illustrate that our proposed approach may be extended to accommodate physical constraints via reporting LNN-optimal reversible circuits. Our results have important implications in the design and optimization of reversible and quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.

Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a complexity explosion (16! ≈ 244 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage.

We address the problem of handwritten symbol classification in the presence of distortions modeled by affine transformations. We consider shear, rotation, scaling and translation, since these types of transformations occur most often in practice, and focus most on shear within this framework. We present a distance-based classification method, in which feature vectors are constructed from Legendre-Sobolev expansions of the coordinate functions and of the affine integral invariants of the curves given by the symbol's ink strokes. We analyze different size normalization methods and conclude that integral invariants provide the most robust norm. Finally, we propose a new parameterization, a combination of arc length and time, insensitive to variations in curve tracing speed and affine distortion.

We consider the problem of dealing with irrelevant votes when a multi-case classifier is built from an ensemble of binary classifiers. We show how run-off elections can be used to limit the effects of irrelevant votes and the occasional errors of binary classifiers, improving classification accuracy. We consider as a concrete classification problem the recognition of handwritten mathematical characters. A succinct representation of handwritten symbol curves can be obtained by computing truncated Legendre-Sobolev expansions of the coordinate functions. With this representation, symbol classes are well linearly separable in low dimension which yields fast classification algorithms based on linear support vector machines. A set of 280 different symbols was considered, which gave 1635 classes when different variants are labelled separately. With this number of classes, however, the effect of irrelevant classifiers becomes significant, often causing the correct class to be ranked lower. We introduce a general technique to correct this effect by replacing the conventional majority voting scheme with a runoff election scheme. We have found that such runoff elections further cut the top-1 mis-classification rate by about half.

We propose an efficient method to recognize multi-stroke handwritten symbols. The method is based on computing the truncated Legendre-Sobolev expansions of the coordinate functions of the stroke curves and classifying them using linear support vector machines. Earlier work has demonstrated the efficiency and robustness of this approach in the case of single-stroke characters. Here we show that the method can be successfully applied to multi-stroke characters by joining the strokes and including the number of strokes in the feature vector or in the class labels. Our experiments yield an error rate of 11-20%, and in 99% of cases the correct class is among the top 4. The recognition process causes virtually no delay, because computation of Legendre-Sobolev expansions and SVM classification proceed on-line, as the strokes are written.