E-Graph Research, Applications, Practices, and Human-factors Symposium

Research on and around e-graphs 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 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, work-in-progress talks, and peer-reviewed papers. 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

Call for Submissions

See the Call for Papers tab for information.

Event

The event will be co-located with PLDI on Tuesday, June 14, 2022.

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

Tue 14 Jun

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

09:00 - 10:00
OpeningEGRAPHS at Toucan +12h
Chair(s): Max Willsey University of Washington
09:00
5m
Day opening
Welcome
EGRAPHS
Max Willsey University of Washington
09:05
30m
Talk
Sketch-Guided Equality Saturation
EGRAPHS
Thomas Koehler University of Glasgow
Pre-print File Attached
09:35
25m
Talk
Synthesizing Mathematical Identities with E-graphs
EGRAPHS
Ian Briggs University of Utah, Pavel Panchekha University of Utah
Link to publication Pre-print
10:30 - 12:00
Thinking AlikeEGRAPHS at Toucan +12h
Chair(s): Max Willsey University of Washington
10:30
15m
Talk
Logging an Egg: Datalog on E-Graphs
EGRAPHS
Philip Zucker Draper Laboratory
Pre-print Media Attached
10:45
15m
Talk
Chasing an egg
EGRAPHS
Yihong Zhang University of Washington
Pre-print
11:00
15m
Talk
ECTAs: E-Graphs Better (at Encoding)
EGRAPHS
James Koppel Massachusetts Institute of Technology, USA, Zheng Guo University of California, San Diego, Edsko de Vries Well-Typed LLP, Armando Solar-Lezama Massachusetts Institute of Technology, Nadia Polikarpova University of California at San Diego
11:15
15m
Talk
E-Graphs, VSAs, and Tree Automata: a Rosetta StoneVirtual
EGRAPHS
Yisu Remy Wang University of Washington, James Koppel Massachusetts Institute of Technology, USA, Altan Haan OctoML, Josh Pollock MIT CSAIL
Link to publication Pre-print
11:30
15m
Talk
Equality Saturation as a Tactic for Proof Assistants
EGRAPHS
Andrés Goens the University of Edinburgh, Siddharth Bhat the University of Edinburgh
11:45
15m
Talk
Towards Optimising Certified Programs by Proof Rewriting
EGRAPHS
Kiran Gopinathan National University of Singapore, Ilya Sergey National University of Singapore
14:00 - 15:00
ApplicationsEGRAPHS at Toucan +12h
Chair(s): Chandrakana Nandi Certora, inc.
14:00
15m
Talk
Quiche: A Python Implementation of E-Graphs
EGRAPHS
Rebecca Swords Unaffiliated
14:15
15m
Talk
Optimizing Large Integer Multiplier on FPGAs Using Equality SaturationVirtual
EGRAPHS
Ecenur Ustun Cornell University, Jiaqi Yin University of Utah, Zhiru Zhang Cornell University, USA
14:30
15m
Talk
Wasm-mutate: Fuzzing WebAssembly Compilers with E-GraphsVirtual
EGRAPHS
Javier Cabrera Arteaga KTH Royal Institute of Technology, Nicholas Fitzgerald Fastly Inc., Martin Monperrus KTH Royal Institute of Technology, Benoit Baudry KTH
Pre-print
14:45
15m
Talk
QuEgg: Automatic Optimization of Quantum Circuits Using Equality Graphs
EGRAPHS
Spencer King Unaffiliated
15:30 - 16:30
ExtensionsEGRAPHS at Toucan +12h
Chair(s): Zachary Tatlock University of Washington
15:30
15m
Talk
On the Optimization of Equivalent Concurrent ComputationsVirtual
EGRAPHS
Henrich Lauko Trail of Bits, Lukáš Korenčik Trail of Bits, Peter Goodman Trail of Bits
15:45
15m
Talk
Abstract Interpretation on E-Graphs
EGRAPHS
Samuel Coward Imperial College London, UK, George A. Constantinides Imperial College London, UK, Theo Drane Intel Corporation, USA
Pre-print
16:00
15m
Talk
Colored E-Graph: Supporting Multiple Equivalence Relations with Resource SharingVirtual
EGRAPHS
Eytan Singher Technion - Israel Institute of Technology, Shachar Itzhaky Technion
16:15
15m
Talk
Toward a Unified Framework for Program Optimization, Bug-Finding, and Repair
EGRAPHS
Jordan Schmerge Colorado School of Mines, Jake Vossen Colorado School of Mines, Jedidiah McClurg Colorado School of Mines
21:00 - 22:00
OpeningEGRAPHS at Toucan
21:00
5m
Day opening
Welcome
EGRAPHS
Max Willsey University of Washington
21:05
30m
Talk
Sketch-Guided Equality Saturation
EGRAPHS
Thomas Koehler University of Glasgow
Pre-print File Attached
21:35
25m
Talk
Synthesizing Mathematical Identities with E-graphs
EGRAPHS
Ian Briggs University of Utah, Pavel Panchekha University of Utah
Link to publication Pre-print
22:30 - 00:00
Thinking AlikeEGRAPHS at Toucan
22:30
15m
Talk
Logging an Egg: Datalog on E-Graphs
EGRAPHS
Philip Zucker Draper Laboratory
Pre-print Media Attached
22:45
15m
Talk
Chasing an egg
EGRAPHS
Yihong Zhang University of Washington
Pre-print
23:00
15m
Talk
ECTAs: E-Graphs Better (at Encoding)
EGRAPHS
James Koppel Massachusetts Institute of Technology, USA, Zheng Guo University of California, San Diego, Edsko de Vries Well-Typed LLP, Armando Solar-Lezama Massachusetts Institute of Technology, Nadia Polikarpova University of California at San Diego
23:15
15m
Talk
E-Graphs, VSAs, and Tree Automata: a Rosetta StoneVirtual
EGRAPHS
Yisu Remy Wang University of Washington, James Koppel Massachusetts Institute of Technology, USA, Altan Haan OctoML, Josh Pollock MIT CSAIL
Link to publication Pre-print
23:30
15m
Talk
Equality Saturation as a Tactic for Proof Assistants
EGRAPHS
Andrés Goens the University of Edinburgh, Siddharth Bhat the University of Edinburgh
23:45
15m
Talk
Towards Optimising Certified Programs by Proof Rewriting
EGRAPHS
Kiran Gopinathan National University of Singapore, Ilya Sergey National University of Singapore

Wed 15 Jun

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

02:00 - 03:00
ApplicationsEGRAPHS at Toucan
02:00
15m
Talk
Quiche: A Python Implementation of E-Graphs
EGRAPHS
Rebecca Swords Unaffiliated
02:15
15m
Talk
Optimizing Large Integer Multiplier on FPGAs Using Equality SaturationVirtual
EGRAPHS
Ecenur Ustun Cornell University, Jiaqi Yin University of Utah, Zhiru Zhang Cornell University, USA
02:30
15m
Talk
Wasm-mutate: Fuzzing WebAssembly Compilers with E-GraphsVirtual
EGRAPHS
Javier Cabrera Arteaga KTH Royal Institute of Technology, Nicholas Fitzgerald Fastly Inc., Martin Monperrus KTH Royal Institute of Technology, Benoit Baudry KTH
Pre-print
02:45
15m
Talk
QuEgg: Automatic Optimization of Quantum Circuits Using Equality Graphs
EGRAPHS
Spencer King Unaffiliated
03:30 - 04:30
ExtensionsEGRAPHS at Toucan
03:30
15m
Talk
On the Optimization of Equivalent Concurrent ComputationsVirtual
EGRAPHS
Henrich Lauko Trail of Bits, Lukáš Korenčik Trail of Bits, Peter Goodman Trail of Bits
03:45
15m
Talk
Abstract Interpretation on E-Graphs
EGRAPHS
Samuel Coward Imperial College London, UK, George A. Constantinides Imperial College London, UK, Theo Drane Intel Corporation, USA
Pre-print
04:00
15m
Talk
Colored E-Graph: Supporting Multiple Equivalence Relations with Resource SharingVirtual
EGRAPHS
Eytan Singher Technion - Israel Institute of Technology, Shachar Itzhaky Technion
04:15
15m
Talk
Toward a Unified Framework for Program Optimization, Bug-Finding, and Repair
EGRAPHS
Jordan Schmerge Colorado School of Mines, Jake Vossen Colorado School of Mines, Jedidiah McClurg Colorado School of Mines
09:00 - 10:10
Keynote: Emery BergerPLDI at Kon-Tiki +12h
Chair(s): Isil Dillig University of Texas at Austin
09:00
10m
Other
Welcome to PLDI 2022
PLDI
Isil Dillig University of Texas at Austin, Ranjit Jhala University of California at San Diego; Amazon Web Services
09:10
60m
Keynote
Getting Your Research Adopted
PLDI
Emery D. Berger University of Massachusetts Amherst
Pre-print Media Attached
18:00 - 19:00
PLDI 2022 ReceptionPLDI at Beach North
18:00
60m
Social Event
PLDI 2022 Reception (sponsored by WhatsApp by Meta)social
PLDI

21:00 - 22:10
Keynote: Emery BergerPLDI at Kon-Tiki
21:00
10m
Other
Welcome to PLDI 2022
PLDI
Isil Dillig University of Texas at Austin, Ranjit Jhala University of California at San Diego; Amazon Web Services
21:10
60m
Keynote
Getting Your Research Adopted
PLDI
Emery D. Berger University of Massachusetts Amherst
Pre-print Media Attached

Accepted Papers

Title
Abstract Interpretation on E-Graphs
EGRAPHS
Pre-print
Chasing an egg
EGRAPHS
Pre-print
Colored E-Graph: Supporting Multiple Equivalence Relations with Resource SharingVirtual
EGRAPHS
ECTAs: E-Graphs Better (at Encoding)
EGRAPHS
E-Graphs, VSAs, and Tree Automata: a Rosetta StoneVirtual
EGRAPHS
Link to publication Pre-print
Equality Saturation as a Tactic for Proof Assistants
EGRAPHS
Logging an Egg: Datalog on E-Graphs
EGRAPHS
Pre-print Media Attached
On the Optimization of Equivalent Concurrent ComputationsVirtual
EGRAPHS
Optimizing Large Integer Multiplier on FPGAs Using Equality SaturationVirtual
EGRAPHS
QuEgg: Automatic Optimization of Quantum Circuits Using Equality Graphs
EGRAPHS
Quiche: A Python Implementation of E-Graphs
EGRAPHS
Sketch-Guided Equality Saturation
EGRAPHS
Pre-print File Attached
Synthesizing Mathematical Identities with E-graphs
EGRAPHS
Link to publication Pre-print
Toward a Unified Framework for Program Optimization, Bug-Finding, and Repair
EGRAPHS
Towards Optimising Certified Programs by Proof Rewriting
EGRAPHS
Wasm-mutate: Fuzzing WebAssembly Compilers with E-GraphsVirtual
EGRAPHS
Pre-print
Welcome
EGRAPHS

Call for Talks / Papers

The symposium welcomes paper and abstract submissions on the topics listed in the program description. All submissions and reviews will take place on the EGRAPHS 2022 HotCRP.

Talk Abstracts

We invite submission for talks broadly, including talks that may cover already published or in-progress work. Submissions should be in the form of a 2-page (excluding references, same format as PLDI) extended abstract that describes the key problems addressed and/or reusable insights from the proposed talk.

You may omit the abstract and keyword sections from the submitted PDF.

Talks are intended to foster discussion between members of the e-graph community. The program will include time for open-ended discussion inspired by the talks as well as Q&A.

Talk proposals will not be published in the ACM DL, so they may cover work that is or will be published elsewhere.

Talk proposals are not anonymous and will be reviewed single-blind (the reviewers will see the author list), so feel free to use identifying information in your submission. Make sure to uncheck the “Anonymous submission” box in HotCRP when submitting a talk proposal.

Research Papers

We also invite research papers describing novel results on any of the subject areas in the program description. Reviewers will evaluate papers on the significance of their results and the clarity of exposition. Papers should clearly state how their novel contributions relate to previous work.

Research papers will be subject to double-blind peer review, so submissions must be anonymized.

Papers should be no more than 8 pages (excluding references) in the same format as PLDI (SIGPLAN, double column). Research paper submissions should not be simultaneously under submission/review at any other venue.

Accepted research papers will be published and available on the ACM Digital Library. We encourage authors to make a preprint freely available as well.

Questions? Use the EGRAPHS contact form.