The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Avi Wigderson - One of the best experts on this subject based on the ideXlab platform.
-
operator scaling via geodesically convex optimization Invariant Theory and polynomial identity testing
Symposium on the Theory of Computing, 2018Co-Authors: Zeyuan Allenzhu, Ankit Garg, Rafael Oliveira, Avi WigdersonAbstract:We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, "commutative" metric (for which the above problem is not convex). Our method is general and applicable to other settings. As a consequence, we solve the equivalence problem for the left-right group action underlying the operator scaling problem. This yields a deterministic polynomial-time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.
-
alternating minimization scaling algorithms and the null cone problem from Invariant Theory
Conference on Innovations in Theoretical Computer Science, 2018Co-Authors: Peter Burgisser, Ankit Garg, Rafael Oliveira, Michael Walter, Avi WigdersonAbstract:Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information Theory, and geometric complexity Theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality Theory, and new bounds on the bitsizes of coefficients of Invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity Theory (GCT).
-
a deterministic polynomial time algorithm for non commutative rational identity testing
Foundations of Computer Science, 2016Co-Authors: Ankit Garg, Rafael Oliveira, Leonid Gurvits, Avi WigdersonAbstract:Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) Invariant Theory and representationTheory, linear algebra, optimization, linear system Theory,quantum information Theory, and naturally in non-commutativealgebra.
R B Zhang - One of the best experts on this subject based on the ideXlab platform.
-
first fundamental theorems of Invariant Theory for quantum supergroups
European Journal of Mathematics, 2019Co-Authors: G I Lehrer, Hechun Zhang, R B ZhangAbstract:Let $$\mathrm{U}_q({{\mathfrak {g}}})$$ be the quantum supergroup of $${\mathfrak {gl}}_{m|n}$$ or the modified quantum supergroup of $${\mathfrak {osp}}_{m|2n}$$ over the field of rational functions in q, and let $$V_q$$ be the natural module for $$\mathrm{U}_q({{\mathfrak {g}}})$$ . There exists a unique tensor functor associated with $$V_q$$ , from the category of ribbon graphs to the category of finite dimensional representations of $$\mathrm{U}_q({{\mathfrak {g}}})$$ , which preserves ribbon category structures. We show that this functor is full in the cases $${{\mathfrak {g}}}={\mathfrak {gl}}_{m|n}$$ or $${\mathfrak {osp}}_{2\ell +1|2n}$$ . For $${{\mathfrak {g}}}={\mathfrak {osp}}_{2\ell |2n}$$ , we show that the space is spanned by images of ribbon graphs if $$r+s< 2\ell (2n+1)$$ . The proofs involve an equivalence of module categories for two versions of the quantisation of $$\mathrm{U}({{\mathfrak {g}}})$$ .
-
the first fundamental theorem of Invariant Theory for the orthosymplectic super group
Advances in Mathematics, 2017Co-Authors: Pierre Deligne, G I Lehrer, R B ZhangAbstract:We give an elementary and explicit proof of the first fundamental theorem of Invariant Theory for the orthosymplectic supergroup by generalising the geometric method of Atiyah, Bott and Patodi to the supergroup context. We use methods from super-algebraic geometry to convert Invariants of the orthosymplectic supergroup into Invariants of the corresponding general linear supergroup on a different space. In this way, super Schur–Weyl–Brauer duality is established between the orthosymplectic supergroup of superdimension (m|2n) and the Brauer algebra with parameter m − 2n. The result may be interpreted either in terms of the group scheme OSp(V) over \({{\mathbb C}}\), where V is a finite dimensional super space, or as a statement about the orthosymplectic Lie supergroup over the infinite dimensional Grassmann algebra \({\Lambda}\). We take the latter point of view here, and also state a corresponding theorem for the orthosymplectic Lie superalgebra, which involves an extra Invariant generator, the super-Pfaffian.
-
the brauer category and Invariant Theory
Journal of the European Mathematical Society, 2015Co-Authors: G I Lehrer, R B ZhangAbstract:A category of Brauer diagrams, analogous to Turaev's tangle category, is introduced, and a presentation of the category is given; specifically, we prove that seven relations among its four generating homomorphisms suffice to deduce all equations among the morphisms. Full tensor functors are constructed from this category to the category of tensor representations of the orthogonal group $O(V)$ or the symplectic group $Sp(V)$ over any field of characteristic zero. The first and second fundamental theorems of Invariant Theory for these classical groups are generalised to the category theoretic setting. The major outcome is that we obtain new presentations for the endomorphism algebras of the module $V^{\otimes r}$. These are obtained by appending to the standard presentation of the Brauer algebra of degree $r$ one additional relation. This relation stipulates the vanishing of an element of the Brauer algebra which is quasi-idempotent, and which we describe explicitly both in terms of diagrams and algebraically. In the symplectic case, if $\dim V = 2n$, the element is precisely the central idempotent in the Brauer subalgebra of degree $n + 1$, which corresponds to its trivial representation. Since this is the Brauer algebra of highest degree which is semisimple, our generator is an exact analogue for the Brauer algebra of the Jones idempotent of the Temperley-Lieb algebra. In the orthogonal case the additional relation is also a quasi-idempotent in the integral Brauer algebra. Both integral and quantum analogues of these results are given, the latter of which involve the BMW algebras.
-
the first fundamental theorem of Invariant Theory for the orthosymplectic super group
arXiv: Representation Theory, 2014Co-Authors: Pierre Deligne, G I Lehrer, R B ZhangAbstract:In a previous work we established a super Schur-Weyl-Brauer duality between the orthosymplectic supergroup of superdimension $(m|2n)$ and the Brauer algebra with parameter $m-2n$. This led to a proof of the first fundamental theorem of Invariant Theory, using some elementary algebraic supergeometry, and based upon an idea of Atiyah. In this work we use the same circle of ideas to prove the second fundamental theorem for the orthosymplectic supergroup. The proof uses algebraic supergeometry to reduce the problem to the case of the general linear supergroup, which is understood. The main result has a succinct formulation in terms of Brauer diagrams. Our proof includes new proofs of the corresponding second fundamental theorems for the classical orthogonal and symplectic groups, as well as their quantum analogues. These new proofs are independent of the Capelli identities, which are replaced by algebraic geometric arguments.
-
the second fundamental theorem of Invariant Theory for the orthogonal group
Annals of Mathematics, 2012Co-Authors: Gustav I. Lehrer, R B ZhangAbstract:Let V = C n be endowed with an orthogonal form and G = O(V ) be the corresponding orthogonal group. Brauer showed in 1937 that there is a surjective homomorphism : Br(n)! EndG(V r ), where Br(n) is the r-string Brauer algebra with parameter n. However the kernel of has remained elusive. In this paper we show that, in analogy with the case of GL(V ), for r n + 1, has a kernel which is generated by a single idempotent element E, and we give a simple explicit formula for E. Using the Theory of cellular algebras, we show how E may be used to determine the multiplicities of the irreducible representations of O(V ) in V r . We also show how our results extend to the case where C is replaced by an appropriate eld of positive characteristic, and we comment on quantum analogues of our results.
Ankit Garg - One of the best experts on this subject based on the ideXlab platform.
-
operator scaling via geodesically convex optimization Invariant Theory and polynomial identity testing
Symposium on the Theory of Computing, 2018Co-Authors: Zeyuan Allenzhu, Ankit Garg, Rafael Oliveira, Avi WigdersonAbstract:We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, "commutative" metric (for which the above problem is not convex). Our method is general and applicable to other settings. As a consequence, we solve the equivalence problem for the left-right group action underlying the operator scaling problem. This yields a deterministic polynomial-time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.
-
alternating minimization scaling algorithms and the null cone problem from Invariant Theory
Conference on Innovations in Theoretical Computer Science, 2018Co-Authors: Peter Burgisser, Ankit Garg, Rafael Oliveira, Michael Walter, Avi WigdersonAbstract:Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information Theory, and geometric complexity Theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality Theory, and new bounds on the bitsizes of coefficients of Invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity Theory (GCT).
-
a deterministic polynomial time algorithm for non commutative rational identity testing
Foundations of Computer Science, 2016Co-Authors: Ankit Garg, Rafael Oliveira, Leonid Gurvits, Avi WigdersonAbstract:Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) Invariant Theory and representationTheory, linear algebra, optimization, linear system Theory,quantum information Theory, and naturally in non-commutativealgebra.
Huayi Chen - One of the best experts on this subject based on the ideXlab platform.
-
maximal slope of tensor product of hermitian vector bundles
Journal of Algebraic Geometry, 2009Co-Authors: Huayi ChenAbstract:We give an upper bound for the maximal slope of the tensor product of several non-zero Hermitian vector bundles on the spectrum of an algebraic integer ring. By Minkowski's theorem, we need to estimate the Arakelov degree of an arbitrary Hermitian line subbundle $\overline M$ of the tensor product. In the case where the generic fiber of $M$ is semistable in the sense of geometric Invariant Theory, the estimation is established by constructing, through the classical Invariant Theory, a special polynomial which does not vanish on the generic fibre of $M$. Otherwise we use an explicte version of a result of Ramanan and Ramanathan to reduce the general case to the former one.
-
maximal slope of tensor product of hermitian vector bundles
arXiv: Algebraic Geometry, 2007Co-Authors: Huayi ChenAbstract:We give an upper bound for the maximal slope of the tensor product of several non-zero Hermitian vector bundles on the spectrum of an algebraic integer ring. By Minkowski's theorem, we need to estimate the Arakelov degree of an arbitrary Hermitian line subbundle $\bar M$ of the tensor product. In the case where the generic fiber of $M$ is semistable in the sense of geometric Invariant Theory, the estimation is established by constructing, through the classical Invariant Theory, a special polynomial which does not vanish on the generic fibre of $M$. Otherwise we use an explicte version of a result of Ramanan and Ramanathan to reduce the general case to the former one.
Rafael Oliveira - One of the best experts on this subject based on the ideXlab platform.
-
operator scaling via geodesically convex optimization Invariant Theory and polynomial identity testing
Symposium on the Theory of Computing, 2018Co-Authors: Zeyuan Allenzhu, Ankit Garg, Rafael Oliveira, Avi WigdersonAbstract:We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, "commutative" metric (for which the above problem is not convex). Our method is general and applicable to other settings. As a consequence, we solve the equivalence problem for the left-right group action underlying the operator scaling problem. This yields a deterministic polynomial-time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.
-
alternating minimization scaling algorithms and the null cone problem from Invariant Theory
Conference on Innovations in Theoretical Computer Science, 2018Co-Authors: Peter Burgisser, Ankit Garg, Rafael Oliveira, Michael Walter, Avi WigdersonAbstract:Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information Theory, and geometric complexity Theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality Theory, and new bounds on the bitsizes of coefficients of Invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity Theory (GCT).
-
a deterministic polynomial time algorithm for non commutative rational identity testing
Foundations of Computer Science, 2016Co-Authors: Ankit Garg, Rafael Oliveira, Leonid Gurvits, Avi WigdersonAbstract:Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) Invariant Theory and representationTheory, linear algebra, optimization, linear system Theory,quantum information Theory, and naturally in non-commutativealgebra.
