Separating OR, SUM, and XOR Circuits

Published

August 23, 2016

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

Pub Type

Journals

Download Paper

https://doi.org/10.1016/j.jcss.2016.01.001

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 December 26, 2024)