Insufficient Evidence of Jatropha curcas L. Invasiveness: Experimental Observations in Burkina Faso, West Africa

Biofuel plants such as Jatropha curcas L. have potential to support the livelihoods of rural communities and contribute to sustainable rural development in Africa, if risks and uncertainties are minimized. Yet, recent papers have warned of the risk of biological invasions in such tropical regions as a consequence of the introduction of exotic biofuel crops. We investigated the seed dispersal risk and invasiveness potential of both J. curcas monoculture plantations and live fences into adjacent cultivated and uncultivated land use systems in Sissili province, Burkina Faso. Invasiveness potential was assessed through (i) detecting evidence of natural regeneration in perimeters around J. curcas plantations and live fences, (ii) assessing seed dispersal mechanisms, and (iii) assessing seedling establishment potential through in situ direct seed sowing. Spontaneous regeneration around the plantation perimeters of the three sites was very low. Individual seedling density around J. curcas live fences was less than 0.01 m⁻² in all sites. Seventy percent of the seedlings were found close to the live fence and most of them derived from the same year (96 %), which indicates low seed-bank longevity and seedling survival. J. curcas can be dispersed by small mammals and arthropods, particularly rodents and ants. In some sites, such as in Onliassan, high secondary seed dispersal by animals (up to 98 %) was recorded. There were highly significant differences in germination rates between seeds at the soil surface (11 %) and those buried artificially at 1–2-cm depth (64 %). In conclusion, we failed to find convincing evidence of the spreading of J. curcas or any significant impact on the surrounding environment.

Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

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.

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.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.