Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower Bounds for Special Cases of Syntactic Multilinear ABPs
98
0
0.0
(
0
)
Added by
Ramya C
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Algebraic Branching Programs(ABPs) are standard models for computing polynomials. Syntactic multilinear ABPs (smABPs) are restrictions of ABPs where every variable is allowed to occur at most once in every path from the start to the terminal node. Proving lower bounds against syntactic multilinear ABPs remains a challenging open question in Algebraic Complexity Theory. The current best known bound is only quadratic [Alon-Kumar-Volk, ECCC 2017]. In this article we develop a new approach upper bounding the rank of the partial derivative matrix of syntactic multlinear ABPs: Convert the ABP to a syntactic mulilinear formula with a super polynomial blow up in the size and then exploit the structural limitations of resulting formula to obtain a rank upper bound. Using this approach, we prove exponential lower bounds for special cases of smABPs and circuits - namely sum of Oblivious Read-Once ABPs, r-pass mulitlinear ABPs and sparse ROABPs. En route, we also prove super-polynomial lower bound for a special class of syntactic multilinear arithmetic circuits.
rate research
Read More
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ circ XOR$ requires size $2^{0.18 n}$. This completely answers an open question of Tur{a}n and Vatan [FoCM97]. We also show that the spectral classes $PL_1, PL_infty$, and the polynomial threshold function classes $widehat{PT}_1, PT_1$, are incomparable to linear decision lists.
We prove a query complexity lower bound for $mathsf{QMA}$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $mathsf{SBP}^A otsubset mathsf{QMA}^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to derive a lower bound for the $mathsf{SBQP}$ query complexity of the $mathsf{AND}$ of two approximate counting instances. We use Laurent polynomials as a tool in our proof, showing that the Laurent polynomial method can be useful even for problems involving ordinary polynomials.
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the circuits which take a matrix input are unchanged by a permutation applied simultaneously to the rows and columns of the matrix. Under such restrictions we have polynomial-size circuits for computing the determinant but no subexponential size circuits for the permanent. Here, we consider a more stringent symmetry requirement, namely that the circuits are unchanged by arbitrary even permutations applied separately to rows and columns, and prove an exponential lower bound even for circuits computing the determinant. The result requires substantial new machinery. We develop a general framework for proving lower bounds for symmetric circuits with restricted symmetries, based on a new support theorem and new two-player restricted bijection games. These are applied to the determinant problem with a novel construction of matrices that are bi-adjacency matrices of graphs based on the CFI construction. Our general framework opens the way to exploring a variety of symmetry restrictions and studying trade-offs between symmetry and other resources used by arithmetic circuits.
In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d. This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order $Omega$($sqrt$ d), and were obtained from arguments based on Wronskian determinants and shifted derivatives. We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as lacunary polynomial interpolation).
We develop a notion of {em inner rank} as a tool for obtaining lower bounds on the rank of matrix multiplication tensors. We use it to give a short proof that the border rank (and therefore rank) of the tensor associated with $ntimes n$ matrix multiplication over an arbitrary field is at least $2n^2-n+1$. While inner rank does not provide improvements to currently known lower bounds, we argue that this notion merits further study.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
