Random Sampling in Computational Algebra: Helly Numbers and Violator Spaces

Abstract: Clarkson’s sampling algorithm was the first expected linear-time algorithm for solving linear programs with a fixed number of variables. It was later shown to apply to more general non-linear geometric problems called LP-type problems. Finally, Gartner et al. proposed Violator Spaces as the most general framework under which Clarkson’s algorithm applies.

We show that two polynomial ideal problems can be formulated to fit into the Violator Space framework, thus enabling us to apply Clarkson’s algorithm to solve them. We employ a Helly-type result for algebraic varieties for one of the problems.

This talk is based on joint work with Jesus A. De Loera and Sonja Petrovic.

Event Topic

Nonlinear Algebra and Statistics (NLASTATS)