DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2012.519

Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes

Authors: Maurice Jansen and Rahul Santhanam

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract

We associate to each Boolean language complexity class C the algebraic class a.C consisting of families of polynomials {f_n} for which the evaluation problem over the integers is in C. We prove the following lower bound and randomness-to-hardness results: 1. If polynomial identity testing (PIT) is in NSUBEXP then a.NEXP does not have poly size constant-free arithmetic circuits. 2. a.NEXP^RP does not have poly size constant-free arithmetic circuits. 3. For every fixed k, a.MA does not have arithmetic circuits of size n^k. Items 1 and 2 strengthen two results due to (Kabanets and Impagliazzo, 2004). The third item improves a lower bound due to (Santhanam, 2009). We consider the special case low-PIT of identity testing for (constant-free) arithmetic circuits with low formal degree, and give improved hardness-to-randomness trade-offs that apply to this case. Combining our results for both directions of the hardness-randomness connection, we demonstrate a case where derandomization of PIT and proving lower bounds are equivalent. Namely, we show that low-PIT is in i.o-NTIME[2^{n^{o(1)}}]/n^{o(1)} if and only if there exists a family of multilinear polynomials in a.NE/lin that requires constant-free arithmetic circuits of super-polynomial size and formal degree.

Cite as

Maurice Jansen and Rahul Santhanam. Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 519-530, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.STACS.2012.519,
  author =	{Jansen, Maurice and Santhanam, Rahul},
  title =	{{Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{519--530},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.519},
  URN =		{urn:nbn:de:0030-drops-34307},
  doi =		{10.4230/LIPIcs.STACS.2012.519},
  annote =	{Keywords: Computational Complexity, Circuit Lower Bounds, Polynomial Identity Testing, Derandomization}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2010.296

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

Authors: Maurice Jansen, Youming Qiao, and Jayalal Sarma M.N.

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. An ABP is given by a layered directed acyclic graph with source $s$ and sink $t$, whose edges are labeled by variables taken from the set $\{x_1, x_2, \ldots, x_n\}$ or field constants. It computes the sum of weights of all paths from $s$ to $t$, where the weight of a path is defined as the product of edge-labels on the path. Given a permutation $\pi$ of the $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from $s$ to $t$, a variable can appear at most once on $p$, and the order in which variables appear on $p$ must respect $\pi$. One can think of OABPs as being the arithmetic analogue of ordered binary decision diagrams (OBDDs). We say an ABP $A$ is of read $r$, if any variable appears at most $r$ times in $A$. Our main result pertains to the polynomial identity testing problem, i.e. the problem of deciding whether a given $n$-variate polynomial is identical to the zero polynomial or not. We prove that over any field $\F$, and in the black-box model, i.e. given only query access to the polynomial, read $r$ $\pi$-OABP computable polynomials can be tested in $\DTIME[2^{O(r\log r \cdot \log^2 n \log\log n)}]$. In case $\F$ is a finite field, the above time bound holds provided the identity testing algorithm is allowed to make queries to extension fields of $\F$. To establish this result, we combine some basic tools from algebraic geometry with ideas from derandomization in the Boolean domain. Our next set of results investigates the computational limitations of OABPs. It is shown that any OABP computing the determinant or permanent requires size $\Omega(2^n/n)$ and read $\Omega(2^n/n^2)$. We give a multilinear polynomial $p$ in $2n+1$ variables over some specifically selected field $\mathbb{G}$, such that any OABP computing $p$ must read some variable at least $2^n$ times. We prove a strict separation for the computational power of read $(r-1)$ and read $r$ OABPs. Namely, 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 $\pi \neq \pi'$, such that $p$ can be computed by a read-once $\pi$-OABP, but where any $\pi'$-OABP computing $p$ must read some variable at least $2^n$ times.

Cite as

Maurice Jansen, Youming Qiao, and Jayalal Sarma M.N.. Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 296-307, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.FSTTCS.2010.296,
  author =	{Jansen, Maurice and Qiao, Youming and Sarma M.N., Jayalal},
  title =	{{Deterministic Black-Box Identity Testing \$pi\$-Ordered Algebraic Branching Programs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{296--307},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.296},
  URN =		{urn:nbn:de:0030-drops-28728},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.296},
  annote =	{Keywords: ordered algebraic branching program, polynomial identity testing}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2477

Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Authors: Maurice Jansen

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

Kabanets and Impagliazzo \cite{KaIm04} show how to decide the circuit polynomial identity testing problem (CPIT) in deterministic subexponential time, assuming hardness of some explicit multilinear polynomial family $\{f_m\}_{m \geq 1}$ for arithmetic circuits. In this paper, a special case of CPIT is considered, namely non-singular matrix completion ($\NSMC$) under a low-individual-degree promise. For this subclass of problems it is shown how to obtain the same deterministic time bound, using a weaker assumption in terms of the {\em determinantal complexity} $\dcomp(f_m)$ of $f_m$. Building on work by Agrawal \cite{Agr05}, hardness-randomness tradeoffs will also be shown in the converse direction, in an effort to make progress on Valiant's $\VP$ versus $\VNP$ problem. To separate $\VP$ and $\VNP$, it is known to be sufficient to prove that the determinantal complexity of the $m\times m$ permanent is $m^{\omega(\log m)}$. In this paper it is shown, for an appropriate notion of explicitness, that the existence of an explicit multilinear polynomial family $\{f_m\}_{m \geq 1}$ with $\dcomp(f_m) = m^{\omega(\log m)}$ is equivalent to the existence of an efficiently computable {\em generator} $\{G_n\}_{n\geq 1}$ {\em for} multilinear $\NSMC$ with seed length $O(n^{1/\sqrt{\log n}})$. The latter is a combinatorial object that provides an efficient deterministic black-box algorithm for $\NSMC$. ``Multilinear $\NSMC$'' indicates that $G_n$ only has to work for matrices $M(x)$ of $poly(n)$ size in $n$ variables, for which $\det(M(x))$ is a multilinear polynomial.

Cite as

Maurice Jansen. Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 465-476, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jansen:LIPIcs.STACS.2010.2477,
  author =	{Jansen, Maurice},
  title =	{{Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{465--476},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2477},
  URN =		{urn:nbn:de:0030-drops-24770},
  doi =		{10.4230/LIPIcs.STACS.2010.2477},
  annote =	{Keywords: Computational complexity, arithmetic circuits, hardness-randomness tradeoffs, identity testing, determinant versus permanent}
}

Search Results

Documents authored by Jansen, Maurice

Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes

Abstract

Cite as

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

Abstract

Cite as

Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Abstract

Cite as

Thanks for your feedback!

Could not send message