Source author record

Magnus Find

Magnus Find appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

What is connected

3works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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.