Separating OR, SUM, and XOR circuits

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

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

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:We show how to obtain matrices that admit OR-circuits of size O(n), but require SUM-circuits of size Ω(n3/2/log2 n).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.

Original languageEnglish
Pages (from-to)793-801
Number of pages9
JournalJOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume82
Issue number5
DOIs
Publication statusPublished - 1 Aug 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • Arithmetic circuits
  • Boolean arithmetic
  • Idempotent arithmetic
  • Monotone separations
  • Rewriting

Fingerprint Dive into the research topics of 'Separating OR, SUM, and XOR circuits'. Together they form a unique fingerprint.

Cite this