Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExplicit polynomial sequences with maximal spaces of partial derivatives and a question of K. Mulmuley
103
0
0.0
(
0
)
Added by
Fulvio Gesmundo
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We answer a question of K. Mulmuley: In [Efremenko-Landsberg-Schenck-Weyman] it was shown that the method of shifted partial derivatives cannot be used to separate the padded permanent from the determinant. Mulmuley asked if this no-go result could be extended to a model without padding. We prove this is indeed the case using the iterated matrix multiplication polynomial. We also provide several examples of polynomials with maximal space of partial derivatives, including the complete symmetric polynomials. We apply Koszul flattenings to these polynomials to have the first explicit sequence of polynomials with symmetric border rank lower bounds higher than the bounds attainable via partial derivatives.
rate research
Read More
The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the trace method, recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.A slightly shorter version of this paper was presented at STACS17. In this new version we have corrected a typo in Section 4.1, and added a reference to Shitovs work on tensor rank.
We extend some classical results - such as Quillens Theorem A, the Grothendieck construction, Thomasons Theorem and the characterisation of homotopically cofinal functors - from the homotopy theory of small categories to polynomial monads and their algebras. As an application we give a categorical proof of the Dwyer-Hess and Turchin results concerning the explicit double delooping of spaces of long knots.
Rank-2 Drinfeld modules are a function-field analogue of elliptic curves, and the purpose of this paper is to investigate similarities and differences between rank-2 Drinfeld modules and elliptic curves in terms of supersingularity. Specifically, we provide an explicit formula of a supersingular polynomial for rank-2 Drinfeld modules and prove several basic properties. As an application, we give a numerical example of an asymptotically optimal tower of Drinfeld modular curves.
In the spirit of recent work of Harada-Kaveh and Nishinou-Nohara-Ueda, we study the symplectic geometry of Popovs horospherical degenerations of complex algebraic varieties with the action of a complex linearly reductive group. We formulate an intrinsic symplectic contraction of a Hamiltonian space, which is a surjective, continuous map onto a new Hamiltonian space that is a symplectomorphism on an explicitly defined dense open subspace. This map is given by a precise formula, using techniques from the theory of symplectic reduction and symplectic implosion. We then show, using the Vinberg monoid, that the gradient-Hamiltonian flow for a horospherical degeneration of an algebraic variety gives rise to this contraction from a general fiber to the special fiber. We apply this construction to branching problems in representation theory, and finally we show how the Gelfand-Tsetlin integrable system can be understood to arise this way.
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
