Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Dutta, Pranjal P."'
We study the \emph{order-finding problem} for Read-once Oblivious Algebraic Branching Programs (ROABPs). Given a polynomial $f$ and a parameter $w$, the goal is to find an order $\sigma$ in which $f$ has an ROABP of \emph{width} $w$. We show that thi
Externí odkaz:
http://arxiv.org/abs/2411.18981
For a polynomial $f$ from a class $\mathcal{C}$ of polynomials, we show that the problem to compute all the constant degree irreducible factors of $f$ reduces in polynomial time to polynomial identity tests (PIT) for class $\mathcal{C}$ and divisibil
Externí odkaz:
http://arxiv.org/abs/2411.17330
Autor:
Berg, Maxim van den, Dutta, Pranjal, Gesmundo, Fulvio, Ikenmeyer, Christian, Lysikov, Vladimir
We prove that in the algebraic metacomplexity framework, the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. This means that many existing
Externí odkaz:
http://arxiv.org/abs/2411.03444
Given an Abelian group G, a Boolean-valued function f: G -> {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain G. In a seminal paper, Gopalan et al. proved "Granularity" for Fourier coefficients of
Externí odkaz:
http://arxiv.org/abs/2406.18700
Publikováno v:
41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), pp. 30:1-30:15
Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has low border complexity. Debordering is the task of proving an upper bou
Externí odkaz:
http://arxiv.org/abs/2401.07631
Publikováno v:
15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pp. 43:1-43:23
We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet m
Externí odkaz:
http://arxiv.org/abs/2311.17019
Polynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth-$4$ reduction result by Agrawal and Vinay (FOCS 2008) has made PIT for depth-$4$ circuits an enticing pursuit. A restricted depth-4 circuit computing a $n$-var
Externí odkaz:
http://arxiv.org/abs/2304.11325
De-bordering is the task of proving that a border complexity measure is bounded from below, by a non-border complexity measure. This task is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmu
Externí odkaz:
http://arxiv.org/abs/2211.07055
Given $(a_1, \dots, a_n, t) \in \mathbb{Z}_{\geq 0}^{n + 1}$, the Subset Sum problem ($\mathsf{SSUM}$) is to decide whether there exists $S \subseteq [n]$ such that $\sum_{i \in S} a_i = t$. There is a close variant of the $\mathsf{SSUM}$, called $\m
Externí odkaz:
http://arxiv.org/abs/2112.11020
Autor:
Mohan, Bitupan1 (AUTHOR), Dutta, Pranjal P.1 (AUTHOR), Saikia, Prakash J.1,2 (AUTHOR) saikiapj@neist.res.in
Publikováno v:
Journal of Polymer Research. Oct2023, Vol. 30 Issue 10, p1-13. 13p.
