This program is tentative and subject to change.

Thu 20 Jan 2022 15:30 - 15:55 at Salon I - Systems Chair(s): Arthur Azevedo de Amorim

We present a new approach to e-matching based on relational join; in particular, we apply recent database query execution techniques to guarantee worst-case optimal run time. Compared to the conventional backtracking approach that always searches the e-graph “top down”, our new relational e-matching approach can better exploit pattern structure by searching the e-graph according to an optimized query plan. We also establish the first data complexity result for e-matching, bounding run time as a function of the e-graph size and output size. We prototyped and evaluated our technique in the state-of-the-art egg e-graph framework. Compared to a conventional baseline, relational e-matching is simpler to implement and orders of magnitude faster in practice.

This program is tentative and subject to change.

Thu 20 Jan

Displayed time zone: Eastern Time (US & Canada) change

15:05 - 16:20
SystemsPOPL at Salon I
Chair(s): Arthur Azevedo de Amorim Boston University, USA
15:05
25m
Research paper
Isolation Without Taxation: Near Zero Cost Transitions for WebAssembly and SFIInPerson
POPL
Matthew Kolosick University of California, San Diego, Shravan Ravi Narayan University of California, San Diego, Evan Johnson University of California, San Diego, Conrad Watt University of Cambridge, UK, Michael LeMay Intel Labs, Deepak Garg MPI-SWS, Ranjit Jhala University of California at San Diego, Deian Stefan University of California at San Diego, USA
15:30
25m
Research paper
Relational E-MatchingRemote
POPL
Yihong Zhang University of Washington, Yisu Remy Wang University of Washington, Max Willsey University of Washington, Zachary Tatlock University of Washington
Pre-print
15:55
25m
Research paper
Linked visualisations via Galois dependenciesRemote
POPL
Roly Perera The Alan Turing Institute/University of Bristol, Minh Nguyen University of Bristol, Tomas Petricek University of Kent, Meng Wang University of Bristol
Pre-print
Hide past events