15 citations · 20 across the 16 of their papers we have counts for
26 papers
Vanishing Ideals and the Computational Tractability of Sum-of-Squares over Boolean Domains
Monaldo Mastrolilli
Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing identities over…
Robust Approximation and the Arity Barrier at Width Two
Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli
Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint langu…
Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems
Stefano Huber, Monaldo Mastrolilli
Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established fo…
Ideal Membership in Polynomial Calculus: Complexity and Reductions
Alex Bortolotti, Monaldo Mastrolilli
The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal <p_1, ..., p_m> of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f…
Integrality gap preserving reductions
Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, calle…
On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
Alex Bortolotti, Monaldo Mastrolilli, Marilena Palomba +1
The Sum-of-Squares (SoS) hierarchy is a powerful framework for polynomial optimization and proof complexity, offering tight semidefinite relaxations that capture many classical alg…