Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number eta(G) of a graph G is the largest integer n for which the complete graph K-n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, eta(G) >= chi(G), where chi(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product G square H of graphs. As the main result of this paper, we prove that eta(G(1) square G(2)) >= h root 1 (1 - o(1)) for any two graphs G(1) and G(2) with eta(G(1)) = h and eta(G(2)) = l. We show that the above lower bound is asymptotically best possible when h >= l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: 1. Let G be a connected graph. Let G = G(1) square G(2) square ... square G(k) be the ( unique) prime factorization of G. Then G satisfies Hadwiger's conjecture if k >= 2 log log chi(G) + c', where c' is a constant. This improves the 2 log chi(G) + 3 bound in [2] 2. Let G(1) and G(2) be two graphs such that chi(G1) >= chi(G2) >= clog(1.5)(chi(G(1))), where c is a constant. Then G1 square G2 satisfies Hadwiger's conjecture. 3. Hadwiger's conjecture is true for G(d) (Cartesian product of G taken d times) for every graph G and every d >= 2. This settles a question by Chandran and Sivadasan [2]. ( They had shown that the Hadiwger's conjecture is true for G(d) if d >= 3).

Developing and Integrating HRM Practices in MNC Subsidiaries in China

Whilst previous research on Human Resource Management (HRM) in subsidiaries of multinational companies (MNCs) has focused extensively on the HRM practices that exist in foreign subsidiaries and the extent to which they resemble MNC home country and/or local host country practices, considerably less attention has been directed at the question of how these practices come to exist. Accordingly, this thesis aims to shed light on the processes that shape HRM practices and capabilities in MNC subsidiaries. The main contribution of the thesis is the focus on how; how HRM practices are integrated in MNC subsidiaries, and how subsidiary HRM capabilities are developed through involvement in social networks. Furthermore, this thesis includes a time aspect which, despite not being purely longitudinal, provides an indication of the ongoing changes in HRM in MNC subsidiaries in China. Data for this study were collected in 2005-2006 through structured face to face interviews with 153 general managers and HR managers in 87 subsidiaries of European MNCs located in China. Five of the six thesis papers build on this questionnaire data and one paper builds on qualitative data collected at the same time. Two papers build on dual data sets, meaning that they in addition to the abovementioned data include quantitative questionnaire data from 1996 and 1999 respectively. The thesis focuses on the following four sub-questions i) To what extent do subsidiary HRM practices resemble parent MNC and host country practices? How has this changed over time and why? ii) How are HRM practices integrated into MNC subsidiaries and why are certain integration mechanisms used? iii) How does involvement in internal and external social networks influence subsidiary HRM capabilities? iv) What factors influence the strategic role of the subsidiary HR department? Regarding the first sub-question the findings indicate that the HRM practices of MNC subsidiaries in China are converging with both local company practices and parent MNC practices. This is interesting in the sense that it suggests that the isomorphic pressures the subsidiary faces from the MNC and from its local host environment are not always in conflict with each other. Concerning the question of how HRM practices are integrated into MNC subsidiaries and why certain integration mechanisms are used, the thesis provides a fine-grained examination of four mechanisms that MNCs use to integrate HRM practices in subsidiaries. The findings suggest that MNCs use a variety of different integration mechanisms as complements rather than as substitutes for each other. Furthermore, it is apparent that different contextual factors in the subsidiary and the subsidiary-headquarters relationship influence why certain mechanisms are or are not used. The most interesting contribution of the thesis in regard to the third question is that it highlights the importance of network involvement for learning about HRM practices in the Chinese context. Networks with other MNCs in China clearly emerged as particularly important contributors to enhanced HRM capabilities. Finally, concerning the fourth sub-question the findings indicate that the role of the HR department in MNC subsidiaries in China had become more strategic between 1999 and 2006.

On Finding the Natural Number of Topics with Latent Dirichlet Allocation: Some Observations

It is important to identify the ``correct'' number of topics in mechanisms like Latent Dirichlet Allocation(LDA) as they determine the quality of features that are presented as features for classifiers like SVM. In this work we propose a measure to identify the correct number of topics and offer empirical evidence in its favor in terms of classification accuracy and the number of topics that are naturally present in the corpus. We show the merit of the measure by applying it on real-world as well as synthetic data sets(both text and images). In proposing this measure, we view LDA as a matrix factorization mechanism, wherein a given corpus C is split into two matrix factors M-1 and M-2 as given by C-d*w = M1(d*t) x Q(t*w).Where d is the number of documents present in the corpus anti w is the size of the vocabulary. The quality of the split depends on ``t'', the right number of topics chosen. The measure is computed in terms of symmetric KL-Divergence of salient distributions that are derived from these matrix factors. We observe that the divergence values are higher for non-optimal number of topics - this is shown by a `dip' at the right value for `t'.

Weak Ehrenfeucht-Fraïssé Games

In this paper we define a game which is played between two players I and II on two mathematical structures A and B. The players choose elements from both structures in moves, and at the end of the game the player II wins if the chosen structures are isomorphic. Thus the difference of this to the ordinary Ehrenfeucht-Fra¨ıss´e game is that the isomorphism can be arbitrary, whereas in the ordinary EF-game it is determined by the moves of the players. We investigate determinacy of the weak EF-game for different (the length of the game) and its relation to the ordinary EF-game.

Properties of Toeplitz operators on analytic function spaces : from function symbols to distributions

Toeplitz operators are among the most important classes of concrete operators with applications to several branches of pure and applied mathematics. This doctoral thesis deals with Toeplitz operators on analytic Bergman, Bloch and Fock spaces. Usually, a Toeplitz operator is a composition of multiplication by a function and a suitable projection. The present work deals with generalizing the notion to the case where the function is replaced by a distributional symbol. Fredholm theory for Toeplitz operators with matrix-valued symbols is also considered. The subject of this thesis belongs to the areas of complex analysis, functional analysis and operator theory. This work contains five research articles. The articles one, three and four deal with finding suitable distributional classes in Bergman, Fock and Bloch spaces, respectively. In each case the symbol class to be considered turns out to be a certain weighted Sobolev-type space of distributions. The Bergman space setting is the most straightforward. When dealing with Fock spaces, some difficulties arise due to unboundedness of the complex plane and the properties of the Gaussian measure in the definition. In the Bloch-type spaces an additional logarithmic weight must be introduced. Sufficient conditions for boundedness and compactness are derived. The article two contains a portion showing that under additional assumptions, the condition for Bergman spaces is also necessary. The fifth article deals with Fredholm theory for Toeplitz operators having matrix-valued symbols. The essential spectra and index theorems are obtained with the help of Hardy space factorization and the Berezin transform, for instance. The article two also has a part dealing with matrix-valued symbols in a non-reflexive Bergman space, in which case a condition on the oscillation of the symbol (a logarithmic VMO-condition) must be added.

Structure of Relativistic States

QCD factorization in the Bjorken limit allows to separate the long-distance physics from the hard subprocess. At leading twist, only one parton in each hadron is coherent with the hard subprocess. Higher twist effects increase as one of the active partons carries most of the longitudinal momentum of the hadron, x -> 1. In the Drell-Yan process \pi N -> \mu^- mu^+ + X, the polarization of the virtual photon is observed to change to longitudinal when the photon carries x_F > 0.6 of the pion. I define and study the Berger-Brodsky limit of Q^2 -> \infty with Q^2(1-x) fixed. A new kind of factorization holds in the Drell-Yan process in this limit, in which both pion valence quarks are coherent with the hard subprocess, the virtual photon is longitudinal rather than transverse, and the cross section is proportional to a multiparton distribution. Generalized parton distributions contain information on the longitudinal momentum and transverse position densities of partons in a hadron. Transverse charge densities are Fourier transforms of the electromagnetic form factors. I discuss the application of these methods to the QED electron, studying the form factors, charge densities and spin distributions of the leading order |e\gamma> Fock state in impact parameter and longitudinal momentum space. I show how the transverse shape of any virtual photon induced process, \gamma^*(q)+i -> f, may be measured. Qualitative arguments concerning the size of such transitions have been previously made in the literature, but without a precise analysis. Properly defined, the amplitudes and the cross section in impact parameter space provide information on the transverse shape of the transition process.

Diffraction of a cylindrical pulse by a metallic half plane

A direct transform technique is applied to the initial and boundary value problem involving diffraction of a cylindrical pulse by a half plane, on which impedance type of boundary conditions must be met by the total field. The solution to the time harmonic incident plane wave is deduced as a particular case of the general time-dependent problem considered here and we avoid the Wiener–Hopf technique which leads to very complicated factorization and which masks the role of the impedance factor Z′ (a small quantity) in the expression for the scattered field.

Points-to Analysis as a System of Linear Equations

We propose a novel formulation of the points-to analysis as a system of linear equations. With this, the efficiency of the points-to analysis can be significantly improved by leveraging the advances in solution procedures for solving the systems of linear equations. However, such a formulation is non-trivial and becomes challenging due to various facts, namely, multiple pointer indirections, address-of operators and multiple assignments to the same variable. Further, the problem is exacerbated by the need to keep the transformed equations linear. Despite this, we successfully model all the pointer operations. We propose a novel inclusion-based context-sensitive points-to analysis algorithm based on prime factorization, which can model all the pointer operations. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that our approach is competitive to the state-of-the-art algorithms. With an average memory requirement of mere 21MB, our context-sensitive points-to analysis algorithm analyzes each benchmark in 55 seconds on an average.

Parts based representation for pedestrian using NMF with robustness to partial occlusion

Computer Vision has seen a resurgence in the parts-based representation for objects over the past few years. The parts are usually annotated beforehand for training. We present an annotation free parts-based representation for the pedestrian using Non-Negative Matrix Factorization (NMF). We show that NMF is able to capture the wide range of pose and clothing of the pedestrians. We use a modified form of NMF i.e. NMF with sparsity constraints on the factored matrices. We also make use of Riemannian distance metric for similarity measurements in NMF space as the basis vectors generated by NMF aren't orthogonal. We show that for 1% drop in accuracy as compared to the Histogram of Oriented Gradients (HOG) representation we can achieve robustness to partial occlusion.

Some results on the reconstruction problems. p-claw-free, chordal, and p4-reducible graphs

A claw is an induced subgraph isomorphic to K-1,K-3. The claw-point is the point of degree 3 in a claw. A graph is called p-claw-free when no p-cycle has a claw-point on it. It is proved that for p greater than or equal to 4, p-claw-free graphs containing at least one chordless p-cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw-free graphs. A simple proof of vertex reconstructibility of P-4-reducible graphs is also presented. (C) 1995 John Wiley and Sons, Inc.

Robust Observer Design with Application to Fault Detection

A new scheme for robust estimation of the partial state of linear time-invariant multivariable systems is presented, and it is shown how this may be used for the detection of sensor faults in such systems. We consider an observer to be robust if it generates a faithful estimate of the plant state in the face of modelling uncertainty or plant perturbations. Using the Stable Factorization approach we formulate the problem of optimal robust observer design by minimizing an appropriate norm on the estimation error. A logical candidate is the 2-norm, corresponding to an H�¿ optimization problem, for which solutions are readily available. In the special case of a stable plant, the optimal fault diagnosis scheme reduces to an internal model control architecture.

Contractive Hilbert modules and their dilations

In this note, we show that a quasi-free Hilbert module R defined over the polydisk algebra with kernel function k(z,w) admits a unique minimal dilation (actually an isometric co-extension) to the Hardy module over the polydisk if and only if S (-1)(z, w)k(z, w) is a positive kernel function, where S(z,w) is the Szego kernel for the polydisk. Moreover, we establish the equivalence of such a factorization of the kernel function and a positivity condition, defined using the hereditary functional calculus, which was introduced earlier by Athavale [8] and Ambrozie, Englis and Muller [2]. An explicit realization of the dilation space is given along with the isometric embedding of the module R in it. The proof works for a wider class of Hilbert modules in which the Hardy module is replaced by more general quasi-free Hilbert modules such as the classical spaces on the polydisk or the unit ball in a'', (m) . Some consequences of this more general result are then explored in the case of several natural function algebras.

Spacelike pion form factor from analytic continuation and the onset of perturbative QCD

The factorization theorem for exclusive processes in perturbative QCD predicts the behavior of the pion electromagnetic form factor F(t) at asymptotic spacelike momenta t(= -Q(2)) < 0. We address the question of the onset energy using a suitable mathematical framework of analytic continuation, which uses as input the phase of the form factor below the first inelastic threshold, known with great precision through the Fermi-Watson theorem from pi pi elastic scattering, and the modulus measured from threshold up to 3 GeV by the BABAR Collaboration. The method leads to almost model-independent upper and lower bounds on the spacelike form factor. Further inclusion of the value of the charge radius and the experimental value at -2.45 GeV2 measured at JLab considerably increases the strength of the bounds in the region Q(2) less than or similar to 10 GeV2, excluding the onset of the asymptotic perturbative QCD regime for Q(2) < 7 GeV2. We also compare the bounds with available experimental data and with several theoretical models proposed for the low and intermediate spacelike region.

Feature selection for unsupervised learning

In this paper, we present a methodology for identifying best features from a large feature space. In high dimensional feature space nearest neighbor search is meaningless. In this feature space we see quality and performance issue with nearest neighbor search. Many data mining algorithms use nearest neighbor search. So instead of doing nearest neighbor search using all the features we need to select relevant features. We propose feature selection using Non-negative Matrix Factorization(NMF) and its application to nearest neighbor search. Recent clustering algorithm based on Locally Consistent Concept Factorization(LCCF) shows better quality of document clustering by using local geometrical and discriminating structure of the data. By using our feature selection method we have shown further improvement of performance in the clustering.