Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
79
0
0.0
(
0
)
Added by
Abhranil Chatterjee
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABP) for determinant and permanent polynomials of the emph{rectangular} symbolic matrix in both commutative and noncommutative settings. The main results are: 1. We show an explicit $O^{*}({nchoose {downarrow k/2}})$-size ABP construction for noncommutative permanent polynomial of $ktimes n$ symbolic matrix. We obtain this via an explicit ABP construction of size $O^{*}({nchoose {downarrow k/2}})$ for $S_{n,k}^*$, noncommutative symmetrized version of the elementary symmetric polynomial $S_{n,k}$. 2. We obtain an explicit $O^{*}(2^k)$-size ABP construction for the commutative rectangular determinant polynomial of the $ktimes n$ symbolic matrix. 3. In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is $W[1]$-hard.
rate research
Read More
We construct pseudorandom generators of seed length $tilde{O}(log(n)cdot log(1/epsilon))$ that $epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $tilde{O}(log(n) cdot mathrm{poly}(1/epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992]. Our constructions are based on the `iterated milder restrictions approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018]. Two conceptual ideas that play an important role in our analysis are: (1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier. (2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions. In addition, we achieve nearly optimal seed-length $tilde{O}(log(n/epsilon))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $mathrm{poly}log(n)$ layers.
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most $k$ is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.
We view the determinant and permanent as functions on directed weighted graphs and introduce their analogues for the undirected graphs. We prove that the task of computing the undirected determinants as well as permanents for planar graphs, whose vertices have degree at most 4, is #P-complete. In the case of planar graphs whose vertices have degree at most 3, the computation of the undirected determinant remains #P-complete while the permanent can be reduced to the FKT algorithm, and therefore is polynomial. The undirected permanent is a Holant problem and its complexity can be deduced from the existing literature. The concept of the undirected determinant is new. Its introduction is motivated by the formal resemblance to the directed determinant, a property that may inspire generalizations of some of the many algorithms which compute the latter. For a sizable class of planar 3-regular graphs, we are able to compute the undirected determinant in polynomial time.
A compound determinant identity for minors of rectangular matrices is established. As an application, we derive Vandermonde type determinant formulae for classical group characters.
There is a digraph corresponding to every square matrix over $mathbb{C}$. We generate a recurrence relation using the Laplace expansion to calculate the characteristic, and permanent polynomials of a square matrix. Solving this recurrence relation, we found that the characteristic, and permanent polynomials can be calculated in terms of characteristic, and permanent polynomials of some specific induced subdigraphs of blocks in the digraph, respectively. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Similar to the characteristic, and permanent polynomials; the determinant, and permanent can also be calculated. Therefore, this article provides a combinatorial meaning of these useful quantities of the matrix theory. We conclude this article with a number of open problems which may be attempted for further research in this direction.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
