Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > AUTHORS > MAURICE JANSEN:
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

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 >>> TR11-133 | 4th October 2011 Maurice Jansen, Rahul Santhanam #### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent 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 >>> TR10-118 | 27th July 2010 Maurice Jansen #### Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods Revisions: 2 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 >>> TR10-084 | 14th May 2010 Maurice Jansen, Youming Qiao, Jayalal Sarma #### Deterministic Identity Testing of Read-Once Algebraic Branching Programs 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 >>> TR10-015 | 8th February 2010 Maurice Jansen, Youming Qiao, Jayalal Sarma #### Deterministic Black-Box Identity Testing$\pi$-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$\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 >>>

ISSN 1433-8092 | Imprint