We investigate the geometric phase (GP) acquired by the states of a spin-1/2 nucleus which is subject to a static magnetic field. This nucleus as the carrier system of GP, is taken as coupled to a dissipative environment, so that it evolves non-unitarily. We study the effects of different characteristics of different environments on GP as nucleus evolves in time. We showed that magnetic field strength is the primary physical parameter that determines the stability of GP / its stability decreases as the magnetic field strength increases. (By decrease in stability what we mean is the increase in the time rate of change of GP.) We showed that this decrease can be very rapid, and so it could be impossible to make use of it as a quantum logic gate in quantum information theory (QIT). To see if these behaviors differ in different environments, we analyze the same system for a fixed temperature environment which is under the influence of an electromagnetic field in a squeezed state. We find that the general dependence of GP on magnetic field does not change, but this time the effects are smoother. Namely, increase in magnetic field decreases the stability of GP also for in this environment / but this decrease is slower in comparison with the former case, and furthermore it occurs gradually. As a second problem we examine the entanglement of two atoms, which can be used as a two-qubit system in QIT. The entanglement is induced by an external quantum system. Both two-level atoms are coupled to a third two-level system by dipole-dipole interaction. The two atoms are assumed to be in ordinary vacuum and the third system is taken as influenced by a certain environment. We examined different types of environments. We show that the steady-state bipartite entanglement can be achieved in case the environment is a strongly fluctuating, that is a squeezed-vacuum, while it is not possible for a thermalized environment.

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T15:27:35Z (GMT). No. of bitstreams: 1 Curi_RafaelLima_M.pdf: 1469554 bytes, checksum: 8367cf52c9256338ee2963b9a9cdf41d (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estudamos Jogos de Roteamento. Esta subclasse de jogos e uma das mais estudadas na literatura e permite modelar de forma relativamente simples vários cenários realistas. Por exemplo, tráfego de veículos em rodovias, transporte de mercadorias, redes de telefonia, redes de computadores como a Internet, etc. Analisamos as principais variantes de jogos de roteamento, destacando suas diferenças. Comparamos jogos atômicos versus jogos não-atômicos, jogos com fluxo divisível versus jogos com fluxo indivisível, jogos com demanda uniforme versus jogos com demanda genérica e jogos com redes específicas versus jogos com redes genéricas. Focamos nosso estudo na existência, unicidade e quantificação da ineficiência de equilíbrios que emergem do comportamento independente e egoísta dos jogadores. Estudamos o equilíbrio de Wardrop para jogos não-atômicos e o equilíbrio de Nash para jogos atômicos. Na literatura, notamos que a existência e unicidade de um equilíbrio dependem basicamente de três fatores: pressupostos nas funções que definem os custos dos segmentos de uma rota, tipo dos jogadores (atômicos ou não-atômicos, com demandas iguais ou diferentes) e topologia da rede. Apresentamos também os principais resultados de ineficiência obtidos para as métricas Preço da Anarquia (PoA) e Limite de Bicritério. Nos resultados que vimos, observamos que jogos não-atômicos possuem um PoA menor que o de jogos atômicos, jogos com fluxo divisível possuem um PoA menor que o de jogos com fluxo indivisível e jogos com demanda uniforme um PoA menor que o de jogos com demanda genérica / Abstract: In this work, we study Routing Games. This subclass of games is one of the most studied in the literature and allows us to model several realistic scenarios, in a relatively simple way. For instance, road traffic, freight transportation, telephone networks, computer networks like the Internet, etc. We analyze the main variants of routing games, emphasizing their differences. We compare atomic games versus nonatomic games, unsplittable flow games versus splittable flow games, unweighted games versus weighted games and specific network games versus generic network games. We focus our study on the existence, uniqueness and quantification of the inefficiency of equilibria that emerge from the independent and selfish behavior of the players. We study the Wardrop equilibrium for nonatomic games and the Nash equilibrium for atomic games. In the literature, we note that the existence and uniqueness of an equilibrium depends basically on three factors: assumptions on the functions that define the costs of the segments of a route, type of the players (atomic or nonatomic, with equal or different demands), and network topology. We present the main results of inefficiency obtained for the metrics Price of Anarchy (PoA) and Bicriteria Limit. In the results we have considered, we noticed that nonatomic games have lower PoA than the atomic ones, splittable flow games have lower PoA than the unsplittable flow ones, and unweighted games have lower PoA than the weighted ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

[pt] Nesse trabalho, propomos o problema AdInvest, que modela o processo decisiório de alocação de investimento em marketing digital do ponto de vista do anunciante. Para o problema proposto, definimos um algoritmo chamado balGreedy, e provamos suas garantias para instâncias determísticas e estocásticas do AdInvest. Os teoremas provados garantem ao nosso algoritmo resultados de pior caso relativamente próximos ao OPT, em diversos tipos de instâncias levantadas ao decorrer do trabalho. Em especial, focamos nas instâncias que modelam o efeito de saturação das audiências, que se faz presente na dinâmica de anúncios online. Como mostrado nos experimentos computacionais, o algoritmo balGreedy se mostrou consistentemente eficiente em comparação com as políticas alternativas adotadas, tanto nas instâncias que foram geradas por simulação, quanto em instâncias reais obtidas a partir de dados de um anunciante do Facebook Ads. / [en] In this work, we propose the problem AdInvest, which models the decision-making process for allocating investment in digital marketing from the advertiser perspective. For the proposed problem, we define an algorithm called balGreedy, and we prove its guarantees in deterministic and stochastic instances of the AdInvest. The proven theorems assure to our algorithm worst-case results relatively close to OPT, in several types of instances raised during the work. In particular, we focus on the instances that model the audience saturation effect, which is present in the dynamics of online advertisements. As shown in the computational experiments, the balGreedy algorithm had been consistently efficient compared to the alternative policies adopted, both in the instances generated by simulation and in real instances built from the data of a certain Facebook Ads advertiser.

No description available.

Imagine your local creamery administers a survey asking their patrons to choose their five favorite ice cream flavors. Any data collected by this survey would be an example of partially ranked data, as the set of all possible flavors is only ranked into subsets of the chosen flavors and the non-chosen flavors. If the creamery asks you to help analyze this data, what approaches could you take? One approach is to use the natural symmetries of the underlying data space to decompose any data set into smaller parts that can be more easily understood. In this work, I describe how to use permutation representations of the symmetric group to create and study efficient algorithms that yield such decompositions.

The purpose of this thesis is to show a method, that would transform given Turing machine into propagating scattered context grammar, which language contains all valid computational histories of that particular Turing machine. Afterwards this thesis deals with questions arising from existence of such algorithm, especially in regards to the current knowledge about power of propagating scattered context grammars. Practical examples and implementation of proposed algorithm is also part of this thesis.

Modern application domains such as Composite Event Recognition (CER) and real-time Analytics require the ability to dynamically refresh query results under high update rates. Traditional approaches to this problem are based either on the materialization of subresults (to avoid their recomputation) or on the recomputation of subresults (to avoid the space overhead of materialization). Both techniques have recently been shown suboptimal: instead of materializing results and subresults, one can maintain a data structure that supports efficient maintenance under updates and can quickly enumerate the full query output, as well as the changes produced under single updates. Unfortunately, these data structures have been developed only for aggregate-join queries composed of equi-joins, limiting their applicability in domains such as CER where temporal joins are commonplace. In this paper, we present a new approach for dynamically evaluating queries with multi-way θ-joins under updates that is effective in avoiding both materialization and recomputation of results, while supporting a wide range of applications. To do this we generalize Dynamic Yannakakis, an algorithm for dynamically processing acyclic equi-join queries. In tandem, and of independent interest, we generalize the notions of acyclicity and free-connexity to arbitrary θ-joins. We instantiate our framework to the case where θ-joins are only composed of equalities and inequalities (<, ≤, =, >, ≥) and experimentally compare this algorithm, called IEDyn, to state of the art CER systems as well as incremental view maintenance engines. IEDyn performs consistently better than the competitor systems with up to two orders of magnitude improvements in both time and memory consumption.

<p>    </p> <p>Irregular control-flow structures like deeply nested conditional branches are common in real-world software applications. Improving the performance and efficiency of such programs is often challenging because it is difficult to analyze and optimize programs with irregular control flow. We observe that real-world programs contain similar or identical computations within different code paths of the conditional branches. Compilers can merge similar code to improve performance or code size. However, existing compiler optimizations like code hoisting/sinking, and tail merging do not fully exploit this opportunity. We propose a new technique called Control-Flow Melding (CFM) that can merge similar code sequences at the control-flow region level. We evaluate CFM in two applications. First, we show that CFM reduces the control divergence in GPU programs and improves the performance. Second, we apply CFM to CPU programs and show its effectiveness in reducing code size without sacrificing performance. In the next part of this dissertation, we investigate how CFM can be extended to improve dynamic test generation techniques like Dynamic Symbolic Execution (DSE). DSE suffers from path explosion problem when many conditional branches are present in the program. We propose a non-semantics-preserving branch elimination transformation called CFM-SE that reduces the number of symbolic branches in a program. We also provide a framework for detecting and reasoning about false positive bugs that might be added to the program by non-semantics-preserving transformations like CFM-SE. Furthermore, we evaluate CFM-SE on real-world applications and show its effectiveness in improving DSE performance and code coverage. </p>

We demonstrate TimeTravel, an efficient DBMS system for seamless integrated querying of past and (forecasted) future values of time series, allowing the user to view past and future values as one joint time series. This functionality is important for advanced application domain like energy. The main idea is to compactly represent time series as models. By using models, the TimeTravel system answers queries approximately on past and future data with error guarantees (absolute error and confidence) one order of magnitude faster than when accessing the time series directly. In addition, it efficiently supports exact historical queries by only accessing relevant portions of the time series. This is unlike existing approaches, which access the entire time series to exactly answer the query. To realize this system, we propose a novel hierarchical model index structure. As real-world time series usually exhibits seasonal behavior, models in this index incorporate seasonality. To construct a hierarchical model index, the user specifies seasonality period, error guarantees levels, and a statistical forecast method. As time proceeds, the system incrementally updates the index and utilizes it to answer approximate and exact queries. TimeTravel is implemented into PostgreSQL, thus achieving complete user transparency at the query level. In the demo, we show the easy building of a hierarchical model index for a real-world time series and the effect of varying the error guarantees on the speed up of approximate and exact queries.