Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

Proof Methods for Corecursive Programs

Recursion is a well-known and powerful programming technique, with a wide variety of applications. The dual technique of corecursion is less well-known, but is increasingly proving to be just as useful. This article is a tutorial on the four main methods for proving properties of corecursive programs: fixpoint induction, the approximation (or take) lemma, coinduction, and fusion.

Sanojen jaksot ja reunattomat tekijät. Ehrenfeuchtin—Silbergerin ongelma.

Ehrenfeuchtin–Silbergerin ongelma kysyy, kuinka pitkä sana voi olla sen pisimpien reunattomien tekijöiden pituuden suhteen, ennen kuin sillä on sen lyhimmän jakson pituinen reunaton tekijä. Ongelman ratkaisu on sanan pisimpien reunattomien tekijöiden pituudesta riippuva raja, jolle kaikilla ainakin tämän pituisilla sanoilla on välttämättä lyhimmän jakson pituinen reunaton tekijä. Tutkielmassa esitellään tämän ongelman paras tunnettu ratkaisu. Lisäksi tarkastellaan muita ongelmaan läheisesti liittyviä tuloksia. Päälauseena todistetaan paras tunnettu raja pisimpien reunattomien tekijöiden suhteen. Todistus on peräisin Štěpán Holubin ja Dirk Nowotkan artikkelista The Ehrenfeucht–Silberger problem (Journal of Combinatorial Theory, Series A) sekä tämän artikkelin alustavasta versiosta ICALP 2009 -konferenssin proceedings-julkaisussa. Esitetty ratkaisu näytetään vakiotermiä vaille optimaaliseksi vertaamalla sitä parhaaseen tunnettuun esimerkkiin äärettömästä sanajoukosta, jonka jokaisen sanan pisimmät reunattomat tekijät ovat lyhyempiä kuin lyhin jakso ja jonka jokaisen sanan pituus pisimpien reunattomien tekijöiden pituuden suhteen on suurin tunnettu. Johdatteluna esitellään perustuloksia sanan jaksoista ja reunattomista tekijöistä sekä esitellään eräitä muita ehtoja sille, milloin sanalla on sen lyhimmän jakson pituinen reunaton tekijä. Toisaalta tarkastellaan myös ongelmaa, joka kysyy vastaavaa rajaa lyhimmän jakson suhteen. Uutena tuloksena parannetaan parasta aiemmin tunnettua rajaa yhtä pienemmäksi, jolloin saatu raja on optimaalinen. Lisäksi todistetaan, mitä muotoa ovat kaikki sanat, joilla ei ole lyhimmän jaksonsa pituista reunatonta tekijää ja jotka ovat lyhimmän jaksonsa suhteen mahdollisimman pitkiä. Lisäksi tarkastellaan kriittistä tekijöihinjakoa, joka liittää sanan lyhimmän jakson sen paikallisiin jaksoihin. Kriittisen tekijöihinjaon lauseesta esitetään eräs todistus. Tämän lisäksi todistetaan päälauseen todistuksessa tarvittava lemma, joka liittyy sanan konjugaatin tekijöihinjaon kriittisyyteen.

Proof methods for structured corecursive programs

Corecursive programs produce values of greatest fixpoint types, in contrast to recursive programs, which consume values of least fixpoint types. There are a number of widely used methods for proving properties of corecursive programs, including fixpoint induction, the take lemma, and coinduction. However, these methods are all rather low level, in that they do not exploit the common structure that is often present in corecursive definitions. We argue for a more structured approach to proving properties of corecursive programs. In particular, we show that by writing corecursive programs using a simple operator that encapsulates a common pattern of corecursive definition, we can then use high-level algebraic properties of this operator to conduct proofs in a purely calculational style that avoids the use of inductive or coinductive methods.

Sanojen jaksot ja reunattomat tekijät. Ehrenfeuchtin—Silbergerin ongelma

Ehrenfeuchtin–Silbergerin ongelma kysyy, kuinka pitkä sana voi olla sen pisimpien reunattomien tekijöiden pituuden suhteen, ennen kuin sillä on sen lyhimmän jakson pituinen reunaton tekijä. Ongelman ratkaisu on sanan pisimpien reunattomien tekijöiden pituudesta riippuva raja, jolle kaikilla ainakin tämän pituisilla sanoilla on välttämättä lyhimmän jakson pituinen reunaton tekijä. Tutkielmassa esitellään tämän ongelman paras tunnettu ratkaisu. Lisäksi tarkastellaan muita ongelmaan läheisesti liittyviä tuloksia. Päälauseena todistetaan paras tunnettu raja pisimpien reunattomien tekijöiden suhteen. Todistus on peräisin Štěpán Holubin ja Dirk Nowotkan artikkelista The Ehrenfeucht–Silberger problem (Journal of Combinatorial Theory, Series A) sekä tämän artikkelin alustavasta versiosta ICALP 2009 -konferenssin proceedings-julkaisussa. Esitetty ratkaisu näytetään vakiotermiä vaille optimaaliseksi vertaamalla sitä parhaaseen tunnettuun esimerkkiin äärettömästä sanajoukosta, jonka jokaisen sanan pisimmät reunattomat tekijät ovat lyhyempiä kuin lyhin jakso ja jonka jokaisen sanan pituus pisimpien reunattomien tekijöiden pituuden suhteen on suurin tunnettu. Johdatteluna esitellään perustuloksia sanan jaksoista ja reunattomista tekijöistä sekä esitellään eräitä muita ehtoja sille, milloin sanalla on sen lyhimmän jakson pituinen reunaton tekijä. Toisaalta tarkastellaan myös ongelmaa, joka kysyy vastaavaa rajaa lyhimmän jakson suhteen. Uutena tuloksena parannetaan parasta aiemmin tunnettua rajaa yhtä pienemmäksi, jolloin saatu raja on optimaalinen. Lisäksi todistetaan, mitä muotoa ovat kaikki sanat, joilla ei ole lyhimmän jaksonsa pituista reunatonta tekijää ja jotka ovat lyhimmän jaksonsa suhteen mahdollisimman pitkiä. Lisäksi tarkastellaan kriittistä tekijöihinjakoa, joka liittää sanan lyhimmän jakson sen paikallisiin jaksoihin. Kriittisen tekijöihinjaon lauseesta esitetään eräs todistus. Tämän lisäksi todistetaan päälauseen todistuksessa tarvittava lemma, joka liittyy sanan konjugaatin tekijöihinjaon kriittisyyteen.

Dispersive estimates for the Schrödinger equation

In this document we explore the issue of $L^1\to L^\infty$ estimates for the solution operator of the linear Schr\"{o}dinger equation, \begin{align*} iu_t-\Delta u+Vu&=0 &u(x,0)=f(x)\in \mathcal S(\R^n). \end{align*} We focus particularly on the five and seven dimensional cases. We prove that the solution operator precomposed with projection onto the absolutely continuous spectrum of $H=-\Delta+V$ satisfies the following estimate $\|e^{itH} P_{ac}(H)\|_{L^1\to L^\infty} \lesssim |t|^{-\frac{n}{2}}$ under certain conditions on the potential $V$. Specifically, we prove the dispersive estimate is satisfied with optimal assumptions on smoothness, that is $V\in C^{\frac{n-3}{2}}(\R^n)$ for $n=5,7$ assuming that zero is regular, $|V(x)|\lesssim \langle x\rangle^{-\beta}$ and $|\nabla^j V(x)|\lesssim \langle x\rangle^{-\alpha}$, $1\leq j\leq \frac{n-3}{2}$ for some $\beta>\frac{3n+5}{2}$ and $\alpha>3,8$ in dimensions five and seven respectively. We also show that for the five dimensional result one only needs that $|V(x)|\lesssim \langle x\rangle^{-4-}$ in addition to the assumptions on the derivative and regularity of the potential. This more than cuts in half the required decay rate in the first chapter. Finally we consider a problem involving the non-linear Schr\"{o}dinger equation. In particular, we consider the following equation that arises in fiber optic communication systems, \begin{align*} iu_t+d(t) u_{xx}+|u|^2 u=0. \end{align*} We can reduce this to a non-linear, non-local eigenvalue equation that describes the so-called dispersion management solitons. We prove that the dispersion management solitons decay exponentially in $x$ and in the Fourier transform of $x$.

Analysis of Self-Organization

The dissertation is devoted to the study of problems in calculus of variation, free boundary problems and gradient flows with respect to the Wasserstein metric. More concretely, we consider the problem of characterizing the regularity of minimizers to a certain interaction energy. Minimizers of the interaction energy have a somewhat surprising relationship with solutions to obstacle problems. Here we prove and exploit this relationship to obtain novel regularity results. Another problem we tackle is describing the asymptotic behavior of the Cahn-Hilliard equation with degenerate mobility. By framing the Cahn-Hilliard equation with degenerate mobility as a gradient flow in Wasserstein metric, in one space dimension, we prove its convergence to a degenerate parabolic equation under the framework recently developed by Sandier-Serfaty.

Nonlinear, nonhomogeneous parametric Neumann problems

We consider a parametric nonlinear Neumann problem driven by a nonlinear nonhomogeneous differential operator and with a Caratheodory reaction $f\left( t,x\right) $ which is $p-$superlinear in $x$ without satisfying the usual in such cases Ambrosetti-Rabinowitz condition. We prove a bifurcation type result describing the dependence of the positive solutions on the parameter $\lambda>0,$ we show the existence of a smallest positive solution $\overline{u}_{\lambda}$ and investigate the properties of the map $\lambda\rightarrow\overline{u}_{\lambda}.$ Finally we also show the existence of nodal solutions.

Regular homomorphisms of minimal sets

The classification of minimal sets is a central theme in abstract topological dynamics. Recently this work has been strengthened and extended by consideration of homomorphisms. Background material is presented in Chapter I. Given a flow on a compact Hausdorff space, the action extends naturally to the space of closed subsets, taken with the Hausdorff topology. These hyperspaces are discussed and used to give a new characterization of almost periodic homomorphisms. Regular minimal sets may be described as minimal subsets of enveloping semigroups. Regular homomorphisms are defined in Chapter II by extending this notion to homomorphisms with minimal range. Several characterizations are obtained. In Chapter III, some additional results on homomorphisms are obtained by relativizing enveloping semigroup notions. In Veech's paper on point distal flows, hyperspaces are used to associate an almost one-to-one homomorphism with a given homomorphism of metric minimal sets. In Chapter IV, a non-metric generalization of this construction is studied in detail using the new notion of a highly proximal homomorphism. An abstract characterization is obtained, involving only the abstract properties of homomorphisms. A strengthened version of the Veech Structure Theorem for point distal flows is proved. In Chapter V, the work in the earlier chapters is applied to the study of homomorphisms for which the almost periodic elements of the associated hyperspace are all finite. In the metric case, this is equivalent to having at least one fiber finite. Strong results are obtained by first assuming regularity, and then assuming that the relative proximal relation is closed as well.

Linear non-local diffusion problems in metric measure spaces

The aim of this paper is to provide a comprehensive study of some linear non-local diffusion problems in metric measure spaces. These include, for example, open subsets in ℝN, graphs, manifolds, multi-structures and some fractal sets. For this, we study regularity, compactness, positivity and the spectrum of the stationary non-local operator. We then study the solutions of linear evolution non-local diffusion problems, with emphasis on similarities and differences with the standard heat equation in smooth domains. In particular, we prove weak and strong maximum principles and describe the asymptotic behaviour using spectral methods.

Qualidade dos empregos e a carcinicultura marinha nos laboratórios da praia de Barreta/RN

To present research had for objective to study the quality of the employment in the maturation Laboratories and larviculture of the Beach of Barreta/RN, adopting for so much the criteria used by Reinecke(1999) to characterize a quality employment: surrender, benefits non salary, regularity and work reliability and of the wage, contractual status, social protection, work day, intensity of the work, risk of accidents and of occupational diseases, involvement in linked decisions to the section work, possibility for the development of professional qualifications. Of the exam of the data it was verified that the generated employments are considered employments of good quality. However, this result should be analyzed to the light of a context of extreme informality and of precarization of the work. Therefore, the results should be relativized. He/she/you imports to retain that one of the limitations of the study resides in the impossibility of generalizing the data for the whole section of the sea carcinicultura. In spite of that fact, he/she is considered that the objectives of the research were assisted fully and that the characterization of the profile of the employment generated by the section of the shrimpculture it is extremely important for the drawing of public politics gone back to foment this activity.

An A Posteriori Error Indicator for Discontinuous Galerkin Approximations of Fourth Order Elliptic Problems

We introduce a residual-based a posteriori error indicator for discontinuous Galerkin discretizations of the biharmonic equation with essential boundary conditions. We show that the indicator is both reliable and efficient with respect to the approximation error measured in terms of a natural energy norm, under minimal regularity assumptions. We validate the performance of the indicator within an adaptive mesh refinement procedure and show its asymptotic exactness for a range of test problems.

Méthodes de Bootstrap pour les modèles à facteurs

Cette thèse développe des méthodes bootstrap pour les modèles à facteurs qui sont couram- ment utilisés pour générer des prévisions depuis l'article pionnier de Stock et Watson (2002) sur les indices de diffusion. Ces modèles tolèrent l'inclusion d'un grand nombre de variables macroéconomiques et financières comme prédicteurs, une caractéristique utile pour inclure di- verses informations disponibles aux agents économiques. Ma thèse propose donc des outils éco- nométriques qui améliorent l'inférence dans les modèles à facteurs utilisant des facteurs latents extraits d'un large panel de prédicteurs observés. Il est subdivisé en trois chapitres complémen- taires dont les deux premiers en collaboration avec Sílvia Gonçalves et Benoit Perron. Dans le premier article, nous étudions comment les méthodes bootstrap peuvent être utilisées pour faire de l'inférence dans les modèles de prévision pour un horizon de h périodes dans le futur. Pour ce faire, il examine l'inférence bootstrap dans un contexte de régression augmentée de facteurs où les erreurs pourraient être autocorrélées. Il généralise les résultats de Gonçalves et Perron (2014) et propose puis justifie deux approches basées sur les résidus : le block wild bootstrap et le dependent wild bootstrap. Nos simulations montrent une amélioration des taux de couverture des intervalles de confiance des coefficients estimés en utilisant ces approches comparativement à la théorie asymptotique et au wild bootstrap en présence de corrélation sérielle dans les erreurs de régression. Le deuxième chapitre propose des méthodes bootstrap pour la construction des intervalles de prévision permettant de relâcher l'hypothèse de normalité des innovations. Nous y propo- sons des intervalles de prédiction bootstrap pour une observation h périodes dans le futur et sa moyenne conditionnelle. Nous supposons que ces prévisions sont faites en utilisant un ensemble de facteurs extraits d'un large panel de variables. Parce que nous traitons ces facteurs comme latents, nos prévisions dépendent à la fois des facteurs estimés et les coefficients de régres- sion estimés. Sous des conditions de régularité, Bai et Ng (2006) ont proposé la construction d'intervalles asymptotiques sous l'hypothèse de Gaussianité des innovations. Le bootstrap nous permet de relâcher cette hypothèse et de construire des intervalles de prédiction valides sous des hypothèses plus générales. En outre, même en supposant la Gaussianité, le bootstrap conduit à des intervalles plus précis dans les cas où la dimension transversale est relativement faible car il prend en considération le biais de l'estimateur des moindres carrés ordinaires comme le montre une étude récente de Gonçalves et Perron (2014). Dans le troisième chapitre, nous suggérons des procédures de sélection convergentes pour les regressions augmentées de facteurs en échantillons finis. Nous démontrons premièrement que la méthode de validation croisée usuelle est non-convergente mais que sa généralisation, la validation croisée «leave-d-out» sélectionne le plus petit ensemble de facteurs estimés pour l'espace généré par les vraies facteurs. Le deuxième critère dont nous montrons également la validité généralise l'approximation bootstrap de Shao (1996) pour les regressions augmentées de facteurs. Les simulations montrent une amélioration de la probabilité de sélectionner par- cimonieusement les facteurs estimés comparativement aux méthodes de sélection disponibles. L'application empirique revisite la relation entre les facteurs macroéconomiques et financiers, et l'excès de rendement sur le marché boursier américain. Parmi les facteurs estimés à partir d'un large panel de données macroéconomiques et financières des États Unis, les facteurs fortement correlés aux écarts de taux d'intérêt et les facteurs de Fama-French ont un bon pouvoir prédictif pour les excès de rendement.

Projeto café do trabalhador como promotor de segurança alimentar e nutricional: avaliação da eficácia da unidade Natal-RN

The evaluation of public policies that promote Food Security and Nutrition (FSN) it s a multidisciplinary activity extremely relevant to the effectiveness of actions to legitimize the Human Right to Adequate Food (HRAF). This study aimed at assessing the effectiveness of the unit project Natal-RN Café do Trabalhador in promoting SAN to its users. The theoretical framework is based on the public and political and on the dimensions of the concept of FSN (quantity and quality-regularity). Through a qualitative approach, methodologically this was the work of an evaluation of efficiency of the unit Natal-RN of Café do Trabalhador project in light of the assumptions of the concept of SAN. Data collection was conducted through retrospective archival research in official documents of the project, semi-structured interviews with managers involved in its implementation (representative of the Secretary of State for Employment, Housing and Care of RN SETHAS and third party), socioeconomic questionnaire applied to the users of the unit, check the amount, regularity and quality of meals offered for 15 days (menu routine) using the descriptive form menu and form filling type checklist for verification of compliance with good practices . Methods of analysis, we used content analysis, descriptive statistics and compared to previously established parameters for the project. As categories of analysis were defined organizational arrangement, access, user, food quantity-regularity and food quality. The results show that, it was found in the category arrangement that will implement the project dismissed technical criteria for choosing the districts and the quantitative distribution of meals for each location. It was found that the valuation of the shares of the company outsources technical SETHA has not been performed. We observed in the access category, the unit has a strategic location, but lack of space in the refectory. The main obstacle to economic access for users is the lack of a register for the beneficiaries. In the category of users, it was identified that the clientele of the project it is predominantly men, with more than 51 years, low education, earning wages less 1 obtained through informal employment, which they move up through the unit transport collective, go to all days of operation due primarily to price. About the meals category quantity-regularity of food showed that the menu serves 95% of the desired needs, and that holidays and weekends are periods of disrupting the regularity of supply of meals. Regarding the category of food quality, it was found that the nutritional aspect on the menu are food sources rich in sodium, nitrates and low in fiber. In the aspect of hygiene and sanitation are the main limitations related to waste management, lack of exposure controls of food prepared and inadequacies of the physical structure. The results showed that in general and the institutional arrangement of the organs attached to the project should establish a systematic evaluation project is to establish as a promoter of and FSN overcome these obstacles

POSITIVE FILTERED P_N METHOD FOR LINEAR TRANSPORT EQUATIONS AND THE ASSOCIATED OPTIMIZATION ALGORITHM

We propose a positive, accurate moment closure for linear kinetic transport equations based on a filtered spherical harmonic (FP_N) expansion in the angular variable. The FP_N moment equations are accurate approximations to linear kinetic equations, but they are known to suffer from the occurrence of unphysical, negative particle concentrations. The new positive filtered P_N (FP_N+) closure is developed to address this issue. The FP_N+ closure approximates the kinetic distribution by a spherical harmonic expansion that is non-negative on a finite, predetermined set of quadrature points. With an appropriate numerical PDE solver, the FP_N+ closure generates particle concentrations that are guaranteed to be non-negative. Under an additional, mild regularity assumption, we prove that as the moment order tends to infinity, the FP_N+ approximation converges, in the L2 sense, at the same rate as the FP_N approximation; numerical tests suggest that this assumption may not be necessary. By numerical experiments on the challenging line source benchmark problem, we confirm that the FP_N+ method indeed produces accurate and non-negative solutions. To apply the FP_N+ closure on problems at large temporal-spatial scales, we develop a positive asymptotic preserving (AP) numerical PDE solver. We prove that the propose AP scheme maintains stability and accuracy with standard mesh sizes at large temporal-spatial scales, while, for generic numerical schemes, excessive refinements on temporal-spatial meshes are required. We also show that the proposed scheme preserves positivity of the particle concentration, under some time step restriction. Numerical results confirm that the proposed AP scheme is capable for solving linear transport equations at large temporal-spatial scales, for which a generic scheme could fail. Constrained optimization problems are involved in the formulation of the FP_N+ closure to enforce non-negativity of the FP_N+ approximation on the set of quadrature points. These optimization problems can be written as strictly convex quadratic programs (CQPs) with a large number of inequality constraints. To efficiently solve the CQPs, we propose a constraint-reduced variant of a Mehrotra-predictor-corrector algorithm, with a novel constraint selection rule. We prove that, under appropriate assumptions, the proposed optimization algorithm converges globally to the solution at a locally q-quadratic rate. We test the algorithm on randomly generated problems, and the numerical results indicate that the combination of the proposed algorithm and the constraint selection rule outperforms other compared constraint-reduced algorithms, especially for problems with many more inequality constraints than variables.