IWLS 2025 Competition on Boolean Circuit Synthesis

The goal of this project is to participate in the IWLS 2025 Programming Contest on Boolean Circuit Synthesis. In this competition, the participants are given the truth tables of 200 Boolean functions and the goal is to synthesize efficient circuits (over the $\{\wedge ,\mathrm{\neg }\}$ basis) computing these functions. The smaller are the circuits, the higher is the rank.

Report ​

During three months, we have been designing and implementing various heuristics for the circuit synthesis problem. Mostly, we have been developing the following two areas.

1. Deciphering functions. Since it is hard to generate a circuit for an arbitrary function, knowing actual meaning of a function would help, so we invested a lot of resources into that area. We looked at different characteristics (number of zeros, injectivity), also drew a picture for each output, where we split the input into two parts, interpret each one as a number, and a pixel $(i,j)$ gets a color depending on an output when the first number is $i$ and the second one is $j$. For some functions we managed to see what they do, for some we got some insights and made a final circuit using ABC.

2. Circuit synthesis and simplification. As a baseline, we used the ABC tool. As was discovered this year, multiple calls of ABC may improve the circuit. Once the circuit was improved after more than 4500 calls. CIOPS and eSLIM were also used, simplifying some circuits by 40%. For a few benchmarks, we used our new tool that converts a Python code into a circuit. Currently, it supports all basic operations, but does not support loops and RAM access.

As a result, we got the third place in the competition.

The report of our team can be found here. We are planning to make our code open source as part of the Cirbo package.