Researcher profile

Magnus Find

Magnus Find contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Computational Complexity

Trust snapshot

Quick read

Trust 15 - Baseline

3works

0followers

1topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2014arXiv

Cancellation-Free Circuits in Unbounded and Bounded Depth

We study the notion of "cancellation-free" circuits. This is a restriction of linear Boolean circuits (XOR circuits), but can be considered as being equivalent to previously studied models of computation. The notion was coined by Boyar and Peralta in a study of heuristics for a particular circuit minimization problem. They asked how large a gap there can be between the smallest cancellation-free circuit and the smallest linear circuit. We show that the difference can be a factor $Ω(n/\log^{2}n)$. This improves on a recent result by Sergeev and Gashkov who have studied a similar problem. Furthermore, our proof holds for circuits of constant depth. We also study the complexity of computing the Sierpinski matrix using cancellation-free circuits and give a tight $Ω(n\log n)$ lower bound.

preprint2013arXiv

Separating OR, SUM, and XOR Circuits

Given a boolean n by 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 \emph{separating} these models in terms of their circuit complexities. We give three results towards this goal: (1) We prove a direct sum type theorem on the monotone complexity of tensor product matrices. As a corollary, we obtain matrices that admit OR-circuits of size O(n), but require SUM-circuits of size Ω(n^{3/2}/\log^2n). (2) We construct so-called \emph{k-uniform} matrices that admit XOR-circuits of size O(n), but require OR-circuits of size Ω(n^2/\log^2n). (3) We consider the task of \emph{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.

preprint2012arXiv

Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators

We continue to study the notion of cancellation-free linear circuits. We show that every matrix can be computed by a cancellation- free circuit, and almost all of these are at most a constant factor larger than the optimum linear circuit that computes the matrix. It appears to be easier to prove statements about the structure of cancellation-free linear circuits than for linear circuits in general. We prove two nontrivial superlinear lower bounds. We show that a cancellation-free linear circuit computing the $n\times n$ Sierpinski gasket matrix must use at least 1/2 n logn gates, and that this is tight. This supports a conjecture by Aaronson. Furthermore we show that a proof strategy for proving lower bounds on monotone circuits can be almost directly converted to prove lower bounds on cancellation-free linear circuits. We use this together with a result from extremal graph theory due to Andreev to prove a lower bound of Ω(n^(2- ε)) for infinitely many $n \times n$ matrices for every $ε> 0$ for. These lower bounds for concrete matrices are almost optimal since all matrices can be computed with $O(n^2/\log n)$ gates.