PLDI 2024
Mon 24 - Fri 28 June 2024 Copenhagen, Denmark

This program is tentative and subject to change.

Thu 27 Jun 2024 11:20 - 11:40 at Finland / Norway - Formally Verified

This paper proposes a novel method to efficiently solve infeasible low-dimensional linear programs (LDLPs) with billions of constraints and a small number of unknown variables, where all the constraints cannot be satised simultaneously. We focus on infeasible linear programs generated in the RLibm project for creating correctly rounded math libraries. Specifcally, we are interested in generating a floating point solution that satisfies the maximum number of constraints. None of the existing methods can solve such large linear programs while producing floating point solutions.

We observe that the convex hull can serve as an intermediate representation (IR) for solving infeasible LDLPs using the geometric duality between linear programs and convex hulls. Specifically, some of the constraints that correspond to points on the convex hull are precisely those constraints that make the linear program infeasible. Our key idea is to split the entire set of constraints into two subsets using the convex hull IR: (a) a set X of feasible constraints and (b) a superset V of infeasible constraints. Using the special structure of the RLibm constraints and the presence of a method to check whether a system is feasible or not, we identify a superset of infeasible constraints by computing the convex hull in 2-dimensions. Subsequently, we identify the key constraints (i.e., basis constraints) in the set of feasible constraints X and use them to create a new linear program whose solution identifies the maximum set of constraints satisfiable in V while satisfying all the constraints in X. This new solver enabled us to improve the performance of the resulting RLibm polynomials while solving the corresponding linear programs significantly faster.

This program is tentative and subject to change.

Thu 27 Jun

Displayed time zone: Windhoek change

10:40 - 12:20
10:40
20m
Talk
The Functional Essence of Imperative Binary Search Trees
PLDI Research Papers
Anton Lorenzen University of Edinburgh, Daan Leijen Microsoft Research, Wouter Swierstra Utrecht University, Netherlands, Sam Lindley University of Edinburgh
DOI Pre-print
11:00
20m
Talk
Quiver: Guided Abductive Inference of Separation Logic Specifications in Coq
PLDI Research Papers
Simon Spies MPI-SWS, Lennard Gäher MPI-SWS, Michael Sammler MPI-SWS, Derek Dreyer MPI-SWS
DOI
11:20
20m
Talk
Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate Representation
PLDI Research Papers
Mridul Aanjaneya Rutgers University, Santosh Nagarakatte Rutgers University
DOI Pre-print
11:40
20m
Talk
Live Verification in an Interactive Proof Assistant
PLDI Research Papers
Samuel Gruetter Massachusetts Institute of Technology, Viktor Fukala Massachusetts Institute of Technology, Adam Chlipala Massachusetts Institute of Technology
DOI
12:00
20m
Talk
Predictable Verification using Intrinsic Definitions
PLDI Research Papers
Adithya Murali University of Illinois at Urbana-Champaign, Cody Rivera University of Illinois at Urbana-Champaign, P. Madhusudan University of Illinois at Urbana-Champaign
DOI