We consider the problem of finding a sparse multiple of a polynomial. Given a polynomial f ∈ F[x] of degree d over a field F, and a desired sparsity t = O(1), our goal is to determine if there exists a multiple h ∈ F[x] of f such that h has at most t non-zero terms, and if so, to find such an h. When F = Q, we give a polynomial-time algorithm in d and the size of coefficients in h. For finding binomial multiples we prove a polynomial bound on the degree of the least degree binomial multiple independent of coefficient size. When F is a finite field, we show that the problem is at least as hard as determining the multiplicative order of elements in an extension field of F (a problem thought to have complexity similar to that of factoring integers), and this lower bound is tight when t = 2.

In this thesis, motivated by modelling polymers, the topological entanglement complexity of systems of two self-avoiding polygons (2SAPs), stretched polygons and systems of self-avoiding walks (SSAWs) in a tubular sublattice of Z3 are investigated. In particular, knotting and linking probabilities are used to measure a polygonfs selfentanglement and its entanglement with other polygons respectively. For the case of 2SAPs, it is established that the homological linking probability goes to one at least as fast as 1-O(n^(-1/2)) and that the topological linking probability goes to one exponentially rapidly as n, the size of the 2SAP, goes to infinity. For the case of stretched polygons, used to model ring polymers under the influence of an external force f, it is shown that, no matter the strength or direction of the external force, the knotting probability goes to one exponentially as n, the size of the polygon, goes to infinity. Associating a two-component link to each stretched polygon, it is also proved that the topological linking probability goes to unity exponentially fast as n→∞. Furthermore, a set of entangled chains confined to a tube is modelled by a system of self- and mutually avoiding walks (SSAW). It is shown that there exists a positive number γ such that the probability that an SSAW of size n has entanglement complexity (EC), as defined in this thesis, greater than γn approaches one exponentially as n→∞. It is also established that EC of an SSAW is bounded above by a linear function of its size. Using a transfer-matrix approach, the asymptotic form of the free energy for the SSAW model is also obtained and the average edge-density for span m SSAWs is proved to approach a constant as m→∞. Hence, it is shown that EC is a ggoodh measure of entanglement complexity for dense polymer systems modelled by SSAWs, in particular, because EC increases linearly with system size, as the size of the system goes to infinity.

<p>Background: Each year, 2 million older Americans complete three to four week courses of post-acute care in nursing homes and return home; however, scant research describes services to protect older adults during their transitions from nursing homes to home. In hospital-based studies, transitional care interventions were associated with improved health outcomes for older adults, but these interventions added new staff positions, which are likely cost-prohibitive in nursing homes. Further, no prior study explored transitional care provided for vulnerable, post-acute care patients in nursing homes. Thus, this dissertation was designed to develop new understandings about transitional care provided by existing staff members in nursing homes. The study has two specific aims: (a) describe transitional care and outcomes for older adults who obtain post-acute care in nursing homes from the day of admission through discharge; (b) explore the influence of interactions, among selected older adult patients and their group of nursing home caregivers, on their ability to accomplish transitional care processes.</p><p>Method: Using data from a literature review and theoretical models, including Donabedian's Model of Healthcare Quality and Anderson's Local Interaction Model, a conceptual model of transitional care for post-acute care patients in nursing homes was constructed. The conceptual model was then used to guide exploration of the research aims with a longitudinal, multiple case study of transitional care in a nursing home. The unit of analysis was the patient care-team, defined as individual post-acute care patients, family caregivers, and 6 to 8 professional staff in each team (e.g., rehabilitation therapists, physicians, nurses and social workers). Three patient care-team members were purposively sampled for study. Moreover, longitudinal data were collected using repeated interviews and observations with patients, family caregivers, and staff; document and daily chart reviews; and surveys of patient preparedness for discharge. Manifest content analysis and thematic analysis (qualitative methods) were used to conduct within- and across-case analyses of trajectories of transitional care and to identify strengths, gaps and inconsistencies in care. </p><p>Results: Findings related to the first research aim include a description of transitional care in the study nursing home. Serious gaps and inconsistencies in transitional care exposed older, post-acute care patients to risks for complications in their transitions from the study nursing home to home: (a) systemic supports were not available to support nursing home staff who provided transitional care; further, nursing home staff and leadership were unaware that they provided transitional care; (b) care processes were not in place to prepare older adults and their caregivers to continue care at home; (c) care-team interactions often excluded family members; and (d) post-acute care patients left the nursing home without resources needed to support safe transitions in care, including transitional care plans, education to appropriately respond to acute changes in health, written materials to guide care at home, referrals for medical follow-up after discharge, and transfers of clinical information to primary care physicians. </p><p>Findings related to the second research aim include a description of local interaction strategies and the effectiveness of transitional care processes. When professional staff more consistently used local interaction strategies, specified in the model, care-team members exhibited greater capacity for connections, information exchange, and cognitive diversity. Further, when care-team interactions were of high quality and sufficient frequency, there were multiple indications of more effective transitional care, such as patient engagement in care, inclusion of patient priorities in care plans, and problem solving which included family members and diverse members of the patient care-team. Thus, local interaction strategies were essential staff behaviors needed to adapt care processes to the specific transitional care needs of individual patients.</p><p>Because transitional care is a grossly under-developed care process in nursing homes, these findings will likely have immediate implications for practice and research. Findings will provide nursing home administrators and staff with resources to develop and evaluate care in nursing homes; further, the findings will help to create targets for protocol and care process development to strengthen existing practice and address deficiencies. Findings will provide researchers with resources for studying transitional care in diverse samples of nursing homes, which should facilitate development of testable hypotheses for needed intervention studies. In addition, the local interaction strategies findings in the study may generalize to other settings of care, where interdependent staff work is required to establish connections, information networks, and to coordinate care among multiple staff members.</p> / Dissertation

<p>For at least two thousand years, voting has been used as one of the most effective ways to aggregate people's ordinal preferences. In the last 50 years, the rapid development of Computer Science has revolutionize every aspect of the world, including voting. This motivates us to study (1) <bold>conceptually, how computational thinking changes the traditional voting theory</bold>, and (2) <bold>methodologically, how to better use voting for preference/information aggregation with the help of Computer</p><p>Science</bold>.</p><p>My Ph.D. work seeks to investigate and foster the interplay between Computer Science and Voting Theory. In this thesis, I will discuss two specific research directions pursued in my Ph.D. work, one for each question asked above. The first focuses on investigating how computational thinking affects the game-theoretic aspects of voting. More precisely, I will discuss the rationale and possibility of using computational complexity to protect voting from a type of strategic behavior of the voters, called <italic>manipulation</italic>. The second studies a voting setting called <italic>Combinatorial Voting</italic>, where the set of alternative is exponentially large and has a combinatorial structure. I will focus on the design and analysis of novel voting rules for combinatorial voting that balance computational efficiency and the expressivity of the voting language, in light of some recent developments in Artificial Intelligence.</p> / Dissertation

In the last twenty years, algebraic techniques have been applied with great success to several areas in theoretical computer science. However, for many problems involving modular counting, there is a huge gap in our understanding depending on whether the modulus is prime or composite. A prime example is the problem of showing lower bounds for circuits with Mod gates in circuit complexity. Proof techniques that work well for primes break down over composites. Moreover, in some cases, the problem for composites turns out to be very different from the prime case. Making progress on these problems seems to require a better understanding of polynomials over composites. In this thesis, we address some such "prime vs. composite" problems from algorithms, complexity and combinatorics, and the surprising connections between them. We consider the complexity-theoretic problem of computing Boolean functions using polynomials modulo composites. We show that symmetric polynomials can viewed as simultaneous communication protocols. This equivalence allows us to use techniques from communication complexity and number theory to prove degree bounds. We use these to give the first tight degree bounds for a number of Boolean functions. We consider the combinatorial problem of explicit construction of Ramsey graphs. We present a simple construction of such graphs using polynomials modulo composites. This approach gives a unifying view of many known constructions,and explains why they all achieve the same bound.We show that certain approaches to this problem cannot give better bounds. Finally, we consider the algorithmic problem of interpolation for polynomials modulo composites. We present the first query-efficient algorithms for interpolation and learning under a distribution. These results rely on some new structural results about such polynomials.

Shared objects are a key component in today's large distributed systems. Linearizability is a popular consistency condition for such shared objects which gives the illusion of sequential execution of operations. The time bound of an operation is the worst-case time complexity from the operation invocation to its response. Some time bounds have been proved for certain operations on linearizable shared objects in partially synchronous systems but there are some gaps between time upper bound and lower bound for each operation. In this work, the goal is to narrow or eliminate the gaps and find optimally fast implementations. To reach this goal, we prove larger lower bounds and show smaller upper bounds (compared to 2d for all operations in previous folklore implementations) by proposing an implementation for a shared object with an arbitrary data type in distributed systems of n processes in which every message delay is bounded within [d-u, d] and the maximum skew between processes' clocks is epsilon. Considering any operation for which there exist two instances such that individually, each instance is legal but in sequence they are not, we prove a lower bound of d + min{epsilon, u, d/3}, improving from d, and show this bound is tight when epsilon < d/3 and epsilon < u. Considering any operation for which there exist k instances such that each instance separately is legal and any sequence of them is legal, but the state of the object is different after different sequences, we prove a lower bound of (1-1/k)u, improving from u/2, and show this bound is tight when k = n. A pure mutator only modifies the object but does not return anything about the object. A pure accessor does not modify the object. For a pure mutator OP1 and a pure accessor OP2, if given a set of instances of OP1, the state of the object reflects the order in which the instances occur and an instance of OP2 can detect whether an instance of OP1 occurs, we prove the sum of the time bound for OP1 and OP2 is at least d + min{epsilon, u, d/3}, improving from d. The upper bound is d + 2*epsilon from our implementation.

The Balanced Scorecard (BSC) facilitates managers to balance strategic focuses on four perspectives, on complex cause and effect relationships, and on developing more systemic aligned strategy. But some literatures showed that the BSC theory and practice had some limitations. The root of limitations is ¡§cause and effect are not closely related in time and space¡¨. And that will mislead managers to generate misperceptions of feedback information and execute wrong strategy. This research employs system dynamics as a method to overcome the limitations, and focuses on exploring the dynamic complexity of developing the BSC strategy. By two case studies, this research finds some opinions to conceptualize a theoretical framework, generate some dynamic pitfalls propositions, and summarize some dynamically aligned principles. By system dynamics method, this research builds qualitative and quantitative system dynamics models and inquires the cases¡¦ BSC strategy. And by case study method, this research follows qualitative research perspective to compare two cases and generate propositions. The conclusion, firstly, includes a conceptualized framework of ¡§improving the dynamic alignment of the balanced scorecard strategy in system dynamics¡¨, to support ¡§the theory of developing BSC with system dynamics¡¨ and enhance the long-term effectiveness of BSC strategy. Secondly, this research finds some dynamic pitfalls propositions. Lastly, this research discusses some implications on management, limitations, and future research.

To inquire into entrepreneurship, a newly-emerging and interesting subject, our research has selected Taiwan¡¦s information technology electronics components industry as research target. By gathering vast- and primary- data, and using several representative Taiwanese component manufacturers as case studies, we found the ¡¥technical-amateur¡¦ phenomenon. This paper will clearly explain the contents, contextual factors, and advantages of technical-amateur entrepreneurship. These type of entrepreneurs are so-called ¡¥technical-amateurs¡¦ because they lacked previous work experiences in the information technology industry, i.e. outsiders; they also lacked technical ability of the typical blue-collared workers and the engineers, they were previously high-level managers in the manufacturing industry. Thus technical-amateurs tend to have vast- and extended- relationship networks that can quickly transfer capitals, to form capital team and gain the assistance of venture capital to attract the technical team; they also have sharp intuition that can strategize to move toward the mainstream to maximize market benefits; they also have managerial ability that can successfully assimilate the technology team and improve production efficiency while reducing production cost. These concepts are similar to the arguments of ¡¥fitness landscape¡¦, ¡¥co-evolution¡¦, and ¡¥the establishment of shared schema¡¨. There are several important contextual factors that led to the emergence of technical-amateurs. 1) Product technology already exists, but the process technology remains to be explored; 2) Clustering of the local information technology industry, especially the existence of world-class EMS manufacturers; 3) Rapid growths of venture-capitals; 4) Mobility of technology and talents; and 5) Profitability minimization of information products. Comparing to technical entrepreneurs, technical-amateur entrepreneurs have the following advantages: 1.By occupying the advanced-guard position in the information industry, can quickly discover entrepreneurial opportunities. Outsourcing under changes in the global commodity chain and the trend toward lighter- and smaller- information products, give rise to more entrepreneurial opportunities in the component industry. Since technical-amateurs maintain close relationships with venture-capital thus can organize capital team, therefore occupying the advanced-guard position where they can quickly discover emerging opportunities. 2.Powerful Capital Reinforcements. To achieve economies of scale, newly-founded components businesses must quickly improve its productivity. But before this could happen, manufacturer must experience a learning period where budgetary deficits are unavoidable. However due to the reinforcements of the capital team, technical-amateur entrepreneurs can lead through this difficult period and into a most profitable period of significant growths.

The Design-Build delivery method has gained popularity in the construction industry in the 21st century among clients seeking singular responsibility, shorter delivery time frame and management of complex works. In this exploratory study, a model that considers the effects of project technical system on the project organisation structure has been proposed. Project technical system comprises of two dimensions: technical uncertainty and technical complexity, while integration, organisational differentiation, information processing and project size were considered as dimensions of the project organisation structure. Several hypotheses linking the relationship between technical uncertainty, technical complexity and project structure has been developed. A self-administered questionnaire was developed as the data collection instrument. Field data were collected from design-build projects in the civil and architectural construction industry in Taiwan, and analysed at the project level. The technical system-structure relationships were tested statistically mainly by multiple regression. Results indicate that various scholarly perspectives of uncertainty have a common underlying construct. Several inter-correlations among components of the technical system were identified, and interactively they affect the project organisation structure. Technical uncertainty was found to be a better predictor of information processing and internal integrative efforts than technical complexity. Less structured and flexible information processes and coordinative mechanisms were favoured under high levels of technical uncertainty and complexity. Technical complexity was found to partially predict organisational differentiation, particularly by the interacting effects of project scope and concurrency. The level of technical staffing could be explained by project scope and technical differentiation of the complexity dimension. Lastly, the results were mixed for technical complexity as a predictor of the extent to which project work is subcontracted. The findings of this study contributed to the understanding of the relationships between technical system and organisation structure in complex Design-Build projects. Various managerial implications were outlined. The model proposed in this study can be extended to include project effectiveness, which may lead to the identification of key structural arrangements that contribute to improved project performance.

This dissertation studies the antecedents and consequences of the flow experience in online retailing environments. Flow is the enjoyable and engrossing experience that people feel when acting with total involvement. A review of previous studies suggests that applying the notion of flow to understand the online consumer experience is a promising but underdeveloped field with several conceptual and methodological issues. This dissertation attempts to contribute to our understanding of flow in online shopping in three ways. First, a three-part validity study was carried out using different approaches to construct validity and involving two sets of two flow measures: the Flow State Scale (FSS, Jackson and Marsh 1996) and the Internet Flow Scale (IFS). The first study related flow to behavioral criteria in online shopping. The second conducted a traditional construct validity study in which we developed and tested a “nomological network” of relationships between flow measures and other logically-related constructs. This study also included a Multitrait-Multimethod validity study. The third was a factorial validity study of the flow construct. These studies provided evidence of construct validity for flow and suggested that the FSS had advantages over the IFS in terms of validity. Second, this dissertation tested a comprehensive model of flow that included the underlying dimensions of flow, the mediating effects of perceived challenge and skill on flow, and antecedents and consequences of flow. Consequences of flow include perceived usefulness, affective responses to the site, and intentions to revisit and purchase. Overall, results based on data collected by a controlled experiment supported our model, suggesting that flow is a second-order construct and positively related to outcome variables. Thirdly, we studied the effect of Web site complexity on flow. Perceived site complexity was found to effect flow negatively. Investigating the effects of it on inducing flow in online shopping may eventually lead us to guidelines for improving the shopping experience by designing more capable Web sites.