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

Published

Author(s)

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

Abstract

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.
Citation
Journal of Computer and System Sciences
Volume
82
Issue
5

Keywords

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

Citation

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], https://doi.org/10.1016/j.jcss.2016.01.001 (Accessed March 29, 2024)
Created August 23, 2016, Updated November 10, 2018