Browsing by Subject "Computational complexity"
Now showing 1 - 6 of 6
Results Per Page
Sort Options
Item Efficient evolution of neural networks through complexification(2004) Stanley, Kenneth Owen; Miikkulainen, RistoItem Lower bound methods for multiparty communication complexity(2006) Ford, Jeffrey Stephen; Gál, A. (Anna)Item On indexing large databases for advanced data models(2001-08) Samoladas, Vasilis; Miranker, Daniel P.Item Static analysis of fundamental computer science student programs(Texas Tech University, 1998-05) Ulans, Joseph V.;While there has been substantial work focused on dynamic metrics, much less work has been done with static metrics. This investigation explores the relationship between the values for a set of metrics collected from C++ programs done by students enrolled in an introductory programming course at Texas Tech University. Three groups of programs prepared in response to three programming assignments were evaluated. A variety of static metrics commonly used to assess style and complexity were used. In addition to those, the code coverage of sample input was measured dynamically. A readily available commercial software package was used to calculate the metric values. The values were then analyzed using linear regression to evaluate the extent of correlation between them. While some metrics showed no meaningful correlation, a strong correlation was observed between each of the number of statements, number of operators, number of operands, and the McCabe cyclomatic complexity value.Item Structure of a firm's knowledge base and the effectiveness of technological search(2004) Yayavaram, Sai Krishna; Fredrickson, James W.; Ahuja, GautamThis dissertation examines the impact of coupling that exists between the knowledge elements of a firm (i.e., the structure of the firm’s knowledge base) on the firm’s technological search activity. I define coupling as the decision made on how the search across two knowledge elements should be combined and distinguish it from interdependence, which is the inherent relationship between these two elements. I ask two questions: 1) How does the structure of a firm’s knowledge base impact the usefulness of a firm’s inventions? 2) How does the prior structure of a firm’s knowledge base affect the malleability of the knowledge base? Malleability is defined as the capacity for adaptive change. Inventions are generated when existing knowledge elements are combined in novel ways. Given the large number of potential combinations of knowledge elements, the problem of searching for technological inventions is computationally intractable. I use the NK model to study this computationally complex problem and argue that the structure of a knowledge base can mitigate the negative effects of complexity. In the first part of the dissertation, I show through computer simulations that a structure that is nearly decomposable (i.e. high coupling within a cluster of elements along with low coupling across clusters) increases the effectiveness of search on an NK landscape. In the second part of the dissertation, I test the relationship between near decomposability in the structure of a knowledge base and technology search in the context of the worldwide semiconductor industry. I find support for the hypothesis that a nearly decomposable structure improves the search for technological inventions. Further, I also find support for the hypothesis that firms with a nearly decomposable structure are likely to undergo a larger change in their knowledge base over time.Item Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation(2006) Trifonov, Vladimir Traianov; Gál, A. (Anna)The subject of computational complexity theory is to analyze the difficulty of solving computational problems within different models of computation. Proving lower bounds is easier in less powerful models and proving upper bounds is easier in the more powerful models. This dissertation studies techniques for analyzing the power of models of computation which are at the frontier of currently existing methods. First, we study the power of certain classes of depth-three circuits. The power of such circuits is largely not understood and studying them under further restrictions has received a lot of attention. We prove exponential lower bounds on the size of certain depth-three circuits computing parity. Our approach is based on relating the lower bounds to correlation between parity and modular polynomials, and expressing the correlation with exponential sums. We show a new expression for the exponential sum which involves a certain affine space corresponding to the polynomial. This technique gives a unified treatment and generalization of bounds which include the results of Goldmann on linear polynomials and Cai, Green, and Thierauf on symmetric polynomials. We obtain bounds on the exponential sums for lasses of polynomials of large degree and with a large number of terms, which previous techniques did not apply to. Second, we study the space complexity of undirected st- connectivity. We prove an O(log n log log n) upper bound on the space complexity of undirected st-connectivity. This improves the previous O(log4=3 n) bound due to Armoni et al. and is a big step towards the conjectured optimal O(log n) bound. Independently of our work and using different techniques recently Reingold proved the optimal bound. Interest in this question comes from the fact that undirected st-connectivity is complete for SL, a class of problems between L and NL. It has been noticed that questions in the space context tend to be easier to answer than the corresponding questions in the time context. Since understanding the power of non-determinism over determinism presents a major challenge to complexity theory, studying complexity lasses between L and NL, which are the smallest natural classes capturing deterministic and non-deterministic space-bounded computation, is important.