Basis Reduction Algorithms and Subset Sum Problems

This thesis investigates a new approach to lattice basis reduction suggested by M. Seysen. Seysen's algorithm attempts to globally reduce a lattice basis, whereas the Lenstra, Lenstra, Lovasz (LLL) family of reduction algorithms concentrates on local reductions. We show that Seysen's algorithm is well suited for reducing certain classes of lattice bases, and often requires much less time in practice than the LLL algorithm. We also demonstrate how Seysen's algorithm for basis reduction may be applied to subset sum problems. Seysen's technique, used in combination with the LLL algorithm, and other heuristics, enables us to solve a much larger class of subset sum problems than was previously possible.

Higher order universal one-way hash functions from the subset sum assumption

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs. We show that the subset sum hash function is a kth order Universal One-Way Hash Function (hashing n bits to m < n bits) under the Subset Sum assumption for k = O(log m). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with ‘extension factor’ k+1, while losing (at most) about k bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to m log(k+1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

The subset sum problem in Keno modelling

Aspects of Keno modelling throughout the Australian states of Queensland, New South Wales and Victoria are discussed: the trivial Heads or Tails and the more interesting Keno Bonus, which leads to consideration of the subset sum problem. The most intricate structure is where Heads or Tails and Keno Bonus are combined, and here, the issue of independence arises. Closed expressions for expected return to player are presented in each case.

Zero-sum problems in finite cyclic groups

The purpose of this thesis is to investigate some open problems in the area of combinatorial number theory referred to as zero-sum theory. A zero-sequence in a finite cyclic group G is said to have the basic property if it is equivalent under group automorphism to one which has sum precisely IGI when this sum is viewed as an integer. This thesis investigates two major problems, the first of which is referred to as the basic pair problem. This problem seeks to determine conditions for which every zero-sequence of a given length in a finite abelian group has the basic property. We resolve an open problem regarding basic pairs in cyclic groups by demonstrating that every sequence of length four in Zp has the basic property, and we conjecture on the complete solution of this problem. The second problem is a 1988 conjecture of Kleitman and Lemke, part of which claims that every sequence of length n in Zn has a subsequence with the basic property. If one considers the special case where n is an odd integer we believe this conjecture to hold true. We verify this is the case for all prime integers less than 40, and all odd integers less than 26. In addition, we resolve the Kleitman-Lemke conjecture for general n in the negative. That is, we demonstrate a sequence in any finite abelian group isomorphic to Z2p (for p ~ 11 a prime) containing no subsequence with the basic property. These results, as well as the results found along the way, contribute to many other problems in zero-sum theory.

The 0-1 Knapsack polytope – a starting point for cryptanalysis of Knapsack ciphers?

The Knapsack Cryptosystem of Merkle and Hellman, 1978, is one of the earliest public-key cryptography schemes. The security of the method relies on the difficulty in solving Subset Sum Problems (also known as Knapsack Problems). In this paper, we first provide a brief history of knapsack-based cryptosystems and their cryptanalysis attacks. Following that, we review the advances in integer programming approaches to 0 − 1 Knapsack Problems, with a focus on the polyhedral studies of the convex hull of the integer set. Last of all, we discuss potential future research directions in applying integer programming in the cryptanalysis of knapsack ciphers.

The dynamics of a genetic algorithm under stabilizing selection

A formalism recently introduced by Prugel-Bennett and Shapiro uses the methods of statistical mechanics to model the dynamics of genetic algorithms. To be of more general interest than the test cases they consider. In this paper, the technique is applied to the subset sum problem, which is a combinatorial optimization problem with a strongly non-linear energy (fitness) function and many local minima under single spin flip dynamics. It is a problem which exhibits an interesting dynamics, reminiscent of stabilizing selection in population biology. The dynamics are solved under certain simplifying assumptions and are reduced to a set of difference equations for a small number of relevant quantities. The quantities used are the population's cumulants, which describe its shape, and the mean correlation within the population, which measures the microscopic similarity of population members. Including the mean correlation allows a better description of the population than the cumulants alone would provide and represents a new and important extension of the technique. The formalism includes finite population effects and describes problems of realistic size. The theory is shown to agree closely to simulations of a real genetic algorithm and the mean best energy is accurately predicted.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Towards a game theoretic authorisation model

Authorised users (insiders) are behind the majority of security incidents with high financial impacts. Because authorisation is the process of controlling users’ access to resources, improving authorisation techniques may mitigate the insider threat. Current approaches to authorisation suffer from the assumption that users will (can) not depart from the expected behaviour implicit in the authorisation policy. In reality however, users can and do depart from the canonical behaviour. This paper argues that the conflict of interest between insiders and authorisation mechanisms is analogous to the subset of problems formally studied in the field of game theory. It proposes a game theoretic authorisation model that can ensure users’ potential misuse of a resource is explicitly considered while making an authorisation decision. The resulting authorisation model is dynamic in the sense that its access decisions vary according to the changes in explicit factors that influence the cost of misuse for both the authorisation mechanism and the insider.

Aspects of Keno modelling

In two earlier papers, an intricate Jackpot structure and analysis of pseudo-random numbers for Keno in the Australian state of Queensland circa 2000 were described. Aspects of the work were also reported at an international conference . Since that time, many aspects of the game in Australia have changed. The present paper presents more up-to-date details of Keno throughout the states of Queensland, New South Wales and Victoria. A much simpler jackpot structure is now in place and this is described. Two add-ons or side-bets to the game are detailed: the trivial Heads or Tails and the more interesting Keno Bonus, which leads to consideration of the subset sum problem. The most intricate structure is where Heads or Tails and Keno Bonus are combined, and here, the issue of independence arises. Closed expressions for expected return to player (ERTP) are presented in all cases.

A cross-national study of calculus

The results from a cross-national study comparing calculus performance of students at East China Normal University (ECNU) in Shanghai and students at the University of Michigan before and after their first university calculus course are presented. Overall, ECNU significantly outperformed Michigan on both the pre- and post-tests, but the Michigan students showed a larger gain and normalized gain, and hence narrowed the gap. ECNU's superior performance was especially striking on the subset of problems requiring only a pre-calculus background. On those, Michigan's post-test scores were below ECNU's pre-test scores and, indeed, ECNU's higher performance on both the overall pre-test and overall post-test is attributable to its success on these problems.

Decentralized supply chain formation using max-sum loopy belief propagation

Supply chain formation is the process by which a set of producers within a network determine the subset of these producers able to form a chain to supply goods to one or more consumers at the lowest cost. This problem has been tackled in a number of ways, including auctions, negotiations, and argumentation-based approaches. In this paper we show how this problem can be cast as an optimization of a pairwise cost function. Optimizing this class of energy functions is NP-hard but efficient approximations to the global minimum can be obtained using loopy belief propagation (LBP). Here we detail a max-sum LBP-based approach to the supply chain formation problem, involving decentralized message-passing between supply chain participants. Our approach is evaluated against a well-known decentralized double-auction method and an optimal centralized technique, showing several improvements on the auction method: it obtains better solutions for most network instances which allow for competitive equilibrium (Competitive equilibrium in Walsh and Wellman is a set of producer costs which permits a Pareto optimal state in which agents in the allocation receive non-negative surplus and agents not in the allocation would acquire non-positive surplus by participating in the supply chain) while also optimally solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions. © 2012 Wiley Periodicals, Inc.

Is the sum more than the corporate entrepreneurship parts? the different effects of social capital on innovation, venturing, and renewal processes

Principal Topic Although corporate entrepreneurship is of vital importance for long-term firm survival and growth (Zahra and Covin, 1995), researchers still struggle with understanding how to manage corporate entrepreneurship activities. Corporate entrepreneurship consists of three parts: innovation, venturing, and renewal processes (Guth and Ginsberg, 1990). Innovation refers to the development of new products, venturing to the creation of new businesses, and renewal to redefining existing businesses (Sharma, and Chrisman, 1999; Verbeke et al., 2007). Although there are many studies focusing on one of these aspects (cf. Burgelman, 1985; Huff et al., 1992), it is very difficult to compare the outcomes of these studies due to differences in contexts, measures, and methodologies. This is a significant lack in our understanding of CE, as firms engage in all three aspects of CE, making it important to compare managerial and organizational antecedents of innovation, venturing and renewal processes. Because factors that may enhance venturing activities may simultaneously inhibit renewal activities. The limited studies that did empirically compare the individual dimensions (cf. Zahra, 1996; Zahra et al., 2000; Yiu and Lau, 2008; Yiu et al., 2007) generally failed to provide a systematic explanation for potential different effects of organizational antecedents on innovation, venturing, and renewal. With this study we aim to investigate the different effects of structural separation and social capital on corporate entrepreneurship activities. The access to existing and the development of new knowledge has been deemed of critical importance in CE-activities (Floyd and Wooldridge, 1999; Covin and Miles, 2007; Katila and Ahuja, 2002). Developing new knowledge can be facilitated by structurally separating corporate entrepreneurial units from mainstream units (cf. Burgelman, 1983; Hill and Rothaermel, 2003; O'Reilly and Tushman, 2004). Existing knowledge and resources are available through networks of social relationships, defined as social capital (Nahapiet and Ghoshal, 1998; Yiu and Lau, 2008). Although social capital has primarily been studied at the organizational level, it might be equally important at top management level (Belliveau et al., 1996). However, little is known about the joint effects of structural separation and integrative mechanisms to provide access to social capital on corporate entrepreneurship. Could these integrative mechanisms for example connect the separated units to facilitate both knowledge creation and sharing? Do these effects differ for innovation, venturing, and renewal processes? Are the effects different for organizational versus top management team integration mechanisms? Corporate entrepreneurship activities have for example been suggested to take place at different levels. Whereas innovation is suggested to be a more bottom-up process, strategic renewal is a more top-down process (Floyd and Lane, 2000; Volberda et al., 2001). Corporate venturing is also a more bottom-up process, but due to the greater required resource commitments relative to innovation, it ventures need to be approved by top management (Burgelman, 1983). As such we will explore the following key research question in this paper: How do social capital and structural separation on organizational and TMT level differentially influence innovation, venturing, and renewal processes? Methodology/Key Propositions We investigated our hypotheses on a final sample of 240 companies in a variety of industries in the Netherlands. All our measures were validated in previous studies. We targeted a second respondent in each firm to reduce problems with single-rater data (James et al., 1984). We separated the measurement of the independent and the dependent variables in two surveys to create a one-year time lag and reduce potential common method bias (Podsakoff et al., 2003). Results and Implications Consistent with our hypotheses, our results show that configurations of structural separation and integrative mechanisms have different effects on the three aspects of corporate entrepreneurship. Innovation was affected by organizational level mechanisms, renewal by integrative mechanisms on top management team level and venturing by mechanisms on both levels. Surprisingly, our results indicated that integrative mechanisms on top management team level had negative effects on corporate entrepreneurship activities. We believe this paper makes two significant contributions. First, we provide more insight in what the effects of ambidextrous organizational forms (i.e. combinations of differentiation and integration mechanisms) are on venturing, innovation and renewal processes. Our findings show that more valuable insights can be gained by comparing the individual parts of corporate entrepreneurship instead of focusing on the whole. Second, we deliver insights in how management can create a facilitative organizational context for these corporate entrepreneurship activities.

Validity of dietary questionnaires in Sri Lankan adults and the association of dietary intake with obesity

Traditionally, infectious diseases and under-nutrition have been considered major health problems in Sri Lanka with little attention paid to obesity and associated non-communicable diseases (NCDs). However, the recent Sri Lanka Diabetes and Cardiovascular Study (SLDCS) reported the epidemic level of obesity, diabetes and metabolic syndrome. Moreover, obesity-associated NCDs is the leading cause of death in Sri Lanka and there is an exponential increase in hospitalization due to NCDs adversely affecting the development of the country. Despite Sri Lanka having a very high prevalence of NCDs and associated mortality, little is known about the causative factors for this burden. It is widely believed that the global NCD epidemic is associated with recent lifestyle changes, especially dietary factors. In the absence of sufficient data on dietary habits in Sri Lanka, successful interventions to manage these serious health issues would not be possible. In view of the current situation the dietary survey was undertaken to assess the intakes of energy, macro-nutrients and selected other nutrients with respect to socio demographic characteristics and the nutritional status of Sri Lankan adults especially focusing on obesity. Another aim of this study was to develop and validate a culturally specific food frequency questionnaire (FFQ) to assess dietary risk factors of NCDs in Sri Lankan adults. Data were collected from a subset of the national SLDCS using a multi-stage, stratified, random sampling procedure (n=500). However, data collection in the SLDCS was affected by the prevailing civil war which resulted in no data being collected from Northern and Eastern provinces. To obtain a nationally representative sample, additional subjects (n=100) were later recruited from the two provinces using similar selection criteria. Ethical Approval for this study was obtained from the Ethical Review Committee, Faculty of Medicine, University of Colombo, Sri Lanka and informed consent was obtained from the subjects before data were collected. Dietary data were obtained using the 24-h Dietary Recall (24HDR) method. Subjects were asked to recall all foods and beverages, consumed over the previous 24-hour period. Respondents were probed for the types of foods and food preparation methods. For the FFQ validation study, a 7-day weight diet record (7-d WDR) was used as the reference method. All foods recorded in the 24 HDR were converted into grams and then intake of energy and nutrients were analysed using NutriSurvey 2007 (EBISpro, Germany) which was modified for Sri Lankan food recipes. Socio-demographic details and body weight perception were collected from interviewer-administrated questionnaire. BMI was calculated and overweight (BMI ≥23 kg.m-2), obesity (BMI ≥25 kg.m-2) and abdominal obesity (Men: WC ≥ 90 cm; Women: WC ≥ 80 cm) were categorized according to Asia-pacific anthropometric cut-offs. The SPSS v. 16 for Windows and Minitab v10 were used for statistical analysis purposes. From a total of 600 eligible subjects, 491 (81.8%) participated of whom 34.5% (n=169) were males. Subjects were well distributed among different socio-economic parameters. A total of 312 different food items were recorded and nutritionists grouped similar food items which resulted in a total of 178 items. After performing step-wise multiple regression, 93 foods explained 90% of the variance for total energy intake, carbohydrates, protein, total fat and dietary fibre. Finally, 90 food items and 12 photographs were selected. Seventy-seven subjects completed (response rate = 65%) the FFQ and 7-day WDR. Estimated mean energy intake (SD) from FFQ (1794±398 kcal) and 7DWR (1698±333 kcal, P<0.001) was significantly different due to a significant overestimation of carbohydrate (~10 g/d, P<0.001) and to some extent fat (~5 g/d, NS). Significant positive correlations were found between the FFQ and 7DWR for energy (r = 0.39), carbohydrate (r = 0.47), protein (r = 0.26), fat (r =0.17) and dietary fiber (r = 0.32). Bland-Altman graphs indicated fairly good agreement between methods with no relationship between bias and average intake of each nutrient examined. The findings from the nutrition survey showed on average, Sri Lankan adults consumed over 14 portions of starch/d; moreover, males consumed 5 more portions of cereal than females. Sri Lankan adults consumed on average 3.56 portions of added sugars/d. Moreover, mean daily intake of fruit (0.43) and vegetable (1.73) portions was well below minimum dietary recommendations (fruits 2 portions/d; vegetables 3 portions/d). The total fruit and vegetable intake was 2.16 portions/d. Daily consumption of meat or alternatives was 1.75 portions and the sum of meat and pulses was 2.78 portions/d. Starchy foods were consumed by all participants and over 88% met the minimum daily recommendations. Importantly, nearly 70% of adults exceeded the maximum daily recommendation for starch (11portions/d) and a considerable proportion consumed larger numbers of starch servings daily, particularly men. More than 12% of men consumed over 25 starch servings/d. In contrast to their starch consumption, participants reported very low intakes of other food groups. Only 11.6%, 2.1% and 3.5% of adults consumed the minimum daily recommended servings of vegetables, fruits, and fruits and vegetables combined, respectively. Six out of ten adult Sri Lankans sampled did not consume any fruits. Milk and dairy consumption was extremely low; over a third of the population did not consume any dairy products and less than 1% of adults consumed 2 portions of dairy/d. A quarter of Sri Lankans did not report consumption of meat and pulses. Regarding protein consumption, 36.2% attained the minimum Sri Lankan recommendation for protein; and significantly more men than women achieved the recommendation of ≥3 servings of meat or alternatives daily (men 42.6%, women 32.8%; P<0.05). Over 70% of energy was derived from carbohydrates (Male:72.8±6.4%, Female:73.9±6.7%), followed by fat (Male:19.9±6.1%, Female:18.5±5.7%) and proteins (Male:10.6±2.1%, Female:10.9±5.6%). The average intake of dietary fiber was 21.3 g/day and 16.3 g/day for males and females, respectively. There was a significant difference in nutritional intake related to ethnicities, areas of residence, education levels and BMI categories. Similarly, dietary diversity was significantly associated with several socio-economic parameters among Sri Lankan adults. Adults with BMI ≥25 kg.m-2 and abdominally obese Sri Lankan adults had the highest diet diversity values. Age-adjusted prevalence (95% confidence interval) of overweight, obesity, and abdominal obesity among Sri Lankan adults were 17.1% (13.8-20.7), 28.8% (24.8-33.1), and 30.8% (26.8-35.2), respectively. Men, compared with women, were less overweight, 14.2% (9.4-20.5) versus 18.5% (14.4-23.3), P = 0.03, less obese, 21.0% (14.9-27.7) versus 32.7% (27.6-38.2), P < .05; and less abdominally obese, 11.9% (7.4-17.8) versus 40.6% (35.1-46.2), P < .05. Although, prevalence of obesity has reached to epidemic level body weight misperception was common among Sri Lankan adults. Two-thirds of overweight males and 44.7% of females considered themselves as in "about right weight". Over one third of both male and female obese subjects perceived themselves as "about right weight" or "underweight". Nearly 32% of centrally obese men and women perceived that their waist circumference is about right. People who perceived overweight or very overweight (n = 154) only 63.6% tried to lose their body weight (n = 98), and quarter of adults seek advices from professionals (n = 39). A number of important conclusions can be drawn from this research project. Firstly, the newly developed FFQ is an acceptable tool for assessing the nutrient intake of Sri Lankans and will assist proper categorization of individuals by dietary exposure. Secondly, a substantial proportion of the Sri Lankan population does not consume a varied and balanced diet, which is suggestive of a close association between the nutrition-related NCDs in the country and unhealthy eating habits. Moreover, dietary diversity is positively associated with several socio-demographic characteristics and obesity among Sri Lankan adults. Lastly, although obesity is a major health issue among Sri Lankan adults, body weight misperception was common among underweight, healthy weight, overweight, and obese adults in Sri Lanka. Over 2/3 of overweight and 1/3 of obese Sri Lankan adults believe that they are in "right weight" or "under-weight" categories.

On the hardness of the sum of K mins problem

The sum of k mins protocol was proposed by Hopper and Blum as a protocol for secure human identification. The goal of the protocol is to let an unaided human securely authenticate to a remote server. The main ingredient of the protocol is the sum of k mins problem. The difficulty of solving this problem determines the security of the protocol. In this paper, we show that the sum of k mins problem is NP-Complete and W[1]-Hard. This latter notion relates to fixed parameter intractability. We also discuss the use of the sum of k mins protocol in resource-constrained devices.