A well known birthday paradox is one the most important problems in cryptographic applications. Incremental hash functions or digital signatures in public key cryptography and low-weight parity check equations of LFSRs in stream ciphers are examples of such applications which benet from birthday problem theories to run their attacks. Wagner introduced and formulated the k-dimensional birthday problem and proposed an algorithm to solve the problem in O(k.m^ 1/log k ). The generalized birthday solutions used in some applications to break Knapsack based systems or collision nding in hash functions. The optimized birthday algorithms can solve Knapsack problems of dimension n which is believed to be NP-hard. Its equivalent problem is Subset Sum Problem nds the solution over Z/mZ. The main property for the classication of the problem is density. When density is small enough the problem reduces to shortest lattice vector problem and has a solution in polynomial time. Assigning a variable to each element of the lists, decoding them into a matrix and considering each row of the matrix as an equation lead us to have a multivariate polynomial system of equations and all solution of this type can be a solution for the k- list problem such as F4, F5, another strategy called eXtended Linearization (XL) and sl. We discuss the new approaches and methods proposed to reduce the complexity of the algorithms. For particular cases in over-determined systems, more equations than variables, regarding to have a single solutions Wolf and Thomea work to make a gradual decrease in the complexity of F5. Moreover, his group try to solve the problem by monomials of special degrees and linear equations for small lists. We observe and compare all suggested methods in this

Yes / The present study demonstrates the application of decision tree algorithms to the co-crystallization process. Fifty four (54) batches of carbamazepine-salicylic acid co-crystals embedded in poly(ethylene oxide) were manufactured via hot melt extrusion and characterized by powder X-ray diffraction, differnetial scanning calorimetry, and near-infrared spectroscopy. This dataset was then applied in WEKA, which is an open-sourced machine learning software to study the effect of processing temperature, screw speed, screw configuration, and poly(ethylene oxide) concentration on the percentage of co-crystal conversion. The decision trees obtained provided statistically meaningful and easy-to-interpret rules, demonstrating the potential to use the method to make rational decisions during the development of co-crystallization processes. / Commonwealth Scholarship Commission in the UK (ZMCS-2018-783) and Engineering and Physical Sciences Research Council (EPSRC EP/J003360/1 and EP/L027011/1)

This large body of work is entirely centered around dual-tree algorithms, a class of algorithm based on spatial indexing structures that often provide large amounts of acceleration for various problems. This work focuses on understanding dual-tree algorithms using a new, tree-independent abstraction, and using this abstraction to develop new algorithms. Stated more clearly, the thesis of this entire work is that we may improve and expand the class of dual-tree algorithms by focusing on and providing improvements for each of the three independent components of a dual-tree algorithm: the type of space tree, the type of pruning dual-tree traversal, and the problem-specific BaseCase() and Score() functions. This is demonstrated by expressing many existing dual-tree algorithms in the tree-independent framework, and focusing on improving each of these three pieces. The result is a formidable set of generic components that can be used to assemble dual-tree algorithms, including faster traversals, improved tree theory, and new algorithms to solve the problems of max-kernel search and k-means clustering.

The Fast Multipole Method of Greengard and Rokhlin does the seemingly impossible: it approximates the quadratic scaling N-body problem in linear time. The key is to avoid explicitly computing the interactions between all pairs of N points. Instead, by organizing the data in a space-partitioning tree, distant interactions are quickly and efficiently approximated. Similarly, dual-tree algorithms, which approximate or eliminate parts of a computation using distance bounds, are the fastest algorithms for several fundamental problems in statistics and machine learning -- including all nearest neighbors, kernel density estimation, and Euclidean minimum spanning tree construction. We show that this overarching principle -- that by organizing points spatially, we can solve a seemingly quadratic problem in linear time -- can be generalized to problems involving interactions between sets of three or more points and can provide orders-of-magnitude speedups and guarantee runtimes that are asymptotically better than existing algorithms. We describe a family of algorithms, multi-tree algorithms, which can be viewed as generalizations of dual-tree algorithms. We support this thesis by developing and implementing multi-tree algorithms for two fundamental scientific applications: n-point correlation function estimation and Hartree-Fock theory. First, we demonstrate multi-tree algorithms for n-point correlation function estimation. The n-point correlation functions are a family of fundamental spatial statistics and are widely used for understanding large-scale astronomical surveys, characterizing the properties of new materials at the microscopic level, and for segmenting and processing images. We present three new algorithms which will reduce the dependence of the computation on the size of the data, increase the resolution in the result without additional time, and allow probabilistic estimates independent of the problem size through sampling. We provide both empirical evidence to support our claim of massive speedups and a theoretical analysis showing linear scaling in the fundamental computational task. We demonstrate the impact of a carefully optimized base case on this computation and describe our distributed, scalable, open-source implementation of our algorithms. Second, we explore multi-tree algorithms as a framework for understanding the bottleneck computation in Hartree-Fock theory, a fundamental model in computational chemistry. We analyze existing fast algorithms for this problem, and show how they fit in our multi-tree framework. We also show new multi-tree methods, demonstrate that they are competitive with existing methods, and provide the first rigorous guarantees for the runtimes of all of these methods. Our algorithms will appear as part of the PSI4 computational chemistry library.

This dissertation addresses the validation of the hypothesis there is a general sense that violence and security perception influence the use of sustainable travel modes. The research characterizes the issue of security perception among University of São Paulo (Brazil) users and identifies the way the sense of security and violence occurrences are related to the travel mode choice. An online survey on security perception and the way its participants access the campus was conducted. The target relationships were explored by Decision Tree (DT) algorithms. An initial exploratory analysis revealed occurrences of violence and reports of insecurity perception were strongly correlated on streets around the campus. The time analysis of violence distribution presented the incidents concentrated at night and during the week. The study also showed that security perception variation according to gender and travel mode choice is less sensitive to security perception than to the occurrence of violence, or type of affiliation to the university. Finally, DT algorithms explored the relation of spatially treated variables (i.e. route length to the university, density of violence occurrences and insecurity reports on the route) to mode choice. The results also showed that distance to the campus was relevant to the mode choice only in routes not strongly considered unsafe. In routes of higher insecurity perception, the share of nonmotorized modes was more expressive and the largest participation of sustainable modes was on routes with high incidence of violence. Since it is counterintuitive to assume numerous walking trips are a consequence of violence, the opposite was considered as a possible explanation to those results. The present study reinforces the need for increased surveillance in regions with high participation of non-motorized modes, for preventing users from shifting to motorized modes. / Esta dissertação busca comprovar a hipótese de que a violência e a percepção de segurança influenciam o uso de modos de transporte sustentáveis. A pesquisa caracteriza a questão da percepção de segurança entre os usuários da Universidade de São Paulo (Brasil), em São Carlos, e identifica como o sentimento de segurança pessoal e a violência estão relacionados com a escolha do modo de viagem. Foi realizada uma pesquisa on-line sobre a percepção de segurança dos usuários da universidade e a forma como eles acessam o campus. As interações foram exploradas por algoritmos de Árvore de Decisão (AD). Uma análise exploratória inicial mostrou que ocorrências de violência e relatos de insegurança estavam fortemente correlacionados nos trechos de via ao redor do campus. A análise temporal da distribuição da violência apresentou os incidentes concentrados à noite e durante os dias de semana. Além disso, a pesquisa mostrou que a percepção de segurança variou de acordo com o gênero e a escolha modal é menos sensível à percepção de segurança do que a ocorrência de violência, ou vinculação com a universidade. Por fim, os algoritmos de AD foram executados para explorar a relação das variáveis tratadas espacialmente (ou seja, o comprimento da rota até o campus, além da densidade de ocorrências e relatos de insegurança na rota) com a escolha modal. O último resultado obtido na análise foi que a distância até a universidade era relevante para a escolha modal apenas em rotas onde não há numerosos relatos de insegurança. A participação dos modos não motorizados foi mais expressiva nas rotas com maior percepção de insegurança, e em rotas com alta incidência de violência. Como não é razoável supor que mais viagens a pé são uma consequência dos roubos e sim o oposto, o estudo reforça a importância de aumentar a segurança nas regiões de alta incidência de viagens não motorizadas, de forma a não incentivar a migração destes usuários para modos motorizados.

This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”. In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees. In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees. In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution. In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.

This dissertation addresses the validation of the hypothesis there is a general sense that violence and security perception influence the use of sustainable travel modes. The research characterizes the issue of security perception among University of São Paulo (Brazil) users and identifies the way the sense of security and violence occurrences are related to the travel mode choice. An online survey on security perception and the way its participants access the campus was conducted. The target relationships were explored by Decision Tree (DT) algorithms. An initial exploratory analysis revealed occurrences of violence and reports of insecurity perception were strongly correlated on streets around the campus. The time analysis of violence distribution presented the incidents concentrated at night and during the week. The study also showed that security perception variation according to gender and travel mode choice is less sensitive to security perception than to the occurrence of violence, or type of affiliation to the university. Finally, DT algorithms explored the relation of spatially treated variables (i.e. route length to the university, density of violence occurrences and insecurity reports on the route) to mode choice. The results also showed that distance to the campus was relevant to the mode choice only in routes not strongly considered unsafe. In routes of higher insecurity perception, the share of nonmotorized modes was more expressive and the largest participation of sustainable modes was on routes with high incidence of violence. Since it is counterintuitive to assume numerous walking trips are a consequence of violence, the opposite was considered as a possible explanation to those results. The present study reinforces the need for increased surveillance in regions with high participation of non-motorized modes, for preventing users from shifting to motorized modes. / Esta dissertação busca comprovar a hipótese de que a violência e a percepção de segurança influenciam o uso de modos de transporte sustentáveis. A pesquisa caracteriza a questão da percepção de segurança entre os usuários da Universidade de São Paulo (Brasil), em São Carlos, e identifica como o sentimento de segurança pessoal e a violência estão relacionados com a escolha do modo de viagem. Foi realizada uma pesquisa on-line sobre a percepção de segurança dos usuários da universidade e a forma como eles acessam o campus. As interações foram exploradas por algoritmos de Árvore de Decisão (AD). Uma análise exploratória inicial mostrou que ocorrências de violência e relatos de insegurança estavam fortemente correlacionados nos trechos de via ao redor do campus. A análise temporal da distribuição da violência apresentou os incidentes concentrados à noite e durante os dias de semana. Além disso, a pesquisa mostrou que a percepção de segurança variou de acordo com o gênero e a escolha modal é menos sensível à percepção de segurança do que a ocorrência de violência, ou vinculação com a universidade. Por fim, os algoritmos de AD foram executados para explorar a relação das variáveis tratadas espacialmente (ou seja, o comprimento da rota até o campus, além da densidade de ocorrências e relatos de insegurança na rota) com a escolha modal. O último resultado obtido na análise foi que a distância até a universidade era relevante para a escolha modal apenas em rotas onde não há numerosos relatos de insegurança. A participação dos modos não motorizados foi mais expressiva nas rotas com maior percepção de insegurança, e em rotas com alta incidência de violência. Como não é razoável supor que mais viagens a pé são uma consequência dos roubos e sim o oposto, o estudo reforça a importância de aumentar a segurança nas regiões de alta incidência de viagens não motorizadas, de forma a não incentivar a migração destes usuários para modos motorizados.