Dissertations / Theses on the topic 'Expander graphs'

L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliers
Applying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs

On dit d'un sous-ensemble de NP qu'il présente une dichotomie s'il contient des problèmes qui sont soit résolubles en temps polynomial (dans Ptime), soit difficiles (NP-complets). La classe des problèmes de satisfaction de contraintes (CSP) finis est un sous-ensemble bien connu de NP qui présente une telle dichotomie. La classe de complexité NP n'a pas de dichotomie à moins que P = NP. Pour ces deux classes, il existe des logiques qui leur sont associées. -- NP est capturé par la logique Existentielle du second ordre (ESO) par le théorème de Fagin, c'est-à-dire qu'un problème est dans NP si et seulement s'il est exprimable par une formule ESO.-- CSP est un sous-ensemble de la logique de Feder et Vardi, le fragment monotone, monadique et sans inégalités de SNP, lui-même un fragment syntaxique de ESO (MMSNP); et, pour chaque formule de MMSNP, il existe un problème CSP équivalent via des réductions polynomiales.Ceci implique que la logique ESO, tout comme NP, n'a pas de dichotomie, à contraster avec le fait que MMSNP a une dichotomie tout comme CSP. L'objectif principal de cette thèse est d'étudier les propriétés de dichotomie de sous-ensembles de NP qui contiennent strictement CSP ou MMSNP.Feder et Vardi ont prouvé que si nous omettons une des trois propriétés qui définissent MMSNP, à savoir être monotone, monadique ou omettre les inégalités, alors la logique résultante n'a pas de dichotomie. Comme leurs preuves restent parfois sommaires, nous revisitons ces résultats et fournissons des preuves détaillées. Le fragment guardé et monotone de SNP (GMSNP) est une extension connue de MMSNP qui est obtenue en relâchant la restriction "monadique" de MMSNP. Nous définissons de manière similaire une nouvelle logique appelée MMSNP avec des inégalités gardées, en relâchant la restriction d'être "sans inégalités". Nous prouvons qu'elle est strictement plus expressive que MMSNP et qu'elle possède également une dichotomie.Il existe une logique MMSNP₂ qui étend MMSNP de la même manière que MSO₂ étend la logique monadique du second ordre (MSO). On sait que MMSNP₂ est un fragment de GMSNP et que ces deux classes ont toutes deux une dichotomie ou n'en ont pas. Nous revisitons ce résultat et le renforçons en prouvant que, en ce qui concerne le fait d'avoir une dichotomie, sans perte de généralité, on peut considérer seulement les problèmes MMSNP₂ sur des signatures à un élément, au lieu des problèmes GMSNP sur des signatures finies arbitraires.Nous cherchons à prouver l'existence d'une dichotomie pour les MMSNP₂ en construisant en temps polynomial, pour tout problème MMSNP₂, un problème MMSNP équivalent. Nous rencontrons quelques obstacles pour construire une telle équivalence. Cependant, si nous permettons aux formules MMSNP d'être composées d'un nombre dénombrable de conjonctions négatives, nous prouvons qu'une telle équivalence existe. De plus, la formule MMSNP infinie correspondante a la propriété d'être "régulière". Cette propriété de régularité signifie que, dans un certain sens, cette formule est essentiellement finie. Il est connu que les problèmes MMSNP réguliers peuvent être exprimés par CSP sur des modèles oméga-catégoriques. De plus, il existe une caractérisation de la dichotomie algébrique pour les CSP oméga-catégoriques qui décrivent des problèmes MMSNP. Si l'on parvient à étendre cette caractérisation algébrique sur les problèmes réguliers MMSNP, alors notre résultat fournirait une dichotomie algébrique pour MMSNP₂. (...)
A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity class NP does not have a dichotomy unless P = NP. For both of these classes there exist logics that are associated with them. -- NP is captured by Existential Second-Order (ESO) logic by Fagin's theorem, i.e., a problem is in NP if and only if it is expressible by an ESO sentence.-- CSP is a subset of Feder and Vardi's logic, Monotone Monadic Strict NP without inequalities (MMSNP), and for every MMSNP sentence there exists a P-time equivalent CSP problem. This implies that ESO does not have a dichotomy as well as NP, and that MMSNP has a dichotomy as well as CSP. The main objective of this thesis is to study subsets of NP that strictly contain CSP or MMSNP with respect to the dichotomy existence.Feder and Vardi proved that if we omit one of the three properties that define MMSNP, namely being monotone, monadic or omitting inequalities, then the resulting logic does not have a dichotomy. As their proofs remain sketchy at times, we revisit these results and provide detailed proofs. Guarded Monotone Strict NP (GMSNP) is a known extension of MMSNP that is obtained by relaxing the "monadic" restriction of MMSNP. We define similarly a new logic that is called MMSNP with Guarded inequalities, relaxing the restriction of being "without inequalities". We prove that it is strictly more expressive than MMSNP and that it also has a dichotomy.There is a logic MMSNP₂ that extends MMSNP in the same way as MSO₂ extends Monadic Second-Order (MSO) logic. It is known that MMSNP₂ is a fragment of GMSNP and that these two classes either both have a dichotomy or both have not. We revisit this result and strengthen it by proving that, with respect to having a dichotomy, without loss of generality, one can consider only MMSNP₂ problems over one-element signatures, instead of GMSNP problems over arbitrary finite signatures.We seek to prove the existence of a dichotomy for MMSNP₂ by finding, for every MMSNP₂ problem, a P-time equivalent MMSNP problem. We face some obstacles to build such an equivalence. However, if we allow MMSNP sentences to consist of countably many negated conjuncts, then we prove that such an equivalence exists. Moreover, the corresponding infinite MMSNP sentence has a property of being "regular". This regular property means that, in some sense, this sentence is still finite. It is known that regular MMSNP problems can be expressed by CSP on omega-categorical templates. Also, there is an algebraic dichotomy characterisation for omega-categorical CSPs that describe MMSNP problems. If one manages to extend this algebraic characterisation onto regular MMSNP, then our result would provide an algebraic dichotomy for MMSNP₂.Another potential way to prove the existence of a dichotomy for MMSNP₂ is to mimic the proof of Feder and Vardi for MMSNP. That is, by finding a P-time equivalent CSP problem. The most difficult part there is to reduce a given input structure to a structure of sufficiently large girth. For MMSNP and CSP, it is done using expanders, i.e., structures, where the distribution of tuples is close to a uniform distribution. We study this approach with respect to MMSNP₂ and point out the main obstacles. (...)

This thesis presents a series of algorithmic innovations in Combinatorial Compressed Sensing and Persistent Homology. The unifying strategy across these contributions is in translating structural patterns in the underlying data into specific algorithmic designs in order to achieve: better guarantees in computational complexity, the ability to operate on more complex data, highly efficient parallelisations, or any combination of these.

Le système immunitaire adaptatif est capable de produire une réponse spécifique contre presque tous le pathogènes qui agressent notre organisme. Ceci est dû aux anticorps qui sont des protéines secrétées par les cellules B. Les molécules qui provoquent cette réaction sont appelées antigènes : pendant une réponse immunitaire, les cellules B sont soumises à un processus d’apprentissage afin d’améliorer leur capacité à reconnaitre un antigène donne. Ce processus est appelé maturation d’affinité des anticorps. Nous établissons un cadre mathématique très flexible dans lequel nous définissons et étudions des modelés évolutionnaires simplifies inspirés par la maturation d’affinité des anticorps. Nous identifions les éléments constitutifs fondamentaux de ce mécanisme d’évolution extrêmement rapide et efficace : mutation, division et sélection. En commençant par une analyse rigoureuse du mécanisme de mutation dans le Chapitre 2, nous procédons à l’enrichissement progressif du modelé en ajoutant et analysant le processus de division dans le Chapitre 3 ,puis des pressions sélectives dépendantes de l’affinité dans le Chapitre 4. Notre objectif n’est pas de construire un modèle mathématique très détaillé et exhaustif de la maturation d’affinité des anticorps, mais plutôt d’enquêter sur les interactions entre mutation, division et sélection dans un contexte théorique simplifie. On cherche à comprendre comment les différents paramètres biologiques influencent la fonctionnalité du système, ainsi qu’à estimer les temps caractéristiques de l’exploration de l’espace d’états des traits des cellules B. Au-delà des motivations biologiques de la modélisation de la maturation d’affinité des anticorps, l’analyse de ce processus d’apprentissage nous a amenée à concevoir un modèle mathématique qui peut également s’appliquer à d’autres systèmes d’évolution, mais aussi à l’étude de la propagation de rumeurs ou de virus. Notre travail théorique s’accompagne de nombreuses simulations numériques qui viennent soit l’illustrer soit montrer que certains résultats demeurent extensibles a des situations plus compliquées
The adaptive immune system is able to produce a specific response against almost any pathogen that could penetrate our organism and inflict diseases. This task is assured by the production of antigen-specific antibodies secreted by B-cells. The agents which causes this reaction are called antigens: during an immune response B-cells are submitted to a learning process in order to improve their ability to recognize the immunizing antigen. This process is called antibody affinity maturation. We set a highly flexible mathematical environment in which we define and study simplified mathematical evolutionary models inspired by antibody affinity maturation. We identify the fundamental building blocks of this extremely efficient and rapid evolutionary mechanism: mutation, division and selection. Starting by a rigorous analysis of the mutational mechanism in Chapter 2, we proceed by successively enriching the model by adding and analyzing the division process in Chapter 3 and affinity-dependent selection pressures in Chapter 4. Our aim is not to build a very detailed and comprehensive mathematical model of antibody affinity maturation, but rather to investigate interactions between mutation, division and selection in a simplified theoretical context. We want to understand how the different biological parameters affect the system’s functionality, as well as estimate the typical time-scales of the exploration of the state-space of B-cell traits. Beyond the biological motivations of antibody affinity maturation modeling, the analysis of this learning process leads us to build a mathematical model which could be relevant to model other evolutionary systems, but also gossip or virus propagation. Our method is based on the complementarity between probabilistic tools and numerical simulations

In this thesis we introduce a notion of graphs approximating actions of finitely generated groups on metric and measure spaces. We systematically investigate expansion properties of said graphs and we prove that a sequence of graphs approximating a fixed action ρ forms a family of expanders if and only if ρ is expanding in measure. This enables us to rely on a number of known results to construct numerous new families of expander (and superexpander) graphs. Proceeding in our investigation, we show that the graphs approximating an action are uniformly quasi-isometric to the level sets of the associated warped cone. The existence of such a relation between approximating graphs and warped cones has twofold advantages: on the one hand it implies that warped cones arising from actions that are expanding in measure coarsely contain families of expanders, on the other hand it provides a geometric model for the approximating graphs allowing us to study the geometry of the expander thus obtained. The rest of the work is devoted to the study of the coarse geometry of warped cones (and approximating graphs). We do so in order to prove rigidity results which allow us to prove that our construction is flexible enough to produce a number of non coarsely equivalent new families of expanders. As a by-product, we also show that some of these expanders enjoy some rather peculiar geometric properties, e.g. we can construct expanders that are coarsely simply connected.

This thesis is comprised of a portfolio of musical compositions with accompanying media and a written commentary. In each of the seven compositions, the timbral palettes of musical instruments have been expanded through unconventional physical manipulation. The written commentary presents, in detail, specific examples of how this has been achieved. Alongside descriptions of the work in question, select aspects of other composers' music that approach a similar aesthetic are also referred to. In addition, the fundamental role technology has played in the creation or realisation of certain pieces is addressed. Also included are descriptions of the various customised notational systems used throughout the portfolio. It is outlined how each of these systems has been constructed in a clear and practical manner and, where possible, has incorporated elements derived from the lingua franca in order to communicate the required information as efficiently as possible to the performers.

Hemodialysis vascular access, the interface between a dialysis patient and a dialysis machine, is quite literally the lifeblood of a patient's health. Vascular access dysfunction is the leading cause of hospitalization in hemodialysis patients. The occlusive growth of neointimal hyperplasia (NH) in expanded polytetrafluoroethylene (ePTFE) ringed grafts is the primary cause of failure. To further develop a proposed thermal ultrasound treatment to reduce or prevent NH in arteriovenous vascular grafts, the acoustic properties of ePTFE were studied in water and alcohol solutions. Previous reports of ePTFE acoustic properties are critiqued. It was found that the acoustic transmission and attenuation through ePTFE, and therefore the potential for an ultrasound-based therapy for NH, are heavily dependent on the medium in which the graft is immersed, suggesting that the acoustic properties of implanted grafts will change as grafts mature in vivo. The acoustic impedance and attenuation of water-soaked ePTFE were 0.478 ± 1.43 × 10^-2 MRayl and 1.78 ± 0.111 Np/cm*MHz, respectively, while the acoustic impedance and attenuation of ePTFE in alcohol were 1.49 ± 0.149 MRayl and 0.77 ± 1.1 × 10^-2 Np/cm*MHz, respectively. The use of focused ultrasound to heat implanted ringed ePTFE grafts was numerically modeled from 1.35- and 1.443-MHz transducers for in vitro geometries. Power deposition and heating, in turn, differed by an order of magnitude between various graft acoustic properties. Graft rings were predicted to be substantial absorbing and scattering features. In vitro phantom models were constructed: one with and one without thermocouples. At 1 W of acoustic power, the maximum temperature rise was 8˚ C. The thermocouple model containing a water-soaked graft did not experience heating in the far graft wall. The MRTI model confirmed that the graft rings are an absorbing/scattering feature. Heating was not prevented in the presence of water flow through the graft. Water was not heated significantly. Overall, results suggest ultrasound exposure can be used to generate temperature rises corresponding with the potential prevention or inhibition of NH in ringed ePTFE vascular grafts. A hybrid therapeutic/diagnostic transducer design with a therapeutic semi-annular array surrounding a diagnostic linear array is presented. Compared to a solid transducer of the same dimensions, there were only marginal aberrations in the focal plane. Numerical optimization of the element drive configuration indicated that the least distorted focal plane was produced by uniform phase and magnitude at each element.

Ma thèse se situe à l'intersection de \textit {la théorie des groupes géométrique} et \textit{la théorie des groupes mesurée}. Une question majeure dans la théorie des groupes géométrique est d'étudier la classe de quasi-isométrie (QI) et la classe d'équivalence mesurée (ME) d'un groupe, respectivement. $L^p$-équivalence mesurée est une relation d'équivalence qui est définie en ajoutant des contraintes géométriques avec d'équivalence mesurée. En plus, QI est une condition géométrique. Il est une question naturelle, si deux groupes sont QI et ME, si elles sont $L^p$-ME pour certains $p>0$. Dans mon premier article, en collaboration avec R. Tessera, nous répondons négativement à cette question pour $p\geq 1$, montrant que l'extension centrale canonique d'un groupe surface de genre plus élevé ne sont pas $L^1$-ME pour le produit direct de ce groupe de surface avec $\mathbb{Z}$ (alors qu'ils sont à la fois quasi-isométrique et équivalente mesurée).Dans mon deuxième papier, j'ai observé un lien général entre la géométrie des expandeurs, defini comme une séquence des quotients finis ( l'espace de boîte) d'un groupe finiment engendré, et les propriétés mesurée theorique du groupe. Plus précisément, je l'ai prouvé que si deux <> sont quasi-isométrique, les groupes correspondants doivent être <>, une notion qui combine à la fois QI et ME. Je prouve aussi une version de ce résultat pour le plongement grossière, ce qui permet de distinguer plusieurs classe des expandeurs. Par exemple, je montre que les expandeurs associé à $SL(m, \mathbb{Z})$ ne grossièrement plongent à les expandeurs associés à $SL_n(\mathbb{Z})$ si $m>n$
My thesis lies at the intersection of \textit{geometric group theory} and \textit{measured group theory}. A major question in geometric group theory is to study the quasi-isometry (QI) class and the measure equivalence (ME) class of a group, respectively. $L^p$-measure equivalence is an equivalence relation which is defined by adding some geometric constraints with measure equivalence. Besides, quasi-isometry is a geometric condition. It is a natural question if two groups are QI and ME, whether they are $L^p$-ME for some $p>0$. In my first paper, together with R. Tessera, we answer this question negatively for $p\geq 1$, showing that the canonical central extension of a surface group of higher genus is not $L^1$-ME to the direct product of this surface group with $\mathbb{Z}$ (while they are both quasi-isometric and measure equivalent). In my second paper, I observed a general link between the geometry of expanders arising as a sequence of finite quotients (box space) of a finitely generated group, and the measured theoretic properties of the group. More precisely, I proved that if two box spaces' are quasi-isometric, then the corresponding groups must be `uniformly measure equivalent', a notion that combines both quasi-isometry and measure equivalence. I also prove a version of this result for coarse embedding, allowing to distinguish many classes of expanders. For instance, I show that the expanders associated to $SL(m,\mathbb{Z})$ do not coarsely embed inside the expanders associated to $SL_n(\mathbb{Z}$ if $m>n$

Projeto de Pós-Graduação/Dissertação apresentado à Universidade Fernando Pessoa como parte dos requisitos para obtenção do grau de Mestre em Medicina Dentária
Os procedimentos de Regeneração Óssea Guiada (ROG) visam fornecer ao paciente melhoras, a nível estético e funcional, aumentando o volume e disponibilidade óssea. Actualmente realizam-se procedimentos para aumento do rebordo ósseo com o intuito de possibilitar a colocação de implantes dentários e melhorar a sua estética. Será descrita nesta revisão bibliográfica a Regeneração Óssea Guiada (ROG) para aumento vertical do rebordo alveolar e posterior colocação de implantes, bem como a previsibilidade da técnica e as suas taxas de sucesso. Existem vários materiais disponíveis para a técnica de ROG vertical, porém as membranas de politetrafluoroetileno expandido não-reabsorvível (PTFE-e) com reforço de titânio em associação com enxerto (1:1) autógeno e mineral de osso bovino desproteinizado (DBBM) constituem, actualmente, a primeira escolha quando se pretende o aumento ósseo vertical. A ROG para aumento vertical, apresenta boas taxas de sucesso e previsibilidade, contudo necessita de um operador com experiencia pois é uma técnica de muita exigência. Esta técnica pode ser realizada prévia ou em simultâneo com a colocação dos implantes.
Guided Bone Regeneration (GBR) procedures aim to provide the patient with aesthetical and functional improvements, increasing the bone volume and availability. Currently, procedures to increase the bone ridge are undertaken with the objective of allowing the placement of dental implants and improve their aesthetical appeal. Guided Bone Regeneration (GBR) for the vertical augmentation of the alveolar ridge and consequent implant placement will be described in this bibliographical review, as well as the predictability of the technique and its success rates. There are several materials available for the vertical GBR technique, however the membranes of expanded non-resorbable polytetrafluoroethylene (PTFE-e) with titanium reinforcement in association with autogenous graft (1:1) and deproteinized bovine bone mineral (DBBM) currently represent the first choice when a vertical bone augmentation is intended. The GBR for vertical augmentation features good success rates and predictability, however it requires an experienced operator, as it is a demanding technique. This can be performed previously or simultaneously with the placement of implants.

We study the existence of expander graphs with a focus on odd and unique expanders. The main goal is to describe configurations of arguments for which there is no infinite family of expanders. The most imporant result is that for every graph there is a nonempty subset of at most half of its vertices, such that every other vertex is connected at least twice to the subset or not connected to the subset at all. It follows that certain classes of unique expanders cannot exist. On the other hand we present some configurations for which there are families of expanders. Powered by TCPDF (www.tcpdf.org)

We explore the relationships between the computational problem of recognizing expander graphs, and the problem of efficiently approximating proof length in the well-known system of \emph{resolution}. This program builds upon known connections between graph expansion and resolution lower bounds. A proof system $P$ is \emph{(quasi-)automatizable} if there is a search algorithm which finds a $P$-proof of a given formula $f$ in time (quasi)polynomial in the length of a shortest $P$-proof of $f$. It is open whether resolution is (quasi-)automatizable. We prove several conditional non-automatizability results for resolution modulo new conjectures concerning the complexity of identifying bipartite expander graphs. Our reductions use a natural family of formulas and exploit the well-known relationships between expansion and length of resolution proofs. Our hardness assumptions are unsupported; we survey known results as progress towards establishing their plausibility. The major contribution is a conditional hardness result for the quasi-automatizability of resolution.

The subject of this thesis is searching in unstructured peer-to-peer systems. Such systems have been used for a variety of different applications, including file-sharing, content distribution and video streaming. These applications have been very popular; they contribute to a large percentage of today's Internet traffic and their users typically number in the millions. By searching, we refer to the process of locating content stored by peers. Searching in unstructured peer-to-peer systems poses a challenge because of high churn: both the topology and the content stored by peers can change quickly as peers arrive and depart, while the network formed under this churn process can be arbitrary at any point in time. As a result, a search mechanism must operate without any a priori assumptions on this dynamic topology. Ideally, a search mechanism should be scalable: as, typically, peers have limited bandwidth, the traffic generated by queries should not grow significantly as the peer population increases. Moreover, a search mechanism should also be reliable: if certain content is in the system, searching should locate it with reasonable guarantees. These two goals can be conflicting, as generating more queries increases a mechanism's reliability but decreases its scalability. Hence, a fundamental question regarding searching in unstructured systems is whether a mechanism can exhibit both properties, despite the network's dynamic and arbitrary nature. In this thesis, we show this is indeed the case, by proposing a novel mechanism that is both scalable and reliable. This is shown under a mathematical model that captures the evolution of both network and content in an unstructured system, but is also verified through simulations. To the best of our knowledge, this is the first provably scalable and reliable search mechanism for unstructured peer-to-peer systems. In addition to the above problem, we also consider a hybrid peer-to-peer system, in which the peer-to-peer network co-exists with a central server. The purpose of this hybrid architecture is to reduce the server's traffic by delegating part of it to its clients ---\emph{i.e.}, the peers: a peer wishing to retrieve certain content first propagates a query over the peer-to-peer network, and downloads the content from the server only if the query fails. This hybrid architecture can be used to partially decentralize a content distribution server, a search engine, an online encyclopedia, etc. The trade-off between scalability and reliability translates, in the hybrid case, to a trade-off between the peer and the server traffic loads. We propose a search mechanism under which both loads remain bounded as the peer population grows. This is surprising, and has an important implication: one can construct hybrid peer-to-peer systems that can handle traffic generated by a large (unbounded) peer population, even when both the server and peer bandwidth capacities are limited. Again, this is proved under a model capturing the hybrid system's dynamic nature and verified through simulations. To the best of our knowledge, our work is the first to show that hybrid systems with such properties exist.

碩士
國立交通大學
應用數學系
89
The notions of expanders, magnifiers, and enlargers are first in this thesis with focus on their relationship with eigenvalues of some associated matrices including adjacency matrices. They are then further studied among strongly regular graphs by taking advantage of the explicit relations between their parameters and eigenvalues.

碩士
國立清華大學
電機工程學系
92
Currently, one of the important issues in bioinformatics is the prediction of novel genes in human genome. Genes with specifc structures are the targets for annotation in the three billions base-pairs of the human genome. Polyadenylation site, a structure at the terminus of a gene, involves a precise endonucleolytic cleavage of the pre-mRNA followed by synthesis of the polyA tail which is found at the 3' end of nearly every mature eukaryotic mRNA. The recognition of polyadenylation site is governed by at least two signals : One is 10-30 nucleotides upstream to the cleavage/polyadenylation site and named as polyA signal (PAS), a highly conserved hexamer AAUAAA (and the common variant AUUAAA). The other is 20-40 nucleotides downstream to the cleavage/polyadenylation site, the downstream element (DE) consisting of a much less well-characterized U or G-U rich sequence. In this thesis, we will provide a program for the prediction of human polyadenylation site by the detection of the PAS signal and the DE signal with dependency graphs and their expanded Bayesian networks. Then we will compare the accuracy of prediction with famous programs POLYAH and ERPIN, and show that our program performs the best results in the polyadenylation dataset of GeneBank.

碩士
國立清華大學
電機工程學系
93
The completion of Human Genome Project has triggered a wave of investigating various biological problems directly through the string of nucleotides and also its derived amino acid sequence. Therefore, the urgent need of predicting protein three-dimensional structure simply from the amino acid sequence propels us to develop a model-based method to predict the composition of the fundamental structural elements–that is, secondary structures–of any protein chain. To accomplish this goal, we first represent all the eligible secondary structure sequences as specific paths in a secondary structure trellis. Then we employ the method of dependency graphs and their expanded Bayesian networks to quantify the relationship between primary and secondary structures. Following the similar procedure as in the coding theory, we finally assign a secondary structure element to each amino acid through the use of two decoding algorithms: the Viterbi algorithm and the sum-product algorithm. The simulation results reveal that our proposed method achieves an accuracy that is indistinguishable from other existing sequence-only methods, and that a better outcome is reached when the target sequences are confined to a specific protein fold.

碩士
國立清華大學
電機工程學系
92
We have a large amount of raw genomic DNA sequence data now with the completion of the Human Genome Project (HGP). There are hundreds of programs developed to analyze these DNA sequences. Promoter is a region usually located at the 5' flanking end of a gene and encompasses the transcription start site. The promoter plays an important role in gene regulation and the detection of the promoter region could help to improve the accuracy of gene-finding. There are also several in silico approaches to predict promoter region or transcription start site, but the performance of these programs are usually unsatisfactory since the number of false positives is too high. In this thesis, we first develop a dependency graph as the basic model for the transcription start site by chi-square test and then expand this graph with a Bayesian network by allowing nucleotides in each position to appear more than once to catch their inter-dependency but avoid overfitting. In consideration of more than one signals within the promoter region, we also construct dependency graph and it's expanded Bayesian network to model TATA box. The prediction of TATA box will be integrated into the prediction of transcription start site in this thesis. The results show that our method has the best performance comparing with four most famous programs available on the Internet.

碩士
國立清華大學
電機工程學系
93
In bioinformatics, one of the challenging issue is to determine the specific structure of each gene from the 3 billion base-pairs of human DNA sequences. Polyadenylation site is a specific feature at the terminus of a gene which involves the endonucleolytic cleavage of the pre-mRNA followed by the addition of a poly(A) tail, which is found at the 3’-terminal of the majority of mRNA. Factors related to cleavage and polyadenylation have to recognize associated signals, i.e., polyadenylation signal (PAS) and downstream element(DSE). PAS is the signal appearing in 10 to 30 nucleotide upstream of the cleavage and polyadenylation site and is with a highly conserved hexamer AAUAAA and a common variant AUUAAA in pre-mRNAs. DSE is in 20 to 40 nucleotide downstream to the cleavage and polyadenylation site and consists of a much less conserved U- or GU-rich sequence. In this thesis, we will construct a stochastic grammar of 3’-terminal of human genes by establishing the dependency graphs and their expanded Bayesian networks of the features in this region. Further more we will compare the performances of this stochastic grammar and the PAS detector provided by former researchers.

Dissertação de Mestrado em Design e Multimédia apresentada à Faculdade de Ciências e Tecnologia
A ideia de sistemas no mundo do design não é recente. Com a criação dos primeiros manuais de identidade gráfica — onde os designers descrevem, até ao mais ínfimo detalhe, todas as regras e directrizes visuais para garantir as melhores práticas de uma marca — o conceito de sistemas no mundo design foi-se adensando.Nos dias de hoje, a utilização de sistemas no design é, sobretudo, focada no desenvolvimento de interfaces de produtos digitais e, foi neste quadro e contexto, que surgiram os design systems1. Um design system é uma coleção de componentes reutilizáveis que são guiados por estilos, padrões e regras. Quando utilizados em simultâneo, permitem a criação de qualquer número de layouts/apalicações, todos coerentes e consistentes entre si, oferecendo uma metodologia de pensar o design de forma sistemática. No entanto, esta forma ou metodologia é estritamente focada no design de interfaces e o estudo da optimização deste conhecimento e da sua utilização e aplicação a outras áreas como, por exemplo, o design gráfico, é ainda muito incipiente. A presente dissertação propõe-se a desenvolver um sistema de identidade gráfica para a empresa Dodoc. Para a criação deste sistema é importante desenvolver, em primeiro lugar, uma nova abordagem sobre a identidade de marca da empresa. Resumidamente o sistema encontra-se divido em duas plataformas, a plataforma de design e a plataforma de documentação e o seu desenvolvimento passou pela definição do seu propósito, por toda a criação dos elementos que o constituem e respectiva documentação. A criação e desenvolvimento do sistema de identidade da marca Dodoc irá ajudar a criar um universo gráfico coerente, garantindo que a marca se mantém forte e completa, capaz de crescer e de se maximizar sem descurar os valores e ideias partilhados pela empresa.
The idea of ​​systems in the design world is not new. With the creation of the first graphic identity manuals—in which designers compile a set of rules or visual guidelines to secure the best practises of a brand—the concept of systems in the design world has increased.Nowadays, the use of systems in design is, above all, focused on the development of digital product interfaces, and it was in this context that design systems emerged. A design system is a collection of reusable components that are guided by styles, patterns, and rules. When assembled together it is possible to build any number of layouts/applications, which are coherent and consistent with each other, offering a systemic design methodology. However, this form or methodology is strictly focused on the design of interfaces. The research for its usability and optimising it to other areas such as, graphic design, is still very incipient.This dissertation proposes to develop a graphic identity system for Dodoc company. To develop this system, it is important to firstly develop a new approach on the company’s brand identity. Starting by dividing it into two platforms, the design platform and the documentation platform, its development went through the definition of its purpose, the creation of all the elements that constitute it and respective documentation.The design and maturing of Dodoc brand system will support building a coherent graphic universe, ensuring that the brand remains strong and solid, capable of growing and maximising itself without neglecting the values ​​and ideas shared by the company.

Nesta dissertação são estudadas propriedades de uma certa família de grafos, os grafos de Ramanujan. São ainda apresentadas e exemplificadas algumas aplicações destes, nomeadamente à Teoria dos Códigos e à Criptografia. Em particular, é apresentada e demonstrada uma propriedade dos grafos regulares com base no seu espetro, propriedade extremal para a família dos grafos de Ramanujan. Existindo outras construções possíveis, esta família pode ser construída, por exemplo, tal como é feito nesta dissertação, enquanto um caso particular de uma família de grafos de Cayley. Os grafos daquela família, caracterizando-se pelo facto de possuírem uma cintura grande, possibilitam, enquanto grafos expansores, a construção de códigos LDPC com uma grande distância e a construção de funções de síntese resistentes a colisões.
In this thesis are studied the properties of a certain family of graphs, the Ramanujan graphs, and are presented and exempli ed some of their applications, namely in Code Theory and Cryptography. Particularly, is presented and proved a regular graphs property based on their spectrum, which is extreme for the Ramanujan graphs family. There are many possible constructions for this family. In this thesis, the Ramanujan graphs are constructed as Cayley graphs. The graphs on that family, because of their large girth as expander graphs, are suitable to apply in constructions of LDPC codes and collision-resistant cryptographic hash functions.
Mestrado em Matemática e Aplicações

Graph-partitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multi-commodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called Cut-Matching game framework. Finally we present the performance results of our implementation of the Leighton-Rao and the Cut-Matching game algorithms. Powered by TCPDF (www.tcpdf.org)