Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Geometric complexity theory V: Efficient algorithms for Noether normalization
HTML articles powered by AMS MathViewer

by Ketan D. Mulmuley PDF
J. Amer. Math. Soc. 30 (2017), 225-309 Request permission

Abstract:

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 the following:

(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,\lfloor m/2 \rfloor ]$.

(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.

References
Similar Articles
  • Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 14Q20, 68Q15
  • Retrieve articles in all journals with MSC (2010): 14Q20, 68Q15
Additional Information
  • Ketan D. Mulmuley
  • Affiliation: Department of Computer Science, The University of Chicago, Chicago, Illinois, 60637
  • MR Author ID: 128145
  • Email: mulmuley@uchicago.edu
  • Received by editor(s): August 5, 2013
  • Received by editor(s) in revised form: March 3, 2014, January 12, 2015, November 6, 2015, March 27, 2016, and April 19, 2016
  • Published electronically: June 21, 2016
  • Additional Notes: This work was supported by NSF grant CCF-1017760. This article is the full version of its FOCS 2012 extended abstract [70].

  • Dedicated: Dedicated to Sri Ramakrishna
  • © Copyright 2016 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 30 (2017), 225-309
  • MSC (2010): Primary 14Q20; Secondary 68Q15
  • DOI: https://doi.org/10.1090/jams/864
  • MathSciNet review: 3556292