Search

A (k, m)-Furstenberg set is a subset S ⊂ F q n with the property that each k-dimensional subspace of F q n can be translated so that it intersects S in at least m points. Ellenberg and Erman (Algebra Number Theory 10(7), 1415–1436 (2016)) proved that (k, m)-Furstenberg sets must have size at least C n , k m n / k , where C n , k is a constant depending only n and k. In this paper, we adopt the same proof strategy as Ellenberg and Erman, but use more elementary techniques than their scheme-theoretic method. By modifying certain parts of the argument, we obtain an improved bound on C n , k , and our improved bound is nearly optimal for an algebraic generalization the main combinatorial result. We also extend our analysis to give lower bounds for sets that have large intersection with shifts of a specific family of higher-degree co-dimension n - k varieties, instead of just co-dimension n - k subspaces. [ABSTRACT FROM AUTHOR]

If G is a graph with vertex set V, let Conf n sink (G , V) be the space of n-tuples of points on G, which are only allowed to overlap on elements of V. We think of Conf n sink (G , V) as a configuration space of points on G, where points are allowed to collide on vertices. In this paper, we attempt to understand these spaces from two separate, but closely related, perspectives. Using techniques of combinatorial topology we compute the fundamental groups and homology groups of Conf n sink (G , V) in the case where G is a tree. Next, we use techniques of asymptotic algebra to prove statements about Conf n sink (G , V) , for general graphs G, whenever n is sufficiently large. It is proven that, for general graphs, the homology groups exhibit generalized representation stability in the sense of Ramos (arXiv:1606.02673, 2016). [ABSTRACT FROM AUTHOR]

Tropical algebra is an emerging field with a number of applications in various areas of mathematics. In many of these applications appeal to tropical polynomials allows studying properties of mathematical objects such as algebraic varieties from the computational point of view. This makes it important to study both mathematical and computational aspects of tropical polynomials. In this paper we prove a tropical Nullstellensatz, and moreover, we show an effective formulation of this theorem. Nullstellensatz is a natural step in building algebraic theory of tropical polynomials and its effective version is relevant for computational aspects of this field. On our way we establish a simple formulation of min-plus and tropical linear dualities. We also observe a close connection between tropical and min-plus polynomial systems. [ABSTRACT FROM AUTHOR]

A Euclidean distance matrix D(α) is defined by Dij=(αi-αj)2, where α=(α1,...,αn) is a real vector. We prove that D(α) cannot be written as a sum of 2n-2 nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation. [ABSTRACT FROM AUTHOR]

Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃ R plays a crucial role in the study of geometric problems. Sometimes ∃ R is referred to as the 'real analog' of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, ∃ R deals with existentially quantified real variables. In analogy to Π 2 p and Σ 2 p in the famous polynomial hierarchy, we study the complexity classes ∀ ∃ R and ∃ ∀ R with real variables. Our main interest is the AreaUniversality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AreaUniversality is ∀ ∃ R -complete and support this conjecture by proving ∃ R - and ∀ ∃ R -completeness of two variants of AreaUniversality. To this end, we introduce tools to prove ∀ ∃ R -hardness and membership. Finally, we present geometric problems as candidates for ∀ ∃ R -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability. [ABSTRACT FROM AUTHOR]