Search

We show that under mild assumptions, the Fano surfaces of lines on smooth cubic threefolds are the only smooth subvarieties of abelian varieties whose Tannaka group for the convolution of perverse sheaves is an exceptional simple group. This in particular leads to a considerable strengthening of our previous work on the Shafarevich conjecture. A key idea is to control the Hodge decomposition on cohomology by a cocharacter of the Tannaka group of Hodge modules, and to play this off against an improvement of the Hodge number estimates for irregular varieties by Lazarsfeld-Popa and Lombardi.

We prove the Shafarevich conjecture for very irregular varieties of dimension less than half the dimension of their Albanese variety, subject to some mild numerical conditions. Our proof relies on the Lawrence-Venkatesh method as in the work of Lawrence-Sawin, together with the big monodromy criterion from our work with Javanpeykar and Lehn., Comment: The main results now hold also for varieties without rational points and under weaker numerical assumptions

We present QUBO.jl, an end-to-end Julia package for working with QUBO (Quadratic Unconstrained Binary Optimization) instances. This tool aims to convert a broad range of JuMP problems for straightforward application in many physics and physics-inspired solution methods whose standard optimization form is equivalent to the QUBO. These methods include quantum annealing, quantum gate-circuit optimization algorithms (Quantum Optimization Alternating Ansatz, Variational Quantum Eigensolver), other hardware-accelerated platforms, such as Coherent Ising Machines and Simulated Bifurcation Machines, and more traditional methods such as simulated annealing. Besides working with reformulations, QUBO.jl allows its users to interface with the aforementioned hardware, sending QUBO models in various file formats and retrieving results for subsequent analysis. QUBO.jl was written as a JuMP / MathOptInterface (MOI) layer that automatically maps between the input and output frames, thus providing a smooth modeling experience.

We investigate the relationship between affine and Stein varieties in the context of rigid geometry. We show that the two concepts are much more closely related than in complex geometry, e.g. they are equivalent for surfaces. This rests on the density of algebraic functions in analytic functions. One key ingredient to prove such a density statement is an extension result for Cartier divisors., Comment: 44 pages

Let $A$ be an abelian variety over a complete non-Archimedean field $K$. The universal cover of the Berkovich space attached to $A$ reflects the reduction behaviour of $A$. In this paper the universal cover of the universal vector extension $E(A)$ of $A$ is described. In a forthcoming paper ( arXiv:2007.04659), this will be one of the crucial tools to show that rigid analytic functions on $E(A)$ are all constant., Comment: This is the first part of arXiv:2007.04659 which is now split into two

Motivated by recent work of Lawrence-Venkatesh and Lawrence-Sawin, we show that non-isotrivial families of subvarieties in abelian varieties have big monodromy when twisted by generic rank one local systems. While Lawrence-Sawin discuss the case of subvarieties of codimension one, our results hold for subvarieties of codimension at least half the dimension of the ambient abelian variety. For the proof, we use a combination of geometric arguments and representation theory to show that the Tannaka groups of intersection complexes on such subvarieties are big., Comment: 68 pages, v2: substantial improvement of the main results

The present note is devoted to an amendment to a recent paper of Ellenberg, Lawrence and Venkatesh. Roughly speaking, the main result here states the subpolynomial growth of the number of integral points with bounded height of a variety over a number field whose fundamental group is large. Such an improvement, i.e. requiring large fundamental group as opposed to the existence of a geometric variation of pure Hodge structures, was already asked in op.cit.., Comment: Minor modifications

A pendant vertex is one of degree one and an isolated vertex has degree zero. A neighborhood star-free (NSF for short) graph is one in which every vertex is contained in a triangle except pendant vertices and isolated vertices. This class has been considered before for several contexts. In the present paper, we study the complexity of the dominating induced matching (DIM) problem and the perfect edge domination (PED) problem for NSF graphs. We prove the corresponding decision problems are NP-Complete for several of its subclasses. As an added value of this study, we have shown three connected variants of planar positive 1in3SAT are also NP-Complete. Since these variants are more basic in complexity theory context than many graph problems, these results can be useful to prove that other problems are NP-Complete.

Let $K$ be a complete non-trivially valued non-Archimedean field. Given an algebraic group over $K$ on which every regular function is constant, any rigid analytic function is shown to be constant too. It follows that an algebraic group over $K$ is affine if and only if the associated $K$-analytic space is Stein; that is, rigid analytic embeddings of it in an affine space may always be chosen to be given by algebraic functions. Arguably curiously, the corresponding statement over the complex numbers is false., Comment: The paper has been split into two. This is the second part

The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension K, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures., Comment: 16 pages

Crime events are known to reveal spatio-temporal patterns, which can be used for predictive modeling and subsequent decision support. While the focus has hitherto been placed on areas with high population density, we address the challenging undertaking of predicting crime hotspots in regions with low population densities and highly unequally-distributed crime.This results in a severe sparsity (i.e., class imbalance) of the outcome variable, which impedes predictive modeling. To alleviate this, we develop machine learning models for spatio-temporal prediction that are specifically adjusted for an imbalanced distribution of the class labels and test them in an actual setting with state-of-the-art predictors (i.e., socio-economic, geographical, temporal, meteorological, and crime variables in fine resolution). The proposed imbalance-aware hyper-ensemble increases the hit ratio considerably from 18.1% to 24.6% when aiming for the top 5% of hotspots, and from 53.1% to 60.4% when aiming for the top 20% of hotspots.

In this paper we start the study of configurations of flags in closed orbits of real forms using mainly tools of GIT. As an application, using cross ratio coordinates for generic configurations, we identify boundary unipotent representations of the fundamental group of the figure eight knot complement into real forms of $\mathrm{PGL}(4,\mathbb{C})$.

Let $k$ be a non-archimedean complete valued field and $X$ be a $k$-analytic space in the sense of Berkovich. In this note, we prove the equivalence between three properties: 1) for every complete valued extension $k'$ of $k$, every coherent sheaf on $X \times_{k} k'$ is acyclic; 2) $X$ is Stein in the sense of complex geometry (holomorphically separated, holomorphically convex) and higher cohomology groups of the structure sheaf vanish (this latter hypothesis is crucial if, for instance, $X$ is compact); 3) $X$ admits a suitable exhaustion by compact analytic domains considered by Liu in his counter-example to the cohomological criterion for affinoidicity. When $X$ has no boundary the characterization is simpler: in~2) the vanishing of higher cohomology groups of the structure sheaf is no longer needed, so that we recover the usual notion of Stein space in complex geometry; in 3) the domains considered by Liu can be replaced by affinoid domains, which leads us back to Kiehl's definition of Stein space. v2: major revision to handle also the case of spaces with boundary, Comment: 31 pages

The interval Distance Geometry Problem (iDGP) consists in finding a realization in $\mathbb{R}^K$ of a simple undirected graph $G=(V,E)$ with nonnegative intervals assigned to the edges in such a way that, for each edge, the Euclidean distance between the realization of the adjacent vertices is within the edge interval bounds. In this paper, we focus on the application to the conformation of proteins in space, which is a basic step in determining protein function: given interval estimations of some of the inter-atomic distances, find their shape. Among different families of methods for accomplishing this task, we look at mathematical programming based methods, which are well suited for dealing with intervals. The basic question we want to answer is: what is the best such method for the problem? The most meaningful error measure for evaluating solution quality is the coordinate root mean square deviation. We first introduce a new error measure which addresses a particular feature of protein backbones, i.e. many partial reflections also yield acceptable backbones. We then present a set of new and existing quadratic and semidefinite programming formulations of this problem, and a set of new and existing methods for solving these formulations. Finally, we perform a computational evaluation of all the feasible solver$+$formulation combinations according to new and existing error measures, finding that the best methodology is a new heuristic method based on multiplicative weights updates.

One of the most important combinatorial optimization problems is graph coloring. There are several variations of this problem involving additional constraints either on vertices or edges. They constitute models for real applications, such as channel assignment in mobile wireless networks. In this work, we consider some coloring problems involving distance constraints as weighted edges, modeling them as distance geometry problems. Thus, the vertices of the graph are considered as embedded on the real line and the coloring is treated as an assignment of positive integers to the vertices, while the distances correspond to line segments, where the goal is to find a feasible intersection of them. We formulate different such coloring problems and show feasibility conditions for some problems. We also propose implicit enumeration methods for some of the optimization problems based on branch-and-prune methods proposed for distance geometry problems in the literature. An empirical analysis was undertaken, considering equality and inequality constraints, uniform and arbitrary set of distances, and the performance of each variant of the method considering the handling and propagation of the set of distances involved., Comment: 24 pages, 14 figures, 9 tables, 2 algorithms

Let $k$ be a complete non-archimedean field (non trivially valued). Given a reductive $k$-group $G$, we prove that hyperspecial subgroups of $G(k)$ (i.e. those arising from reductive models of $G$) are maximal among bounded subgroups. The originality resides in the argument: it is inspired by the case of $\textrm{GL}_n$ and avoids all considerations on the Bruhat-Tits building of $G$., Comment: To appear at "Annales de l'Institut Fourier". This version avoids completely Berkovich geometry

We propose a new speed and departure time optimization algorithm for the Pollution-Routing Problem (PRP), which runs in quadratic time and returns a certified optimal schedule. This algorithm is embedded into an iterated local search-based metaheuristic to achieve a combined speed, scheduling and routing optimization. The start of the working day is set as a decision variable for individual routes, thus enabling a better assignment of human resources to required demands. Some routes that were evaluated as unprofitable can now appear as viable candidates later in the day, leading to a larger search space and further opportunities of distance optimization via better service consolidation. Extensive computational experiments on available PRP benchmark instances demonstrate the good performance of the algorithms. The flexible departure times from the depot contribute to reduce the operational costs by 8.36% on the considered instances., Comment: 12 pages

In this paper we study heights on quotient varieties in the sense of Geometric Invariant Theory (GIT). We generalise a construction of Burnol and we generalise diverse lower bounds of the height of semi-stable points due to Bost, Zhang, Gasbarri and Chen. In order to prove Burnol's formula for the height on the quotient we develop a Kempf-Ness theory in the setting of Berkovich analytic spaces, completing the former work of Burnol.

We propose an exact polynomial algorithm for a resource allocation problem with convex costs and constraints on partial sums of resource consumptions, in the presence of either continuous or integer variables. No assumption of strict convexity or differentiability is needed. The method solves a hierarchy of resource allocation subproblems, whose solutions are used to convert constraints on sums of resources into bounds for separate variables at higher levels. The resulting time complexity for the integer problem is $O(n \log m \log (B/n))$, and the complexity of obtaining an $\epsilon$-approximate solution for the continuous case is $O(n \log m \log (B/\epsilon))$, $n$ being the number of variables, $m$ the number of ascending constraints (such that $m < n$), $\epsilon$ a desired precision, and $B$ the total resource. This algorithm attains the best-known complexity when $m = n$, and improves it when $\log m = o(\log n)$. Extensive experimental analyses are conducted with four recent algorithms on various continuous problems issued from theory and practice. The proposed method achieves a higher performance than previous algorithms, addressing all problems with up to one million variables in less than one minute on a modern computer., Comment: Working Paper -- MIT, 23 pages

We consider several Vehicle Routing Problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customers selection, assignment to vehicles, and sequencing of deliveries for each route. We propose a new neighborhood search for these problems which explores an exponential number of solutions in pseudo polynomial time. The search is conducted with standard VRP neighborhoods on an "exhaustive" solution representation, visiting all customers. Since visiting all customers is usually infeasible or sub-optimal, an efficient "Select" algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open., Comment: Working Paper -- MIT, Revised, 34 pages

The problem of optimal allocation of samples in surveys using a stratified sampling plan was first discussed by Neyman in 1934. Since then, many researchers have studied the problem of the sample allocation in multivariate surveys and several methods have been proposed. Basically, these methods are divided into two class: The first involves forming a weighted average of the stratum variances and finding the optimal allocation for the average variance. The second class is associated with methods that require that an acceptable coefficient of variation for each of the variables on which the allocation is to be done. Particularly, this paper proposes a new optimization approach to the second problem. This approach is based on an integer programming formulation. Several experiments showed that the proposed approach is efficient way to solve this problem, considering a comparison of this approach with the other approach from the literature.

We present a proof of Thue-Siegel-Roth's Theorem (and its more recent variants, such as those of Lang for number fields and that "with moving targets" of Vojta) as an application of Geometric Invariant Theory (GIT). Roth's Theorem is deduced from a general formula comparing the height of a semi-stable point and the height of its projection on the GIT quotient. In this setting, the role of the zero estimates appearing in the classical proof is played by the geometric semi-stability of the point to which we apply the formula., Comment: Second revised version. Many typos corrected and an error corrected in Section 6.3

Euclidean distance geometry is the study of Euclidean geometry based on the concept of distance. This is useful in several applications where the input data consists of an incomplete set of distances, and the output is a set of points in Euclidean space that realizes the given distances. We survey some of the theory of Euclidean distance geometry and some of the most important applications: molecular conformation, localization of sensor networks and statics., Comment: 64 pages, 21 figures

We report a new optimal resolution for the statistical stratification problem under proportional sampling allocation among strata. Consider a finite population of N units, a random sample of n units selected from this population and a number L of strata. Thus, we have to define which units belong to each stratum so as to minimize the variance of a total estimator for one desired variable of interest in each stratum,and consequently reduce the overall variance for such quantity. In order to solve this problem, an exact algorithm based on the concept of minimal path in a graph is proposed and assessed. Computational results using real data from IBGE (Brazilian Central Statistical Office) are provided.