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