Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Separating OR, SUM, and XOR Circuits



Magnus G. Find, Mika Goos, Matti Jarvisalo, Petteri Kaski, Miko Koivisto, Janne Korhonen


Given a boolean n x n matrix A we consider arithmetic circuits for computing the transformation x 7! Ax over different semirings. Namely, we study three circuit models: monotone OR-circuits, monotone SUM-circuits (addition of non-negative integers), and non-monotone XOR-circuits (addition modulo 2). Our focus is on separating OR-circuits from the two other models in terms of circuit complexity: (1) We show how to obtain matrices that admit OR-circuits of size O(n), but require SUM-circuits of size (n^(3/2)/log^2n). (2) We consider the task of rewriting a given OR-circuit as a XOR-circuit and prove that any subquadratic-time algorithm for this task violates the strong exponential time hypothesis.
Journal of Computer and System Sciences


arithmetic circuits, boolean arithmetic, idempotent arithmetic, monotone separations, rewriting


Find, M. , Goos, M. , Jarvisalo, M. , Kaski, P. , Koivisto, M. and Korhonen, J. (2016), Separating OR, SUM, and XOR Circuits, Journal of Computer and System Sciences, [online], (Accessed May 22, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created August 23, 2016, Updated November 10, 2018