Source author record

Ketan D. Mulmuley

Ketan D. Mulmuley appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity math.AG math.CO math.RT

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Boundaries of VP and VNP

One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = $\overline{\textrm{VP}}$, where VP is the class of families of polynomials that are of polynomial degree and can be computed by arithmetic circuits of polynomial size, and $\overline{\textrm{VP}}$ is the class of families of polynomials that are of polynomial degree and can be approximated infinitesimally closely by arithmetic circuits of polynomial size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that $\overline{\textrm{VP}}$ is not contained in VP. Towards that end, we introduce three degenerations of VP (i.e., sets of points in $\overline{\textrm{VP}}$), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VP $\subseteq$ Newton-VP $\subseteq$ VP* $\subseteq$ VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating $\overline{\textrm{VP}}$ from VP. Although we do not yet construct explicit candidates for the polynomial families in $\overline{\textrm{VP}}\setminus$VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP $\setminus$ VP based on semi-invariants of quivers would have to be non-generic by showing that, for many finite quivers (including some wild ones), any Newton degeneration of a generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.

preprint2016arXiv

Geometric Complexity Theory V: Efficient algorithms for Noether Normalization

We study a basic algorithmic problem in algebraic geometry, which we call NNL, of constructing a normalizing map as per Noether's Normalization Lemma. For general explicit varieties, as formally defined in this paper, we give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, we give deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry. In particular, we show that: (1) The categorical quotient for any finite dimensional representation $V$ of $SL_m$, with constant $m$, is explicit in characteristic zero. (2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of $V$. (3) The categorical quotient of the space of $r$-tuples of $m \times m$ matrices by the simultaneous conjugation action of $SL_m$ is explicit in any characteristic. (4) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in $m$ and $r$ in any characteristic $p$ not in $[2,\ m/2]$. (5) NNL for every explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, assuming the hardness hypothesis for the permanent in geometric complexity theory. The last result leads to a geometric complexity theory approach to put NNL for every explicit variety in P.

preprint2013arXiv

Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem

The Kronecker coefficient g_{λμν} is the multiplicity of the GL(V)\times GL(W)-irreducible V_λ\otimes W_μin the restriction of the GL(X)-irreducible X_νvia the natural map GL(V)\times GL(W) \to GL(V \otimes W), where V, W are \mathbb{C}-vector spaces and X = V \otimes W. A fundamental open problem in algebraic combinatorics is to find a positive combinatorial formula for these coefficients. We construct two quantum objects for this problem, which we call the nonstandard quantum group and nonstandard Hecke algebra. We show that the nonstandard quantum group has a compact real form and its representations are completely reducible, that the nonstandard Hecke algebra is semisimple, and that they satisfy an analog of quantum Schur-Weyl duality. Using these nonstandard objects as a guide, we follow the approach of Adsul, Sohoni, and Subrahmanyam to construct, in the case dim(V) = dim(W) =2, a representation \check{X}_νof the nonstandard quantum group that specializes to Res_{GL(V) \times GL(W)} X_νat q=1. We then define a global crystal basis +HNSTC(ν) of \check{X}_νthat solves the two-row Kronecker problem: the number of highest weight elements of +HNSTC(ν) of weight (λ,μ) is the Kronecker coefficient g_{λμν}. We go on to develop the beginnings of a graphical calculus for this basis, along the lines of the U_q(\sl_2) graphical calculus, and use this to organize the crystal components of +HNSTC(ν) into eight families. This yields a fairly simple, explicit and positive formula for two-row Kronecker coefficients, generalizing a formula of Brown, van Willigenburg, and Zabrocki. As a byproduct of the approach, we also obtain a rule for the decomposition of Res_{GL_2 \times GL_2 \rtimes §_2} X_νinto irreducibles.

preprint2007arXiv

Geometric Complexity Theory: Introduction

These are lectures notes for the introductory graduate courses on geometric complexity theory (GCT) in the computer science department, the university of Chicago. Part I consists of the lecture notes for the course given by the first author in the spring quarter, 2007. It gives introduction to the basic structure of GCT. Part II consists of the lecture notes for the course given by the second author in the spring quarter, 2003. It gives introduction to invariant theory with a view towards GCT. No background in algebraic geometry or representation theory is assumed. These lecture notes in conjunction with the article \cite{GCTflip1}, which describes in detail the basic plan of GCT based on the principle called the flip, should provide a high level picture of GCT assuming familiarity with only basic notions of algebra, such as groups, rings, fields etc.