Strong shift equivalence, algebraic K-theory, and isolating zero-dimensional dynamics on manifolds

We study the relations of shift equivalence and strong shift equivalence for matrices over a ring $\mathcal{R}$, and establish a connection between these relations and algebraic K-theory. We utilize this connection to obtain results in two areas where the shift and strong shift equivalence relations play an important role: the study of finite group extensions of shifts of finite type, and the Generalized Spectral Conjectures of Boyle and Handelman for nonnegative matrices over subrings of the real numbers. We show the refinement of the shift equivalence class of a matrix $A$ over a ring $\mathcal{R}$ by strong shift equivalence classes over the ring is classified by a quotient $NK_{1}(\mathcal{R}) / E(A,\mathcal{R})$ of the algebraic K-group $NK_{1}(\calR)$. We use the K-theory of non-commutative localizations to show that in certain cases the subgroup $E(A,\mathcal{R})$ must vanish, including the case $A$ is invertible over $\mathcal{R}$. We use the K-theory connection to clarify the structure of algebraic invariants for finite group extensions of shifts of finite type. In particular, we give a strong negative answer to a question of Parry, who asked whether the dynamical zeta function determines up to finitely many topological conjugacy classes the extensions by $G$ of a fixed mixing shift of finite type. We apply the K-theory connection to prove the equivalence of a strong and weak form of the Generalized Spectral Conjecture of Boyle and Handelman for primitive matrices over subrings of $\mathbb{R}$. We construct explicit matrices whose class in the algebraic K-group $NK_{1}(\mathcal{R})$ is non-zero for certain rings $\mathcal{R}$ motivated by applications. We study the possible dynamics of the restriction of a homeomorphism of a compact manifold to an isolated zero-dimensional set. We prove that for $n \ge 3$ every compact zero-dimensional system can arise as an isolated invariant set for a homeomorphism of a compact $n$-manifold. In dimension two, we provide obstructions and examples.

DESIGN, MODELING, AND FABRICATION OF MICROROBOT LEGS

This dissertation presents work done in the design, modeling, and fabrication of magnetically actuated microrobot legs. Novel fabrication processes for manufacturing multi-material compliant mechanisms have been used to fabricate effective legged robots at both the meso and micro scales, where the meso scale refers to the transition between macro and micro scales. This work discusses the development of a novel mesoscale manufacturing process, Laser Cut Elastomer Refill (LaCER), for prototyping millimeter-scale multi-material compliant mechanisms with elastomer hinges. Additionally discussed is an extension of previous work on the development of a microscale manufacturing process for fabricating micrometer-sale multi-material compliant mechanisms with elastomer hinges, with the added contribution of a method for incorporating magnetic materials for mechanism actuation using externally applied fields. As both of the fabrication processes outlined make significant use of highly compliant elastomer hinges, a fast, accurate modeling method for these hinges was desired for mechanism characterization and design. An analytical model was developed for this purpose, making use of the pseudo rigid-body (PRB) model and extending its utility to hinges with significant stretch component, such as those fabricated from elastomer materials. This model includes 3 springs with stiffnesses relating to material stiffness and hinge geometry, with additional correction factors for aspects particular to common multi-material hinge geometry. This model has been verified against a finite element analysis model (FEA), which in turn was matched to experimental data on mesoscale hinges manufactured using LaCER. These modeling methods have additionally been verified against experimental data from microscale hinges manufactured using the Si/elastomer/magnetics MEMS process. The development of several mechanisms is also discussed: including a mesoscale LaCER-fabricated hexapedal millirobot capable of walking at 2.4 body lengths per second; prototyped mesoscale LaCER-fabricated underactuated legs with asymmetrical features for improved performance; 1 centimeter cubed LaCER-fabricated magnetically-actuated hexapods which use the best-performing underactuated leg design to locomote at up to 10.6 body lengths per second; five microfabricated magnetically actuated single-hinge mechanisms; a 14-hinge, 11-link microfabricated gripper mechanism; a microfabricated robot leg mechansim demonstrated clearing a step height of 100 micrometers; and a 4 mm x 4 mm x 5 mm, 25 mg microfabricated magnetically-actuated hexapod, demonstrated walking at up to 2.25 body lengths per second.

ADVERTISEMENT ALLOCATION AND TRUST MECHANISMS DESIGN IN SOCIAL NETWORKS

Social network sites (SNS), such as Facebook, Google+ and Twitter, have attracted hundreds of millions of users daily since their appearance. Within SNS, users connect to each other, express their identity, disseminate information and form cooperation by interacting with their connected peers. The increasing popularity and ubiquity of SNS usage and the invaluable user behaviors and connections give birth to many applications and business models. We look into several important problems within the social network ecosystem. The first one is the SNS advertisement allocation problem. The other two are related to trust mechanisms design in social network setting, including local trust inference and global trust evaluation. In SNS advertising, we study the problem of advertisement allocation from the ad platform's angle, and discuss its differences with the advertising model in the search engine setting. By leveraging the connection between social networks and hyperbolic geometry, we propose to solve the problem via approximation using hyperbolic embedding and convex optimization. A hyperbolic embedding method, \hcm, is designed for the SNS ad allocation problem, and several components are introduced to realize the optimization formulation. We show the advantages of our new approach in solving the problem compared to the baseline integer programming (IP) formulation. In studying the problem of trust mechanisms in social networks, we consider the existence of distrust (i.e. negative trust) relationships, and differentiate between the concept of local trust and global trust in social network setting. In the problem of local trust inference, we propose a 2-D trust model. Based on the model, we develop a semiring-based trust inference framework. In global trust evaluation, we consider a general setting with conflicting opinions, and propose a consensus-based approach to solve the complex problem in signed trust networks.