Separating OR, SUM, and XOR Circuits

Find, Magnus; Göös, Mika; Järvisalo, Matti; Kaski, Petteri; Koivisto, Mikko; Korhonen, Janne

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

Journal Article

Separating OR, SUM, and XOR Circuits

Published: August 23, 2016
Citation: Journal of Computer and System Sciences vol. 82, no. 5, (August 2016) pp. 793-801

Author(s)

Magnus Find (NIST), Mika Göös (University of Toronto), Matti Järvisalo (University of Helsinki), Petteri Kaski (Aalto University), Mikko Koivisto (University of Helsinki), Janne Korhonen (University of Helsinki)

Abstract

Given a boolean n × n matrix A we consider arithmetic circuits for computing the transformation x ↦ 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²n) .

(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.

Keywords

boolean arithmetic; idempotent arithmetic; monotone separations; arithmetic circuits; rewriting

Control Families

None selected

Documentation

Publication:
Journal Article (DOI)

Supplemental Material:
Preprint (pdf)

Document History:
08/23/16: Journal Article (Final)