 Award ID(s):
 1901950
 NSFPAR ID:
 10342024
 Date Published:
 Journal Name:
 Transactions of the American Mathematical Society
 ISSN:
 00029947
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvátal rank. We determine the Chvátal rank of all known cutting planes and show that almost all of them have Chvátal rank 1. We observe that these inequalities have an associated hypergraph that is βacyclic. Our second goal is to derive deeper cutting planes; to do so, we consider hypergraphs that admit βcycles. We introduce a novel class of valid inequalities arising from odd βcycles, that generally have Chvátal rank 2. These inequalities allow us to obtain the first characterization of the multilinear polytope for hypergraphs that contain βcycles. Namely, we show that the multilinear polytope for cycle hypergraphs is given by the standard linearization inequalities, flower inequalities, and odd βcycle inequalities. We also prove that odd βcycle inequalities can be separated in linear time when the hypergraph is a cycle hypergraph. This shows that instances represented by cycle hypergraphs can be solved in polynomial time. Last, to test the strength of odd βcycle inequalities, we perform numerical experiments that imply that they close a significant percentage of the integrality gap.more » « less

Abstract Let $K$ be a real closed field with a nontrivial nonarchimedean absolute value. We study a refined version of the tropicalization map, which we call real tropicalization map, that takes into account the signs on $K$. We study images of semialgebraic subsets of $K^n$ under this map from a general point of view. For a semialgebraic set $S \subseteq K^n$ we define a space $S_r^{{\operatorname{an}}}$ called the real analytification, which we show to be homeomorphic to the inverse limit of all real tropicalizations of $S$. We prove a real analogue of the tropical fundamental theorem and show that the tropicalization of any semialgebraic set is described by tropicalization of finitely many inequalities, which are valid on the semialgebraic set. We also study the topological properties of real analytification and tropicalization. If $X$ is an algebraic variety, we show that $X_r^{{\operatorname{an}}}$ can be canonically embedded into the real spectrum $X_r$ of $X$, and we study its relation with the Berkovich analytification of $X$.

Abstract We develop a convenient framework for characterizing multipartite entanglement in composite systems, based on relations between entropies of various subsystems. This continues the program initiated in [1], of using holography to effectively recast the geometric problem into an algebraic one. We prove that, for an arbitrary number of parties, our procedure identifies a finite set of entropic information quantities that we conveniently represent geometrically in the form of an arrangement of hyperplanes. This leads us to define the
holographic entropy arrangement , whose algebraic and combinatorial aspects we explore in detail. Using the framework, we derive three new information quantities for four parties, as well as a new infinite family for any number of parties. A natural construct from the arrangement is theholographic entropy polyhedron which captures holographic entropy inequalities describing the physically allowed region of entropy space. We illustrate how to obtain the polyhedron by winnowing down the arrangement through a sieve to pick out candidate sign‐definite information quantities. Comparing the polyhedron with the holographic entropy cone, we find perfect agreement for 4 parties and corroborating evidence for the conjectured 5‐party entropy cone. We work with explicit configurations in arbitrary (time‐dependent) states leading to both simple derivations and an intuitive picture of the entanglement pattern. 
In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graphconstrained group testing. Graphconstrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology. The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graphconstrained group testing is nearoptimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs. Finally, we provide empirical results which suggest that our connectedsubgraph tests perform better not just in theory but also in practice, and in particular perform better on a realworld network topology.more » « less

Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks. In many of these applications, the underlying context is better modelled as a weighted hypergraph that keeps evolving with time. This motivates the problem of maintaining the densest subhypergraph of a weighted hypergraph in a dynamic setting, where the input keeps changing via a sequence of updates (hyperedge insertions/deletions). Previously, the only known algorithm for this problem was due to Hu et al. [19]. This algorithm worked only on unweighted hypergraphs, and had an approximation ratio of (1 +ϵ)r2 and an update time of O(poly(r, log n)), where r denotes the maximum rank of the input across all the updates. We obtain a new algorithm for this problem, which works even when the input hypergraph is weighted. Our algorithm has a significantly improved (nearoptimal) approximation ratio of (1 +ϵ) that is independent of r, and a similar update time of O(poly(r, log n)). It is the first (1 +ϵ)approximation algorithm even for the special case of weighted simple graphs. To complement our theoretical analysis, we perform experiments with our dynamic algorithm on largescale, realworld datasets. Our algorithm significantly outperforms the state of the art [19] both in terms of accuracy and efficiency.more » « less