Lossy channel systems were originally introduced to model communication protocols. It gave birth to a complexity class wich remained scarcely undersood for a long time. In this thesis we study some of the most important gaps. In particular, we bring matching upper and lower bounds for the time complexity. Then we describe a new proof tool : the Post Embedding Problem (PEP) which is a simple problem, closely related to the Post Correspondence Problem, and complete for this complexity class. Finally, we study PEP, its variants and the languages of solutions of PEP on which we provide complexity results and proof tools like pumping lemmas.

Image and video quality evaluation is very important. In applications involving signal transmission, the Reduced- or No-Reference quality metrics are generally more practical than the Full-Reference metrics. Digital watermarking based quality evaluation emerges as a potential Reduced- or No-Reference quality metric, which estimates signal quality by assessing the degradation of the embedded watermark. Since the watermark contains a small amount of information compared to the cover signal, performing accurate signal quality evaluation is a challenging task. Meanwhile, the watermarking process causes signal quality loss. To address these problems, in this thesis, a framework for image and video quality evaluation is proposed based on semi-fragile and adaptive watermarking. In this framework, adaptive watermark embedding strength is assigned by examining the signal quality degradation characteristics. The "Ideal Mapping Curve" is experimentally generated to relate watermark degradation to signal degradation so that the watermark degradation can be used to estimate the quality of distorted signals. With the proposed framework, a quantization based scheme is first implemented in DWT domain. In this scheme, the adaptive watermark embedding strengths are optimized by iteratively testing the image degradation characteristics under JPEG compression. This iterative process provides high accuracy for quality evaluation. However, it results in relatively high computational complexity. As an improvement, a tree structure based scheme is proposed to assign adaptive watermark embedding strengths by pre-estimating the signal degradation characteristics, which greatly improves the computational efficiency. The SPIHT tree structure and HVS masking are used to guide the watermark embedding, which greatly reduces the signal quality loss caused by watermark embedding. Experimental results show that the tree structure based scheme can evaluate image and video quality with high accuracy in terms of PSNR, wPSNR, JND, SSIM and VIF under JPEG compression, JPEG2000 compression, Gaussian low-pass filtering, Gaussian noise distortion, H.264 compression and packet loss related distortion.

Although theoretically practical algorithms for torus embedding exist, they have not yet been successfully implemented and their complexity may be prohibitive to their practicality. We describe a simple exponential algorithm for embedding graphs on the torus (a surface shaped like a doughnut) and discuss how it was inspired by the quadratic time planar embedding algorithm of Demoucron, Malgrange and Pertuiset. We show that it is faster in practice than the only fully implemented alternative (also exponential) and explain how both the algorithm itself and the knowledge gained during its development might be used to solve the well-studied problem of finding the complete set of torus obstructions.

During the last years we have seen the birth of free-electron lasers, a new type of light source ten billion times brighter than syncrotrons and able to produce pulses only a few femtoseconds long. One of the main motivations for building these multi-million dollar machines was the prospect of imaging biological samples such as proteins and viruses in 3D without the need for crystallization or staining. This thesis contains some of the first biological results from free-electron lasers. These results include 2D images, both of whole cells and of the giant mimivirus and also con- tains a 3D density map of the mimivirus assembled from diffraction patterns from many virus particles. These are important proof-of-concept experiments but they also mark the point where free-electron lasers start to produce biologically relevant results. The most noteworthy of these results is the unexpectedly non-uniform density distribution of the internals of the mimivirus. We also present Hawk, the only open-source software toolkit for analysing single particle diffraction data. The Uppsala-developed program suite supports a wide range fo algorithms and takes advantage of Graphics Processing Units which makes it very computationally efficient. Last, the problem introduced by structural variability in samples is discussed. This includes a description of the problem and how it can be overcome, and also how it could be turned into an advantage that allows us to image samples in all of their conformational states.

Although theoretically practical algorithms for torus embedding exist, they have not yet been successfully implemented and their complexity may be prohibitive to their practicality. We describe a simple exponential algorithm for embedding graphs on the torus (a surface shaped like a doughnut) and discuss how it was inspired by the quadratic time planar embedding algorithm of Demoucron, Malgrange and Pertuiset. We show that it is faster in practice than the only fully implemented alternative (also exponential) and explain how both the algorithm itself and the knowledge gained during its development might be used to solve the well-studied problem of finding the complete set of torus obstructions.

No description available.

O atual sucesso da Internet vem inibindo a disseminação de novas arquiteturas e protocolos de rede. Especificamente, qualquer modificação no núcleo da rede requer comum acordo entre diversas partes. Face a isso, a Virtualização de Redes vem sendo proposta como um atributo diversificador para a Internet. Tal paradigma promove o desenvolvimento de novas arquiteturas e protocolos por meio da criação de múltiplas redes virtuais sobrepostas em um mesmo substrato físico. Adicionalmente, aplicações executando sobre uma mesma rede física podem ser isoladas mutuamente, propiciando a independência funcional entre as mesmas. Uma de suas mais promissoras vantagens é a capacidade de limitar o escopo de ataques, através da organização de uma infraestrutura em múltiplas redes virtuais, isolando o tráfego das mesmas e impedindo interferências. Contudo, roteadores e enlaces virtuais permanecem vulneráveis a ataques e falhas na rede física subjacente. Particularmente, caso determinado enlace do substrato seja comprometido, todos os enlaces virtuais sobrepostos (ou seja, alocados neste) serão afetados. Para lidar com esse problema, a literatura propõe dois tipos de estratégias: as que reservam recursos adicionais do substrato como sobressalentes, protegendo contra disrupções; e as que utilizam migração em tempo real para realocar recursos virtuais comprometidos. Ambas estratégias acarretam compromissos: o uso de recursos sobressalentes tende a tornar-se custoso ao provedor de infraestrutura, enquanto a migração de recursos demanda um período de convergência e pode deixar as redes virtuais inoperantes durante o mesmo. Esta dissertação apresenta ORE (Opportunistic Resilience Embedding – Mapeamento com Resiliência Oportunística), uma nova abordagem de mapeamento de redes para proteger enlaces virtuais contra disrupções no substrato físico. ORE é composto por duas estratégias: uma proativa, na qual enlaces virtuais são alocados em múltiplos caminhos para mitigar o impacto de uma disrupção; e uma reativa, a qual tenta recuperar, parcial ou integralmente, a capacidade perdida nos enlaces virtuais afetados. Ambas são modeladas como problemas de otimização. Ademais, como o mapeamento de redes virtuais é NP-Difícil, ORE faz uso de uma meta-heurística baseada em Simulated Annealing para resolver o problema de forma eficiente. Resultados numéricos mostram que ORE pode prover resiliência a disrupções por um custo mais baixo. / Recently, the Internet’s success has prevented the dissemination of novel networking architectures and protocols. Specifically, any modification to the core of the network requires agreement among many different parties. To address this situation, Network Virtualization has been proposed as a diversifying attribute for the Internet. This paradigm promotes the development of new architectures and protocols by enabling the creation of multiple virtual networks on top of a same physical substrate. In addition, applications running over the same physical network can be isolated from each other, thus allowing them to coexist independently. One of the main advantages of this paradigm is the use of isolation to limit the scope of attacks. This can be achieved by creating different, isolated virtual networks for each task, so traffic from one virtual network does not interfere with the others. However, routers and links are still vulnerable to attacks and failures on the underlying network. Particularly, should a physical link be compromised, all embedded virtual links will be affected. Previous work tackled this problem with two main strategies: using backup resources to protect against disruptions; or live migration to relocate a compromised virtual resource. Both strategies have drawbacks: backup resources tend to be expensive for the infrastructure provider, while live migration may leave virtual networks inoperable during the recovery period. This dissertation presents ORE (Opportunistic Resilience Embedding), a novel embedding approach for protecting virtual links against substrate network disruptions. ORE’s design is two-folded: while a proactive strategy embeds virtual links into multiple substrate paths in order to mitigate the initial impact of a disruption, a reactive one attempts to recover any capacity affected by an underlying disruption. Both strategies are modeled as optimization problems. Additionally, since the embedding problem is NP-Hard, ORE uses a Simulated Annealing-based meta-heuristic to solve it efficiently. Numerical results show that ORE can provide resilience to disruptions at a lower cost.

Internet offre une énorme quantité d’informations à portée de main et dans une telle variété de sujets, que tout le monde est en mesure d’accéder à une énorme variété de connaissances. Une telle grande quantité d’information pourrait apporter un saut en avant dans de nombreux domaines (moteurs de recherche, réponses aux questions, tâches NLP liées) si elle est bien utilisée. De cette façon, un enjeu crucial de la communauté d’intelligence artificielle a été de recueillir, d’organiser et de faire un usage intelligent de cette quantité croissante de connaissances disponibles. Heureusement, depuis un certain temps déjà des efforts importants ont été faits dans la collecte et l’organisation des connaissances, et beaucoup d’informations structurées peuvent être trouvées dans des dépôts appelés Bases des Connaissances (BCs). Freebase, Entity Graph Facebook ou Knowledge Graph de Google sont de bons exemples de BCs. Un grand problème des BCs c’est qu’ils sont loin d’êtres complets. Par exemple, dans Freebase seulement environ 30% des gens ont des informations sur leur nationalité. Cette thèse présente plusieurs méthodes pour ajouter de nouveaux liens entre les entités existantes de la BC basée sur l’apprentissage des représentations qui optimisent une fonction d’énergie définie. Ces modèles peuvent également être utilisés pour attribuer des probabilités à triples extraites du Web. On propose également une nouvelle application pour faire usage de cette information structurée pour générer des informations non structurées (spécifiquement des questions en langage naturel). On pense par rapport à ce problème comme un modèle de traduction automatique, où on n’a pas de langage correct comme entrée, mais un langage structuré. Nous adaptons le RNN codeur-décodeur à ces paramètres pour rendre possible cette traduction. / Internet provides a huge amount of information at hand in such a variety of topics, that now everyone is able to access to any kind of knowledge. Such a big quantity of information could bring a leap forward in many areas if used properly. This way, a crucial challenge of the Artificial Intelligence community has been to gather, organize and make intelligent use of this growing amount of available knowledge. Fortunately, important efforts have been made in gathering and organizing knowledge for some time now, and a lot of structured information can be found in repositories called Knowledge Bases (KBs). A main issue with KBs is that they are far from being complete. This thesis proposes several methods to add new links between the existing entities of the KB based on the learning of representations that optimize some defined energy function. We also propose a novel application to make use of this structured information to generate questions in natural language.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-03-17T12:24:22Z No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-04-24T13:10:09Z (GMT) No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-04-24T13:10:17Z (GMT) No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) / Made available in DSpace on 2017-04-24T13:13:58Z (GMT). No. of bitstreams: 1 DissCOSF.pdf: 3751345 bytes, checksum: 50050f093a497de77a404a0a957ad02c (MD5) Previous issue date: 2016-11-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The expansion of different areas of knowledge through many types of information brought the necessity to support complex data (images, sounds, videos, strings, DNA chains, etc.), that do not have a Total Order Relationship and need other management mechanisms, like the contentbased retrieval. In general, they are represented in metric space domains, where we have only the elements and the distances between them. Through the characteristics extracted from them, we perform the similarity search. Considering the necessity to associate temporal information on these data in many applications, this work aims to analyze the temporal evolve of metric data. One alternative for this is embedding them into a multidimensional space to allow trajectories estimates. We studied different methods of embedding and analyzed how this affected the data’s distribution and, consequently, the estimates. Two new methods were purposed to estimate an element’s status on a different time from that available in database, in order to reduce the number of non-relevant elements on search results. These methods are based on radius search reduction (range) and evaluation of retrieved element’s proximity by using an approximation of reverse k- NN. We performed experiments which showed that purposed methods could improve the estimate’s result, that used to be performed only using k-NN searches. / A expansão de diferentes áreas do conhecimento com os diversos tipos de informação tornou necessário o suporte a dados complexos (imagens, sons, vídeos, cadeias de DNA, entre outros), que por não possuírem uma Relação de Ordem Total (ROT), necessitam de outros mecanismos de gerenciamento, como a recuperação por conteúdo. Em geral, esses dados são representados em domínios de espaços métricos, onde apenas se tem os elementos e as distâncias entre eles. Através das características extraídas dos mesmos, realiza-se consultas por similaridade. Considerando a necessidade de associar a informação temporal a esses dados em muitas aplicações, este trabalho visa analisar a evolução temporal dos dados métricos. Para isso, uma alternativa é mapeá-los para um espaço multidimensional, a fim possibilitar a estimativa de trajetórias. Neste trabalho, foram estudados diferentes métodos de mapeamento, sendo também analisado como o mapeamento afetou a distribuição dos mesmos e, por conseguinte, a realização das estimativas. Foram propostos dois novos métodos para estimar o estado de um elemento em um tempo diferente daqueles disponíveis na base de dados, com o objetivo de reduzir no conjunto resposta a quantidade de elementos não relevantes. Os métodos propostos são baseados na redução do raio de consulta na região estimada pela delimitação do raio de consulta (range) e a avaliação da proximidade dos elementos retornados utilizando verificação (aproximação) do k-NN reverso. Foram realizados experimentos que mostraram que os métodos propostos melhoraram o resultado final das estimativas, que anteriormente eram realizadas apenas com consultas aos vizinhos mais próximos.

Submitted by Diego Sa de Lima null (diegos.lima88@hotmail.com) on 2018-03-03T04:54:32Z No. of bitstreams: 1 Dissertacao_Teorias_duais_massivas_spin32.pdf: 569707 bytes, checksum: 2062a40c0ffdddb4c5801a33f1f13f9d (MD5) / Approved for entry into archive by Pamella Benevides Gonçalves null (pamella@feg.unesp.br) on 2018-03-05T18:32:28Z (GMT) No. of bitstreams: 1 lima_ds_me_guara.pdf: 569707 bytes, checksum: 2062a40c0ffdddb4c5801a33f1f13f9d (MD5) / Made available in DSpace on 2018-03-05T18:32:28Z (GMT). No. of bitstreams: 1 lima_ds_me_guara.pdf: 569707 bytes, checksum: 2062a40c0ffdddb4c5801a33f1f13f9d (MD5) Previous issue date: 2018-02-05 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Nesta dissertação serão analisados os dois modelos conhecidos na literatura que descrevem partículas massivas de spin 3/2 em D=2+1 dimensões. Essa análise será feita, assim como nos trabalhos relacionados aos bósons (spin 1, spin 2 e spin 3), via procedimento de Imersão de Calibre de Noether (ICN), Solda generalizada, análise de vínculos e condições de Fierz-Pauli. Através de argumentos de simetria, via ICN, apresentaremos uma forma de relacionar os dois modelos e mostraremos que é possível construir um novo modelo de terceira ordem em derivadas. Apresentaremos um modelo de dubleto de segunda ordem em derivadas de onde é possível obter os demais modelos auto-duais da teoria. A partir da aplicação da ICN no modelo de dubleto construiremos um novo modelo, de quarta ordem em derivadas, análogo a versão linearizada da chamada " New Massive Gravity". / In this master's thesis we will analyze the two known models in the literature wich describe massive spin 3/2 particles in D = 2 + 1 dimensions. This analysis will be done, as was previously done on works related to the bosons (spin- 1 , spin- 2 and spin- 3 ), via Noether gauge embedment (NGE) procedure, generalized soldering, hamiltonian constraints analysis and Fierz-Pauli conditions. Through symmetry arguments, by NGE, we will present a way of relating the two models and show that it is possible to construct a new model in third order derivatives. We will show a second order derivative doublet-model whence it is possible to obtain the other self-dual models of the theory. From the application of NGE in the dublet model we will construct a new model, wich has a fourth-order derivative term, analogue to the linearized version of the so-called "New Massive Gravity"