@article{FindGJKKK:JCSS2016,
title = {Separating {OR}, {SUM}, and {XOR} circuits},
author = {Magnus Find and Mika G\"o\"os and Matti J\"arvisalo and
Petteri Kaski and Mikko Koivisto and Janne H. Korhonen},
journal = {Journal of Computer and System Sciences},
volume = {82},
number = {5},
pages = {793--801},
year = {2016},
}
Abstract:
Given a boolean $n$ by $n$ matrix $A$ we consider arithmetic circuits for
computing the transformation $x\mapsto 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 these models
in terms of circuit complexity:
- We show how to obtain matrics that admit OR-circuits of size $O(n)$, but
require SUM-circuits of size $\Omega(n^{3/2}/\log^2n)$.
- 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.