Source author record

Maurice Jansen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2010arXiv

Deterministic Black-Box Identity Testing $π$ -Ordered Algebraic Branching Programs

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation $π$ of $n$ variables, for a $π$ -ordered ABP ( $π$ -OABP), for any directed path $p$ from source to sink, a variable can appear at most once on $p$ , and the order in which variables appear on $p$ must respect $π$ . An ABP $A$ is said to be of read $r$ , if any variable appears at most $r$ times in $A$ . Our main result pertains to the identity testing problem. Over any field $F$ and in the black-box model, i.e. given only query access to the polynomial, we have the following result: read $r$ $π$ -OABP computable polynomials can be tested in $\DTIME[2^{O(r\log r \cdot \log^2 n \log\log n)}]$. Our next set of results investigates the computational limitations of OABPs. It is shown that any OABP computing the determinant or permanent requires size $Ω(2^n/n)$ and read $Ω(2^n/n^2)$ . We give a multilinear polynomial $p$ in $2n+1$ variables over some specifically selected field $G$ , such that any OABP computing $p$ must read some variable at least $2^n$ times. We show that the elementary symmetric polynomial of degree $r$ in $n$ variables can be computed by a size $O(rn)$ read $r$ OABP, but not by a read $(r-1)$ OABP, for any $0 < 2r-1 \leq n$ . Finally, we give an example of a polynomial $p$ and two variables orders $π\neq π'$ , such that $p$ can be computed by a read-once $π$ -OABP, but where any $π'$ -OABP computing $p$ must read some variable at least $2^n$

preprint2009arXiv

Balancing Bounded Treewidth Circuits

Algorithmic tools for graphs of small treewidth are used to address questions in complexity theory. For both arithmetic and Boolean circuits, it is shown that any circuit of size $n^{O(1)}$ and treewidth $O(\log^i n)$ can be simulated by a circuit of width $O(\log^{i+1} n)$ and size $n^c$ , where $c = O(1)$ , if $i=0$ , and $c=O(\log \log n)$ otherwise. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size $n^{O(1)}$ and treewidth $k$ can be simulated by bounded fan-in arithmetic formulas of depth $O(k^2\log n)$ . From this we derive the analogous statement for syntactically multilinear arithmetic circuits, which strengthens a theorem of Mahajan and Rao. As another application, we derive that constant width arithmetic circuits of size $n^{O(1)}$ can be balanced to depth $O(\log n)$ , provided certain restrictions are made on the use of iterated multiplication. Also from our main construction, we derive that Boolean bounded fan-in circuits of size $n^{O(1)}$ and treewidth $k$ can be simulated by bounded fan-in formulas of depth $O(k^2\log n)$ . This strengthens in the non-uniform setting the known inclusion that $SC^0 \subseteq NC^1$ . Finally, we apply our construction to show that {\sc reachability} for directed graphs of bounded treewidth is in $LogDCFL$ .

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.

Maurice Jansen

Research overview

Is this your work?

2 publications

Deterministic Black-Box Identity Testing $π$ -Ordered Algebraic Branching Programs

Balancing Bounded Treewidth Circuits

See the researcher in context

Building this map preview

Maurice Jansen

Research overview

Is this your work?

2 publications

Deterministic Black-Box Identity Testing πππ-Ordered Algebraic Branching Programs

Balancing Bounded Treewidth Circuits

See the researcher in context

Building this map preview

Deterministic Black-Box Identity Testing $π$ -Ordered Algebraic Branching Programs