We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of \(\sum _{i=1}^n x_i\) for 0/1 variables under the constraint \(\sum _{i=1}^n x_i \ge q\), with \(q \in \mathbb {R}\). Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász–Schrijver and Sherali–Adams hierarchies require (maximal) rank n to solve them, already when q = 1/2 is constant. The SOS hierarchy requires only sublinear rank \(O(\sqrt {n})\) to solve unweighted MK when q = 1/2. On the other hand, when q is allowed to vary with n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small (0 < q ≤ 2− n). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter q.

Local intrinsic dimension (LID) estimation methods have received a lot of attention in recent years thanks to the progress in deep neural networks and generative modeling. In opposition to old non-parametric methods, new methods use generative models to approximate diffused dataset density to scale the methods to high-dimensional datasets (e.g. images). In this paper, we investigate the recent state-of-the-art parametric LID estimation methods from the perspective of the Wiener process. We explore how these methods behave when their assumptions are not met. We give an extended mathematical description of those methods and their error as a function of the probability density of the data.

Optimal packing of objects in containers is a critical problem in various real-life and industrial applications. This paper investigates the two-dimensional packing of convex polygons without rotations, where only translations are allowed. We study different settings depending on the type of containers used, including minimizing the number of containers or the size of the container based on an objective function. Building on prior research in the field, we develop polynomial-time algorithms with improved approximation guarantees upon the best-known results by Alt, de Berg and Knauer, as well as Aamand, Abrahamsen, Beretta and Kleist, for problems such as Polygon Area Minimization, Polygon Perimeter Minimization, Polygon Strip Packing, and Polygon Bin Packing. Our approach utilizes a sequence of object transformations that allows sorting by height and orientation, thus enhancing the effectiveness of shelf packing algorithms for polygon packing problems. In addition, we present efficient approximation algorithms for special cases of the Polygon Bin Packing problem, progressing toward solving an open question concerning an O(1)-approximation algorithm for arbitrary polygons.

The Empty Integral Hull problem is a feasibility problem that is a linear representation of a subset of the Boolean Hypercube with n vertices with no integral points. In this paper, we study the Sum of Squares rank of the problem. We present a novel approach to derive SoS bounds by transforming the problem into a sequence of questions in the Boolean Function Analysis, positive definiteness of tri-diagonal matrices, and finally, into a problem from the field of Continued Fractions. The results showed for these intermediate problems are of independent interest. We apply the techniques to prove that the SoS rank for the Empty Integral Hull problem is at least

We consider two key issues faced by many clustering methods when used for data summarization, namely (a) an unfair representation of "demographic groups” and (b) distorted summarizations, where data points in the summary represent subsets of the original data of vastly different sizes. Previous work made important steps towards handling separately each of these two issues in the context of the fundamental k-Center clustering objective through the study of fast algorithms for natural models that address them. We show that it is possible to effectively address both (a) and (b) simultaneously by presenting a clustering procedure that works for a canonical combined model and (i) is fast, both in theory and practice, (ii) exhibits a worst-case constant-factor guarantee, and (iii) gives promising computational results showing that there can be significant benefits in addressing both issues together instead of sequentially.

We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in n variables with roots placed in points k-1 and k. Functions of this type have played a central role in deepening the understanding of the performance of the SoS method for various unconstrained Boolean hypercube optimization problems, including the Max Cut problem. Recently, Lee, Prakash, de Wolf, and Yuen proved a lower bound on the SoS rank for SQFs of Ω(√{k(n-k)}) and conjectured the lower bound of Ω(n) by similarity to a polynomial representation of the n-bit OR function. Leveraging recent developments on Chebyshev polynomials, we refute the Lee-Prakash-de Wolf-Yuen conjecture and prove that the SoS rank for SQFs is at most O(√{nk}log(n)). We connect this result to two constrained Boolean hypercube optimization problems. First, we provide a degree O(√n) SoS certificate that matches the known SoS rank lower bound for an instance of Min Knapsack, a problem that was intensively studied in the literature. Second, we study an instance of the Set Cover problem for which Bienstock and Zuckerberg conjectured an SoS rank lower bound of n/4. We refute the Bienstock-Zuckerberg conjecture and provide a degree O(√nlog(n)) SoS certificate for this problem.

We introduce a method for proving bounds on the SoS rank based on Boolean Function Analysis and Approximation Theory. We apply our technique to improve upon existing results, thus making progress towards answering several open questions. We consider two questions by Laurent. First, finding what is the SoS rank of the linear representation of the set with no integral points. We prove that the SoS rank is between ceil[n/2] and ceil[~ n/2 +sqrt{n log{2n}} ~]. Second, proving the bounds on the SoS rank for the instance of the Min Knapsack problem. We show that the SoS rank is at least Omega(sqrt{n}) and at most ceil[{n+ 4 ceil[sqrt{n} ~]}/2]. Finally, we consider the question by Bienstock regarding the instance of the Set Cover problem. For this problem we prove the SoS rank lower bound of Omega(sqrt{n}).

We compare four key hierarchies for solving Constrained Polynomial Optimization Problems (CPOP) arising from semialgebraic proof systems: Sum of Squares (SOS), Sum of Diagonally Dominant Polynomials (SDSOS), Sum of Nonnegative Circuits (SONC), and the Sherali Adams (SA) hierarchies. We prove a collection of dependencies among these hierarchies both for general CPOPs and for optimization problems on the Boolean hypercube. Key results include for the general case that the SONC and SOS hierarchy are polynomially incomparable, while SDSOS is contained in SONC. On the Boolean hypercube, we show as a main result that Schmudgen-like versions of the hierarchies SDSOS*, SONC*, and SA* are polynomially equivalent. Moreover, we show that SA* is contained in any Schmudgen-like hierarchy that provides a O(n) degree bound.

We give two results concerning the power of the Sum-Of-Squares(SoS)/Lasserre hierarchy. For binary polynomial optimization problems of degree 2d and an odd number of variables n, we prove that (n+2d-1)/2 levels of the SoS/Lasserre hierarchy are necessary to provide the exact optimal value. This matches the recent upper bound result by Sakaue, Takeda, Kim and Ito. Additionally, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points. She showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull, and conjectured that the SoS/Lasserre rank for the same problem is n-1. We disprove this conjecture and derive lower and upper bounds for the rank.