Zobrazeno 1 - 10
of 20
pro vyhledávání: '"Chatterjee, Prerona"'
In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering ($\sum \mathsf{smABP}$). Specifically, we give an explicit $nd$-variate
Externí odkaz:
http://arxiv.org/abs/2312.15874
Autor:
Chatterjee, Prerona, Tengse, Anamay
We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the
Externí odkaz:
http://arxiv.org/abs/2309.07612
Autor:
Chatterjee, Prerona, Hrubeš, Pavel
We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate
Externí odkaz:
http://arxiv.org/abs/2301.01676
In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran and Perifel 2009, Malod 2011, Mahajan and Rao 2013) that is believed to be larger than VNP. We observe that
Externí odkaz:
http://arxiv.org/abs/2202.13103
Publikováno v:
In Theoretical Computer Science 12 September 2024 1009
Autor:
Chatterjee, Prerona
The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues
Externí odkaz:
http://arxiv.org/abs/2103.00864
Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation
Externí odkaz:
http://arxiv.org/abs/2102.12886
The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the efficacy of commonly used techniques for proving lower bounds in algeb
Externí odkaz:
http://arxiv.org/abs/2004.14147
We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Stras
Externí odkaz:
http://arxiv.org/abs/1911.11793
We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (2
Externí odkaz:
http://arxiv.org/abs/1812.10249