Integer Linear Programming for Sequence Problems: A general approach to reduce the problem size

Sequence problems belong to the most challenging interdisciplinary topics of the actuality. They are ubiquitous in science and daily life and occur, for example, in form of DNA sequences encoding all information of an organism, as a text (natural or formal) or in form of a computer program. Therefore, sequence problems occur in many variations in computational biology (drug development), coding theory, data compression, quantitative and computational linguistics (e.g. machine translation). In recent years appeared some proposals to formulate sequence problems like the closest string problem (CSP) and the farthest string problem (FSP) as an Integer Linear Programming Problem (ILPP). In the present talk we present a general novel approach to reduce the size of the ILPP by grouping isomorphous columns of the string matrix together. The approach is of practical use, since the solution of sequence problems is very time consuming, in particular when the sequences are long.

Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP

The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date.

Adaptive tackling of the swinging problem for a 2 DOF crane – payload system

The control of a crane carrying its payload by an elastic string corresponds to a task in which precise, indirect control of a subsystem dynamically coupled to a directly controllable subsystem is needed. This task is interesting since the coupled degree of freedom has little damping and it is apt to keep swinging accordingly. The traditional approaches apply the input shaping technology to assist the human operator responsible for the manipulation task. In the present paper a novel adaptive approach applying fixed point transformations based iterations having local basin of attraction is proposed to simultaneously tackle the problems originating from the imprecise dynamic model available for the system to be controlled and the swinging problem, too. The most important phenomenological properties of this approach are also discussed. The control considers the 4th time-derivative of the trajectory of the payload. The operation of the proposed control is illustrated via simulation results.

Algorithmic aspects of bio-inspired string operations

We present building blocks for algorithms for the efficient reduction of square factor, i.e. direct repetitions in strings. So the basic problem is this: given a string, compute all strings that can be obtained by reducing factors of the form zz to z. Two types of algorithms are treated: an offline algorithm is one that can compute a data structure on the given string in advance before the actual search for the square begins; in contrast, online algorithms receive all input only at the time when a request is made. For offline algorithms we treat the following problem: Let u and w be two strings such that w is obtained from u by reducing a square factor zz to only z. If we further are given the suffix table of u, how can we derive the suffix table for w without computing it from scratch? As the suffix table plays a key role in online algorithms for the detection of squares in a string, this derivation can make the iterated reduction of squares more efficient. On the other hand, we also show how a suffix array, used for the offline detection of squares, can be adapted to the new string resulting from the deletion of a square. Because the deletion is a very local change, this adaption is more eficient than the computation of the new suffix array from scratch.

Subclass problem-dependent design for error-correcting output codes

A common way to model multiclass classification problems is by means of Error-Correcting Output Codes (ECOCs). Given a multiclass problem, the ECOC technique designs a code word for each class, where each position of the code identifies the membership of the class for a given binary problem. A classification decision is obtained by assigning the label of the class with the closest code. One of the main requirements of the ECOC design is that the base classifier is capable of splitting each subgroup of classes from each binary problem. However, we cannot guarantee that a linear classifier model convex regions. Furthermore, nonlinear classifiers also fail to manage some type of surfaces. In this paper, we present a novel strategy to model multiclass classification problems using subclass information in the ECOC framework. Complex problems are solved by splitting the original set of classes into subclasses and embedding the binary problems in a problem-dependent ECOC design. Experimental results show that the proposed splitting procedure yields a better performance when the class overlap or the distribution of the training objects conceal the decision boundaries for the base classifier. The results are even more significant when one has a sufficiently large training size.

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

Towards a hybrid compactification with a scalar-tensor global cosmic string

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Effect of denture fabrication and wear on closest speaking space and interocclusal distance during deglutition

Statement of problem. The accuracy of assessing maxillomandibular relationships for trial bases and dentures using phonetic and swallowing methods has not been compared to that observed with definitive prostheses. Thus, there is no evidence to prove whether measurements obtained through such methods remain the same after adaptation to dentures.Purpose. This study investigated changes in the closest speaking space, interocclusal rest space, and interocclusal distance during deglutition in edentulous patients during and after complete denture treatment.Material and methods. Eighteen edentulous subjects participated in this study and measurements were performed after 7 Intervals of time: (1) with occlusion rims and record bases following creation of the maxillomandibular relationship record, (2) with trial dentures, (3) at Insertion of definitive complete dentures, (4) 1 week, (5) 2 weeks, (6) 1 month, and (7) 3 months after insertion. Recordings of interocclusal distances were made with a mandibular kinesiograph. Closest speaking space was measured during the pronunciation of the word 'seis'. The distance between postural rest position and centric occlusion, or interocclusal rest space, was measured using a kinesiograph. Interocclusal distance during deglutition was tested by recording the closest mandibular position recorded during swallowing of 20 mL of water. Data were analyzed using repeated-measure ANOVA, followed by the Student-Newman-Keuls test (alpha=.05).Results. A significant (P <.01)reduction in the mean closest speaking space was found when it was evaluated using occlusion rims and record bases (4.6 mm) compared with other stages (3.0 to 3.4 mm). No significant differences were found in mean interocclusal rest space and interocclusal distance during deglutition among the time periods evaluated.Conclusions. The presence of occlusion rims can influence mandibular position during pronunciation of the /s/ sound. The arrangement of artificial teeth changes the closest speaking space. However, rest position and deglutition were not affected, either during denture fabrication or short-term use.

The magnetic field of a current carrying cosmic string

The magnetostatic field of an infinite rectilinear current placed in the stationary gravitational field of a rotating cosmic string is found. An interesting aspect of this problem is that although the metric is mathematically very simple, its physical meaning is not trivial. It depends only on topological parameters. So, the cosmic string vacuum space-time is locally equivalent to the Minkowski space-time, but not globally. The calculations are so simple that they can easily be shown in the classroom. © 1997 American Association of Physics Teachers.

Aspects of Integrability in Gauge/String Correspondence

In this thesis, we present our work about some generalisations of ideas, techniques and physical interpretations typical for integrable models to one of the most outstanding advances in theoretical physics of nowadays: the AdS/CFT correspondences. We have undertaken the problem of testing this conjectured duality under various points of view, but with a clear starting point - the integrability - and with a clear ambitious task in mind: to study the finite-size effects in the energy spectrum of certain string solutions on a side and in the anomalous dimensions of the gauge theory on the other. Of course, the final desire woul be the exact comparison between these two faces of the gauge/string duality. In few words, the original part of this work consists in application of well known integrability technologies, in large parte borrowed by the study of relativistic (1+1)-dimensional integrable quantum field theories, to the highly non-relativisic and much complicated case of the thoeries involved in the recent conjectures of AdS5/CFT4 and AdS4/CFT3 corrspondences. In details, exploiting the spin chain nature of the dilatation operator of N = 4 Super-Yang-Mills theory, we concentrated our attention on one of the most important sector, namely the SL(2) sector - which is also very intersting for the QCD understanding - by formulating a new type of nonlinear integral equation (NLIE) based on a previously guessed asymptotic Bethe Ansatz. The solutions of this Bethe Ansatz are characterised by the length L of the correspondent spin chain and by the number s of its excitations. A NLIE allows one, at least in principle, to make analytical and numerical calculations for arbitrary values of these parameters. The results have been rather exciting. In the important regime of high Lorentz spin, the NLIE clarifies how it reduces to a linear integral equations which governs the subleading order in s, o(s0). This also holds in the regime with L ! 1, L/ ln s finite (long operators case). This region of parameters has been particularly investigated in literature especially because of an intriguing limit into the O(6) sigma model defined on the string side. One of the most powerful methods to keep under control the finite-size spectrum of an integrable relativistic theory is the so called thermodynamic Bethe Ansatz (TBA). We proposed a highly non-trivial generalisation of this technique to the non-relativistic case of AdS5/CFT4 and made the first steps in order to determine its full spectrum - of energies for the AdS side, of anomalous dimensions for the CFT one - at any values of the coupling constant and of the size. At the leading order in the size parameter, the calculation of the finite-size corrections is much simpler and does not necessitate the TBA. It consists in deriving for a nonrelativistc case a method, invented for the first time by L¨uscher to compute the finite-size effects on the mass spectrum of relativisic theories. So, we have formulated a new version of this approach to adapt it to the case of recently found classical string solutions on AdS4 × CP3, inside the new conjecture of an AdS4/CFT3 correspondence. Our results in part confirm the string and algebraic curve calculations, in part are completely new and then could be better understood by the rapidly evolving developments of this extremely exciting research field.

Quantum Integrability in Non-Linear Sigma Models related to Gauge/String Correspondences

The Thermodynamic Bethe Ansatz analysis is carried out for the extended-CP^N class of integrable 2-dimensional Non-Linear Sigma Models related to the low energy limit of the AdS_4xCP^3 type IIA superstring theory. The principal aim of this program is to obtain further non-perturbative consistency check to the S-matrix proposed to describe the scattering processes between the fundamental excitations of the theory by analyzing the structure of the Renormalization Group flow. As a noteworthy byproduct we eventually obtain a novel class of TBA models which fits in the known classification but with several important differences. The TBA framework allows the evaluation of some exact quantities related to the conformal UV limit of the model: effective central charge, conformal dimension of the perturbing operator and field content of the underlying CFT. The knowledge of this physical quantities has led to the possibility of conjecturing a perturbed CFT realization of the integrable models in terms of coset Kac-Moody CFT. The set of numerical tools and programs developed ad hoc to solve the problem at hand is also discussed in some detail with references to the code.

Thermal inflation and the cosmological moduli problem

Ho studiato la possibilità di soluzione per il problema cosmologico dei moduli (CMP) presente a causa della compattificazione delle dimensioni extra tramite un periodo di inflazione a basse energie (Thermal Inflation). L'elaborato consta di cinque capitoli. Il primo introduce il lettore alla problematica dei moduli partendo dalla teoria Kaluza-Klein. Il secondo riguarda interamente il CMP e altri problemi cosmologici associati ai moduli. Nel terzo viene descritta la thermal inflation e le condizioni di funzionamento. Nel quarto capitolo viene preso in esame il problema di stabilizzazione dei moduli nella teoria di stringa tipo IIB: vengono descritti sia il meccanismo KKTL che il LVS. L'ultimo capitolo consiste nel calcolo della diluizione dei moduli, enunciata prima in un contesto generale e infine applicata al LVS, tramite la thermal inflation. Viene altresì presa in esame la possibilità di due epoche di thermal inflation, al fine di ottenere una diluizione più efficiente dei moduli. In LVS sono presenti due moduli, differenti per massa e vita media. Il più leggero è soggetto al CMP e si trova che, anche dopo due periodi di thermal inflation vi è ancora un numero eccessivo di tali campi, in quanto se da un lato la thermal inflation ne diliusca la densità iniziale, dall'altro ne causa una forte riproduzione, dovuta essenzialmente alle caratteristiche del modulo

Moduli stabilisation and soft supersymmetry breaking in string compactifications

In this thesis, we shall work in the framework of type IIB Calabi-Yau flux compactifications and present a detailed review of moduli stabilisation studying in particular the phenomenological implications of the LARGE-volume scenario (LVS). All the physical relevant quantities such as moduli masses and soft-terms, are computed and compared to the phenomenological constraints that today guide the research. The structure of this thesis is the following. The first chapter introduces the reader to the fundamental concepts that are essentially supersymmetry-breaking, supergravity and string moduli, which represent the basic framework of our discussion. In the second chapter we focus our attention on the subject of moduli stabilisation. Starting from the structure of the supergravity scalar potential, we point out the main features of moduli dynamics, we analyse the KKLT and LARGE-volume scenario and we compute moduli masses and couplings to photons which play an important role in the early-universe evolution since they are strictly related to the decay rate of moduli particles. The third chapter is then dedicated to the calculation of soft-terms, which arise dynamically from gravitational interactions when moduli acquire a non-zero vacuum expectation value (VeV). In the last chapter, finally, we summarize and discuss our results, underling their phenomenological aspects. Moreover, in the last section we analyse the implications of the outcomes for standard cosmology, with particular interest in the cosmological moduli problem.

Dirichlet-Neumann inverse spectral problem for a star graph of Stieltjes strings

We solve two inverse spectral problems for star graphs of Stieltjes strings with Dirichlet and Neumann boundary conditions, respectively, at a selected vertex called root. The root is either the central vertex or, in the more challenging problem, a pendant vertex of the star graph. At all other pendant vertices Dirichlet conditions are imposed; at the central vertex, at which a mass may be placed, continuity and Kirchhoff conditions are assumed. We derive conditions on two sets of real numbers to be the spectra of the above Dirichlet and Neumann problems. Our solution for the inverse problems is constructive: we establish algorithms to recover the mass distribution on the star graph (i.e. the point masses and lengths of subintervals between them) from these two spectra and from the lengths of the separate strings. If the root is a pendant vertex, the two spectra uniquely determine the parameters on the main string (i.e. the string incident to the root) if the length of the main string is known. The mass distribution on the other edges need not be unique; the reason for this is the non-uniqueness caused by the non-strict interlacing of the given data in the case when the root is the central vertex. Finally, we relate of our results to tree-patterned matrix inverse problems.