Kamalika Bhattacharjee

Bhuvaneswari A, Kamalika Bhattacharjee

An equidistribution is a theoretical quality criteria that measures the uniformity of a linear pseudo-random number generator (PRNG). In this work, we first show that all existing linear cellular automaton (CA) based pseudo-random number generators (PRNGs) are weak in the equidistribution characteristic. Then we propose a list of light-weight combined CA-based PRNGs with time spacing ($2 \leq s \leq 10$) using linear maximal length cellular automata of degree $31 \leq k \leq 128$ (close to computer word size). We show that these PRNGs achieve maximal period as well as satisfy the maximal equidistribution property. Finally, we show that these combined maximal length CA-based PRNGs pass almost all the empirical testbeds, with speed and performance comparable to the Mersenne Twister.

Baby C. J., Kamalika Bhattacharjee

This work proposes a hierarchical clustering algorithm for high-dimensional datasets using the cyclic space of reversible finite cellular automata. In cellular automaton (CA) based clustering, if two objects belong to the same cycle, they are closely related and considered as part of the same cluster. However, if a high-dimensional dataset is clustered using the cycles of one CA, closely related objects may belong to different cycles. This paper identifies the relationship between objects in two different cycles based on the median of all elements in each cycle so that they can be grouped in the next stage. Further, to minimize the number of intermediate clusters which in turn reduces the computational cost, a rule selection strategy is taken to find the best rules based on information propagation and cycle structure. After encoding the dataset using frequency-based encoding such that the consecutive data elements maintain a minimum hamming distance in encoded form, our proposed clustering algorithm iterates over three stages to finally cluster the data elements into the desired number of clusters given by user. This algorithm can be applied to various fields, including healthcare, sports, chemical research, agriculture, etc. When verified over standard benchmark datasets with various performance metrics, our algorithm is at par with the existing algorithms with quadratic time complexity.

Vicky Vikrant, Narodia Parth P, Kamalika Bhattacharjee

In this paper, a decimal first degree cellular automata (FDCA) based clustering algorithm is proposed where clusters are created based on reachability. Cyclic spaces are created and configurations which are in the same cycle are treated as the same cluster. Here, real-life data objects are encoded into decimal strings using Gödel number based encoding. The benefits of the scheme is, it reduces the encoded string length while maintaining the features properties. Candidate CA rules are identified based on some theoretical criteria such as self-replication and information flow. An iterative algorithm is developed to generate the desired number of clusters over three stages. The results of the clustering are evaluated based on benchmark clustering metrics such as Silhouette score, Davis Bouldin, Calinski Harabasz and Dunn Index. In comparison with the existing state-of-the-art clustering algorithms, our proposed algorithm gives better performance.

Kamalika Bhattacharjee, Sukanta Das

This paper targets to search so-called \emph{good} generators by doing a brief survey over the generators developed in the history of pseudo-random number generators (PRNGs), verify their claims and rank them based on strong empirical tests in same platforms. To do this, the genre of PRNGs developed so far are explored and classified into three groups -- linear congruential generator based, linear feedback shift register based and cellular automata based. From each group, the well-known widely used generators which claimed themselves to be `\emph{good}' are chosen. Overall $30$ PRNGs are selected in this way on which two types of empirical testing are done -- blind statistical tests with Diehard battery of tests, battery \emph{rabbit} of TestU01 library and NIST statistical test-suite as well as graphical tests (lattice test and space-time diagram test). Finally, the selected PRNGs are divided into $24$ groups and are ranked according to their overall performance in all empirical tests.