Abstract. We propose an approach to graph sparsification based on the idea of preserving the smallest [Formula: see text] eigenvalues and eigenvectors of the graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph [Formula: see text] that have the same first [Formula: see text] eigenvalues (and eigenvectors) as [Formula: see text] is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of [Formula: see text]. Various families of graphs illustrate our construction.

The reconstruction of a 3-dimensional scene from (noisy) camera images is a routine task in computer vision. This problem encompasses a number of interesting mathematical questions with deep and old roots in projective geometry, which makes them amenable to tools from algebraic geometry. In this article I will address two foundational questions that revolve around the existence of a reconstruction from two camera images. The results involve real and semialgebraic geometry, as well as classical algebraic geometry and invariant theory. This article is a written account of my talk at ISSAC 2023.

The multiview variety of an arrangement of cameras is the Zariski closure of the images of world points in the cameras. The prime vanishing ideal of this complex projective variety is called the multiview ideal. We show that the bifocal and trifocal polynomials from the cameras generate the multiview ideal when the foci are distinct. In the computer vision literature, many sets of (determinantal) polynomials have been proposed to describe the multiview variety. We establish precise algebraic relationships between the multiview ideal and these various ideals. When the camera foci are noncoplanar, we prove that the ideal of bifocal polynomials saturate to give the multiview ideal. Finally, we prove that all the ideals we consider coincide when dehomogenized, to cut out the space of finite images.

In this paper we introduce a natural model for the realization space of a polytope up to projective equivalence which we call the slack realization space of the polytope. The model arises from the positive part of an algebraic variety determined by the slack ideal of the polytope. This is a saturated determinantal ideal that encodes the combinatorics of the polytope. We also derive a new model of the realization space of a polytope from the positive part of the variety of a related ideal. The slack ideal offers an effective computational framework for several classical questions about polytopes such as rational realizability, nonprescribability of faces, and realizability of combinatorial polytopes.