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

Research in the EGRAPHS Community has recently exploded in both quantity and diversity. The data structure that powers SMT solvers is now seeing use in synthesis, optimization, and verification via equality saturation and related techniques. In addition to recent advances in the core data structure and techniques, researchers and practitioners are applying e-graphs to domains such as compilers, floating point accuracy, test generation, computational fabrication, automatic vectorization, deep learning compute graphs, symbolic computation, and more.

The third EGRAPHS workshop will bring together those working on and with e-graphs, providing a collaborative venue to share work that advances e-graphs as a broadly applicable technique in programming languages or other fields of computing. The program will contain a mix of invited speakers and work-in-progress talks. The symposium seeks papers on a diverse range of topics including (but not limited to):

  • e-graphs as data structures and their related algorithms
  • equality saturation and other e-graph based rewriting approaches
  • applications of e-graphs and/or equality saturation, whether in programming languages or other fields
  • tools/frameworks that facilitate the use of e-graphs and associated techniques
  • investigations into the human-facing aspects using e-graph-based toolkits including error reporting, debugging, and visualization
  • other frameworks for optimizing/analyzing programs in an equational manner

Accepted submissions will not be placed on the ACM DL, so we allow and encourage in-progress or already published relevant work to be presented.

This program is tentative and subject to change.

You're viewing the program in a time zone which is different from your device's time zone change time zone

Mon 24 Jun

Displayed time zone: Windhoek change

09:00 - 10:10
1. WelcomeEGRAPHS at Helsinki
09:00
10m
Talk
Welcome
EGRAPHS
Max Willsey UC Berkeley
09:10
30m
Talk
E-graphs and Automated Reasoning: Looking back to look forward
EGRAPHS
Pre-print
09:40
30m
Talk
Equivalence Hypergraphs: E-Graphs for Monoidal Theories
EGRAPHS
Aleksei Tiurin University of Birmingham, Chris Barrett University of Oxford, Dan Ghica Huawei Research and University of Birmingham
10:40 - 12:20
2. ImplementationEGRAPHS at Helsinki
10:40
25m
Talk
Slotted E-Graphs
EGRAPHS
Rudi Schneider TU Berlin, Thomas Koehler INRIA, Michel Steuwer Technische Universität Berlin
Pre-print
11:05
25m
Talk
Towards Relational Contextual Equality Saturation
EGRAPHS
Tyler Hou University of California, Berkeley, Shadaj Laddad University of California at Berkeley, Joseph M. Hellerstein UC Berkeley
11:30
25m
Talk
Performant Dynamically Typed E-Graphs in Pure Julia
EGRAPHS
Alessandro Cheli PlantingSpace, Niklas Heim Czech Technical University
Pre-print
11:55
25m
Talk
EGSTRA: E-Graph-Based Strategy for Test Suite Reduction and Abstraction
EGRAPHS
Sabrina Reis Lawrence Livermore National Laboratory, Matthew Sottile Lawrence Livermore National Laboratory
13:40 - 15:20
3. ApplicationsEGRAPHS at Helsinki
13:40
25m
Talk
Powered by Less: Low Power Circuit Synthesis
EGRAPHS
Samuel Coward Imperial College London, UK / Intel Corporation, Theo Drane Intel Corporation, USA, Emiliano Morini Intel Corporation, George A. Constantinides Imperial College London, UK
14:05
25m
Talk
Algorithm-Aware Hardware Optimization using E-Graph Rewriting: how should we marry software and hardware?
EGRAPHS
Jianyi Cheng University of Cambridge, Samuel Coward Imperial College London, UK / Intel Corporation, Rafael Barbalho Intel Corporation, Theo Drane Intel Corporation, USA
Link to publication DOI
14:30
25m
Talk
Loop Saturation for Scalable High-Level Synthesis
EGRAPHS
Camille Bossut Georgia Institute of Technology, Qirun Zhang Georgia Institute of Technology, Cong "Callie" Hao Georgia Institute of Technology
14:55
25m
Talk
SpEQ: Translation of Sparse Codes using Equivalences
EGRAPHS
Avery Laird University of Toronto, Bangtian Liu University of Toronto, Nikolaj Bjørner Microsoft Research, Maryam Mehri Dehnavi University of Toronto
16:00 - 17:40
4. VerificationEGRAPHS at Helsinki
16:00
25m
Talk
Automated Proof Generation for Associative and Distributive Rewriting with E-Graphs
EGRAPHS
Adrian Lehmann University of Chicago, Ben Caldwell University of Chicago, John Reppy University of Chicago, USA, Robert Rand University of Chicago
16:25
25m
Talk
superVer: Verifying Probabilistic Independence of Systems of Expressions using Equality Saturation
EGRAPHS
Alexander Treff University of Lübeck, Pajam Pauls University of Lübeck, Maximilian Orlt TU Darmstadt
16:50
25m
Talk
Bridging Syntax and Semantics of Lean Expressions in E-Graphs
EGRAPHS
Marcus Rossel Technische Universität Dresden, Andrés Goens University of Amsterdam
Pre-print
17:15
25m
Talk
Disequalities in E-Graphs: An Experiment
EGRAPHS
George Zakhour University of St. Gallen, Pascal Weisenburger University of St. Gallen, Guido Salvaneschi University of St. Gallen

Accepted Papers

Title
Algorithm-Aware Hardware Optimization using E-Graph Rewriting: how should we marry software and hardware?
EGRAPHS
Link to publication DOI
Automated Proof Generation for Associative and Distributive Rewriting with E-Graphs
EGRAPHS
Bridging Syntax and Semantics of Lean Expressions in E-Graphs
EGRAPHS
Pre-print
Disequalities in E-Graphs: An Experiment
EGRAPHS
E-graphs and Automated Reasoning: Looking back to look forward
EGRAPHS
Pre-print
EGSTRA: E-Graph-Based Strategy for Test Suite Reduction and Abstraction
EGRAPHS
Equivalence Hypergraphs: E-Graphs for Monoidal Theories
EGRAPHS
Loop Saturation for Scalable High-Level Synthesis
EGRAPHS
Performant Dynamically Typed E-Graphs in Pure Julia
EGRAPHS
Pre-print
Powered by Less: Low Power Circuit Synthesis
EGRAPHS
Slotted E-Graphs
EGRAPHS
Pre-print
SpEQ: Translation of Sparse Codes using Equivalences
EGRAPHS
superVer: Verifying Probabilistic Independence of Systems of Expressions using Equality Saturation
EGRAPHS
Towards Relational Contextual Equality Saturation
EGRAPHS

Call for Presentations

We invite submissions for talks broadly, including talks that may cover already published or in-progress work. Submissions should be in the form of a 2 to 6 page extended abstract that describes the key problems addressed and/or reusable insights from the proposed talk. Links to preprints, repos, demos, or other media are encouraged!

We welcome submissions from academic, industrial, or independent researchers and practitioners. Talks are intended to foster discussion between members of the e-graph community. The program will include time for Q&A as well as open-ended discussion inspired by the talks.

Submissions and review will take place on HotCRP. Submissions are not anonymous.

At least one author is expected to attend the workshop and present in person.

Deadline is in the anywhere-on-earth timezone.

Questions? Use the EGRAPHS contact form.