Guo, Saxena, and Sinhababu (TOC'18, CCC'18) defined a natural, approximative analog of the polynomial system satisfiability problem, which they called approximate polynomial satisfiability (APS). They proved algebraic and geometric properties of it and showed an NP-hardness lower bound and a PSPACE upper bound for it. They further established how the problem naturally occurs in border complexity and Geometric complexity theory (GCT) and used the problem to construct hitting sets for ̅{VP} in PSPACE, hence greatly mitigating the GCT chasm. The starting point of this work is the observation that Guo, Saxena, and Sinhababu’s criterion for non-existence of approximative solution can be interpreted as an analog of Weak Hilbert’s Nullstellensatz in the approximative setting. We extend their work by proving an analog of Strong Hilbert’s Nullstellensatz in the approximative setting. Concretely, we give an algebraic criterion for containment between approximative solution sets defined by systems of polynomials. In fact, this characterization turns out to be equivalent to membership in the integral closure over a maximal ideal of a local subring of ℂ(x₁,…, x_n) determined by the given polynomials. In addition, we use our proof to provide a PSPACE algorithm for testing this containment, exponentially better than the EXPSPACE bounds for polynomial subalgebra membership testing and the polynomial integral closure membership testing, hence matching the complexity bound of Guo, Saxena, and Sinhababu’s Weak Approximative Nullstellensatz.

We investigate the number of real zeros of a univariate k-sparse polynomial f over the reals, when the coefficients of f come from independent standard normal distributions. Recently Bürgisser, Ergür and Tonelli-Cueto showed that the expected number of real zeros of f in such cases is bounded by [EQUATION]. In this work, we improve the bound to [EQUATION] and also show that this bound is tight by constructing a family of sparse support whose expected number of real zeros is lower bounded by [EQUATION]. Our main technique is an alternative formulation of the Kac integral by Edelman-Kostlan which allows us to bound the expected number of zeros of f in terms of the expected number of zeros of polynomials of lower sparsity. Using our technique, we also recover the O (log n) bound on the expected number of real zeros of a dense polynomial of degree n with coefficients coming from independent standard normal distributions.

In an IaaS cloud, the dynamic VM scheduler observes and mitigates resource hotspots to maintain performance in an oversubscribed environment. Most systems are focused on schedulers that fit very large infrastructures, which lead to workload-dependent optimisations, thereby limiting their portability. However, while the number of massive public clouds is very small, there is a countless number of private clouds running very different workloads. In that context, we consider that it is essential to look for schedulers that overcome the workload diversity observed in private clouds to benefit as many use cases as possible.

Enterprises today increasingly rely on IT for their day-to-day processes. Newer application types (such as web, mobile, social, and big data applications) and the advent of public cloud computing have further increased the role of IT in enterprises. The result is that a typical enterprise data center today can have thousands of workloads spanning tens of thousands of nodes and hundreds of thousands of virtual machines. This makes day-to-day IT management tasks challenging for enterprise IT administrators, since they need to manage multiple types of hardware and software entities that can interact with each other in complex ways, and can span private data centers and public clouds. The problem is made worse by the management interfaces of current data center solutions, which work poorly at such a large scale, as they are navigational in nature and require administrators to learn a variety of tools and their myriad workflows. This can result in administrators spending too much time learning the tools and understanding when to use which tool, otherwise, they run the risk of making costly mistakes. In this paper we present the design and implementation of QUEST, a search-driven data center management system that provides an easy-to-use interface to search for data center entities, get information about them, and perform actions on them, all from a single pane of glass. QUEST allows administrators to express their intent through a semi-structured query language, and interfaces with multiple management components behind the scenes to return the most relevant information, this eliminates the need for administrators having to learn and remember the workflows of multiple data center management interfaces. We built QUEST [1] as a part of the Nutanix data center management solution [2] and it is currently used by 25% of Nutanix's customers [3] to manage tens of thousands of nodes. Initial customer feedback is positive and validates our hypothesis that search-based management interfaces are superior to traditional navigational interfaces in reducing administrator burden and making them more effective. Our evaluation shows that QUEST can support interactive use in real data centers, and a case study with a real customer performance trouble ticket shows that QUEST can reduce the number of steps by 6× compared to state-of-the-art management tools in troubleshooting scenarios.

k-HA (high-Availability) is an important faulttolerance property of VM placement in clouds and clusters - it is the ability to tolerate up to k host failures by relocating VMs from failed hosts without disrupting other VMs. It has long been assumed [1] that deciding the existence of a k-HA placement is ΣP 3 -hard. In a surprising yet simple result we show that k-HA reduces to multiple knapsack and hence is in NP= ΣP 1 . We propose a stochastic model for multiple knapsack that not only captures real-world workloads but also provides a uniform basis for comparing the efficiencies of different polynomial-time heuristics. We prove, using the central limit theorem and linear programming, that, there exists a best polynomial-time heuristic, albeit impractical from the standpoint of implementation. We turn to industry practice and discuss the drawbacks of commonly used heuristics-First- fit,Best-fit,Worst-fit,MTHM and CSP. Load-balancing is a fundamental customer requirement in industry. Based on a large real-world dataset of cluster workloads (from industry leader Nutanix) we show that the natural load-balancing heuristic - Water- filling - has several excellent properties. We compare and contrast Water-filling with MTHM using our stochastic model and find that Water-filling is a heuristic of choice.