Skip to main content
Post Made Community Wiki by Stefan Kohl
Connected more directly to complexity theory.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

In the above paper, KM proves that Noether's Normalization Lemma (NNL) is not as intractable as it might seem (from Gröbner basis theory—exponential in $n$). He shows that, "in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability." The next issue is achieving deterministic polynomial-time. Here he only partially succeeds, showing that "for some interesting cases of explicit varieties," NNL "can indeed be solved deterministically in quasi-poly$(n)$-time." This brings some instances of NNL "from EXPSPACE to quasi-P, assuming the hardness hypothesis for the permanent in geometric complexity theory."

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

In the above paper, KM proves that Noether's Normalization Lemma (NNL) is not as intractable as it might seem (from Gröbner basis theory—exponential in $n$). He shows that, "in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability." The next issue is achieving deterministic polynomial-time. Here he only partially succeeds, showing that "for some interesting cases of explicit varieties," NNL "can indeed be solved deterministically in quasi-poly$(n)$-time."

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

In the above paper, KM proves that Noether's Normalization Lemma (NNL) is not as intractable as it might seem (from Gröbner basis theory—exponential in $n$). He shows that, "in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability." The next issue is achieving deterministic polynomial-time. Here he only partially succeeds, showing that "for some interesting cases of explicit varieties," NNL "can indeed be solved deterministically in quasi-poly$(n)$-time." This brings some instances of NNL "from EXPSPACE to quasi-P, assuming the hardness hypothesis for the permanent in geometric complexity theory."

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

added 589 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

In the above paper, KM proves that Noether's Normalization Lemma (NNL) is not as intractable as it might seem (from Gröbner basis theory—exponential in $n$). He shows that, "in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability." The next issue is achieving deterministic polynomial-time. Here he only partially succeeds, showing that "for some interesting cases of explicit varieties," NNL "can indeed be solved deterministically in quasi-poly$(n)$-time."

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

In the above paper, KM proves that Noether's Normalization Lemma (NNL) is not as intractable as it might seem (from Gröbner basis theory—exponential in $n$). He shows that, "in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability." The next issue is achieving deterministic polynomial-time. Here he only partially succeeds, showing that "for some interesting cases of explicit varieties," NNL "can indeed be solved deterministically in quasi-poly$(n)$-time."

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

added 13 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is hisKetan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is his summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

"Current breakthroughs" I cannot address. So I will just list three recent relevant papers. The first is Ketan Mulmuley's summary of the CGT program:

(1) Mulmuley, Ketan D. "The GCT program toward the P vs. NP problem." Communications of the ACM, 55.6 (2012): 98-107. PDF download.

Next, Ketan's just published paper, the 5th in a series:

(2) Mulmuley, Ketan. "Geometric complexity theory V: Efficient algorithms for Noether normalization." Journal of the American Mathematical Society, 30.1 (2017): 225-309. Earlier arXiv version.

And here is a quite recent posting to the arXiv, commenting "on how [the] algebraic natural proofs barrier [they detail] bears on geometric complexity theory":

(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Abstract.

added 66 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading