Separating OR, SUM, and XOR circuits

作者：

Highlights：

• We study circuits for linear maps defined by n times n Boolean matrices.

• We consider three circuit models: OR-circuits, SUM-circuits, and XOR-circuits.

• Our focus is on separating these models in terms of their circuit complexities.

• We obtain matrices with OR-circuits of size O(n) which require large SUM-circuits.

• We prove a conditional quadratic lower bound for an OR–XOR circuit rewriting task.

摘要

•We study circuits for linear maps defined by n times n Boolean matrices.•We consider three circuit models: OR-circuits, SUM-circuits, and XOR-circuits.•Our focus is on separating these models in terms of their circuit complexities.•We obtain matrices with OR-circuits of size O(n) which require large SUM-circuits.•We prove a conditional quadratic lower bound for an OR–XOR circuit rewriting task.

论文关键词：Arithmetic circuits,Boolean arithmetic,Idempotent arithmetic,Monotone separations,Rewriting

论文评审过程：Received 16 March 2015, Revised 17 November 2015, Accepted 15 January 2016, Available online 10 March 2016, Version of Record 1 April 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.01.001