Zohar Karnin, Amir Shpilka

In this paper we consider the problem of determining whether an

unknown arithmetic circuit, for which we have oracle access,

computes the identically zero polynomial. Our focus is on depth-3

circuits with a bounded top fan-in. We obtain the following

results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

Nader Bshouty

In this paper we first show that Tester for an $F$-algebra $A$

and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear

algorithm for the product of elements in $A$

(see Algebraic

complexity theory. vol. 315, Springer-Verlag). Our

result is constructive in deterministic polynomial time. ...
more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of ... more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. ... more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost $(nw)^{O(\log n)}$, where $n$ is the number of variables and $w$ is the width of ... more >>>

Guillaume Lagarde, Guillaume Malod

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-

alize algebraic branching programs (ABP). This model is called unambiguous because it captures the

polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-

morphic).

We ...
more >>>

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

Visu Makam, Avi Wigderson

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: ${\rm SING}_{n,m}$, consisting of all $m$-tuples of $n\times n$ complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in ${\rm SING}_{n,m}$ will imply super-polynomial circuit lower bounds, ... more >>>

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

Vishwas Bhargava, Sumanta Ghosh

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of ... more >>>

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>