All reports by Author Maurice Jansen:

__
TR11-135
| 9th October 2011
__

Maurice Jansen, Rahul Santhanam#### Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes

__
TR11-133
| 4th October 2011
__

Maurice Jansen, Rahul Santhanam#### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

__
TR10-118
| 27th July 2010
__

Maurice Jansen#### Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods

Revisions: 2

__
TR10-084
| 14th May 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Identity Testing of Read-Once Algebraic Branching Programs

__
TR10-015
| 8th February 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

Maurice Jansen, Rahul Santhanam

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

Maurice Jansen, Rahul Santhanam

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.

It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ...
more >>>

Maurice Jansen

For two polynomials $f \in \mathbb{F}[x_1, x_2, \ldots, x_n, y]$ and $p \in \mathbb{F}[x_1, x_2, \ldots, x_n]$, we say that $p$ is a root of $f$, if $f(x_1, x_2, \ldots, x_n, p) \equiv 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits ... more >>>

Maurice Jansen, Youming Qiao, Jayalal Sarma

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of ... more >>>

Maurice Jansen, Youming Qiao, Jayalal Sarma

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 $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>