Applications of Linear Programming to Coding Theory

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.

Records of migration in the exoplanet configurations

When compared to our Solar System, many exoplanet systems exhibit quite unusual planet configurations; some of these are hot Jupiters, which orbit their central stars with periods of a few days, others are resonant systems composed of two or more planets with commensurable orbital periods. It has been suggested that these configurations can be the result of a migration processes originated by tidal interactions of the planets with disks and central stars. The process known as planet migration occurs due to dissipative forces which affect the planetary semi-major axes and cause the planets to move towards to, or away from, the central star. In this talk, we present possible signatures of planet migration in the distribution of the hot Jupiters and resonant exoplanet pairs. For this task, we develop a semi-analytical model to describe the evolution of the migrating planetary pair, based on the fundamental concepts of conservative and dissipative dynamics of the three-body problem. Our approach is based on an analysis of the energy and the orbital angular momentum exchange between the two-planet system and an external medium; thus no specific kind of dissipative forces needs to be invoked. We show that, under assumption that dissipation is weak and slow, the evolutionary routes of the migrating planets are traced by the stationary solutions of the conservative problem (Birkhoff, Dynamical systems, 1966). The ultimate convergence and the evolution of the system along one of these modes of motion are determined uniquely by the condition that the dissipation rate is sufficiently smaller than the roper frequencies of the system. We show that it is possible to reassemble the starting configurations and migration history of the systems on the basis of their final states, and consequently to constrain the parameters of the physical processes involved.

Teoria canonica delle perturbazioni

Ci proponiamo di introdurre i risultati principali della teoria canonica delle perturbazioni. In particolare, studiamo la riduzione generale di sistemi unidimensionali e la teoria di Birkhoff nel caso multidimensionale. Come ulteriori sviluppi, descriviamo anche il teorema KAM.

Trasformazioni che conservano la misura

Si consideri un insieme X non vuoto su cui si costruisce una sigma-algebra F, una trasformazione T dall'insieme X in se stesso F-misurabile si dice che conserva la misura se, preso un elemento della sigma-algebra, la misura della controimmagine di tale elemento è uguale a quella dell'elemento stesso. Con questa nozione si possono costruire vari esempi di applicazioni che conservano la misura, nell'elaborato si presenta la trasformazione di Gauss. Questo tipo di trasformazioni vengono utilizzate nella teoria ergodica dove ha senso considerare il sistema dinamico a tempi discreti T^j x; dove x = T^0 x è un dato iniziale, e studiare come la dinamica dipende dalla condizione iniziale x. Il Teorema Ergodico di Von Neumann afferma che dato uno spazio di Hilbert H su cui si definisce un'isometria U è possibile considerare, per ogni elemento f dello spazio di Hilbert, la media temporale di f che converge ad un elemento dell'autospazio relativo all'autovalore 1 dell'isometria. Il Teorema di Birkhoff invece asserisce che preso uno spazio X sigma-finito ed una trasformazione T non necessariamente invertibile è possibile considerare la media temporale di una funzione f sommabile, questa converge sempre ad una funzione f* misurabile e se la misura di X è finita f* è distribuita come f. In particolare, se la trasformazione T è ergodica si avrà che la media temporale e spaziale coincideranno.

Equivariant inverse spectral theory and toric orbifolds

Let O-2n be a symplectic toric orbifold with a fixed T-n-action and with a tonic Kahler metric g. In [10] we explored whether, when O is a manifold, the equivariant spectrum of the Laplace Delta(g) operator on C-infinity(O) determines O up to symplectomorphism. In the setting of tonic orbifolds we shmilicantly improve upon our previous results and show that a generic tone orbifold is determined by its equivariant spectrum, up to two possibilities. This involves developing the asymptotic expansion of the heat trace on an orbifold in the presence of an isometry. We also show that the equivariant spectrum determines whether the toric Kahler metric has constant scalar curvature. (C) 2012 Elsevier Inc. All rights reserved.

Hearing Delzant Polytopes From the Equivariant Spectrum

Let M^{2n} be a symplectic toric manifold with a fixed T^n-action and with a toric K\"ahler metric g. Abreu asked whether the spectrum of the Laplace operator $\Delta_g$ on $\mathcal{C}^\infty(M)$ determines the moment polytope of M, and hence by Delzant's theorem determines M up to symplectomorphism. We report on some progress made on an equivariant version of this conjecture. If the moment polygon of M^4 is generic and does not have too many pairs of parallel sides, the so-called equivariant spectrum of M and the spectrum of its associated real manifold M_R determine its polygon, up to translation and a small number of choices. For M of arbitrary even dimension and with integer cohomology class, the equivariant spectrum of the Laplacian acting on sections of a naturally associated line bundle determines the moment polytope of M.

A new dominance intensity method to deal with ordinal information about a DM's preferences within MAVT

Dominance measuring methods are a new approach to deal with complex decision-making problems with imprecise information. These methods are based on the computation of pairwise dominance values and exploit the information in the dominance matrix in dirent ways to derive measures of dominance intensity and rank the alternatives under consideration. In this paper we propose a new dominance measuring method to deal with ordinal information about decision-maker preferences in both weights and component utilities. It takes advantage of the centroid of the polytope delimited by ordinal information and builds triangular fuzzy numbers whose distances to the crisp value 0 constitute the basis for the de?nition of a dominance intensity measure. Monte Carlo simulation techniques have been used to compare the performance of this method with other existing approaches.

Aplicación del método de los elementos finitos a problemas de interpolación

Como es conocido, no siempre admite solución el problema de interpolación polinómica de Birkhoff. En este trabajo se presenta un método como alternativa a este tipo de problemas para la obtención de interpolantes con unas determinadas conclusiones de continuidad y en el cual el criterio de aproximación es el de minimización de un cierto funcional real utilizando el método de los elementos finitos. Se describe el método empleado, así como diversos ejemplos l-D y la extensión a problemas 2-D.

Mehrdimensionale Geometrie,

Available on demand as hard copy or computer file from Cornell University Library.

Motzkin Decomposable Sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. We have provided several characterizations of the larger class of closed convex sets, Motzkin decomposable, in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed. Another result establishes that a closed convex set is Motzkin decomposable if and only if the set of extreme points of its intersection with the linear subspace orthogonal to its lineality is bounded. We characterize the class of the extended functions whose epigraphs are Motzkin decomposable sets showing, in particular, that these functions attain their global minima when they are bounded from below. Calculus of Motzkin decomposable sets and functions is provided.

Binomial Skew Polynomial Rings, Artin-Schelter Regularity, and Binomial Solutions of the Yang-Baxter Equation

2000 Mathematics Subject Classification: Primary 81R50, 16W50, 16S36, 16S37.

Riccati Representation for Elements in H^(-1) and Its Applications

2002 Mathematics Subject Classification: 35L05, 34L15, 35D05, 35Q53

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.