Ketan D. Mulmuley
Supplemental Material
- Agrawal, M. Proving lower bounds via pseudo-random generators. In Proceedings of the FSTTCS (2005), Springer-Verlag, Berlin, Germany, 92--105. Google Scholar
Digital Library
- Appel, K., Haken, W., Koch, J. Every planar map is four colourable. Illinois J. Math. 21 (1977), 439--567.Google Scholar
- Arora, S., Barak, B. Computation Complexity: a Modern Approach, Cambridge University Press, Cambridge, England, 2009. Google ScholarDigital Library
- Blasiak, J., Mulmuley, K., Sohoni, M. Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem. cs. ArXiv preprint cs. CC/0703110 (2011).Google Scholar
- Boppana, R., Sipser, M. The complexity of finite functions. Handbook of Theoretical Computer Science. J. van Leeuwen, ed. Volume A, MIT press, 1990, 757--804. Google ScholarDigital Library
- Bürgisser, P., Clausen, M., Shokrollahi, M. Algebraic Complexity Theory, Springer-Verlag, 1997. Google ScholarCross Ref
- Bürgisser, P. and Ikenmeyer, C. Geometric complexity theory and tensor rank. arXiv:1011.1350v1 (2010).Google Scholar
- Bürgisser, P., Landsberg, J., Manivel, L., Weyman, J. An overview of mathematical issues arising in the geometric complexity theory approach to VP ≠ VNP. arXiv:0907.2850v1 {cs.CC} (2009).Google Scholar
- Cook, S. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM Symposium on Theory of Computing (1971), ACM, New York, NY, 151--158. Google ScholarDigital Library
- Deligne, P. La conjecture de weil II. Publ. Math. Inst. Hau. Étud. Sci. 52 (1980), 137--252.Google Scholar
- Fortnow, L. The status of the P versus NP problem. CACM 52, 9 (2009), 78--86. Google ScholarDigital Library
- Kabanets, V., Impagliazzo, R. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13 (2004), 1--46. Google ScholarDigital Library
- Karp, R. Reducibility among combinatorial problems. Complexity of Computer Computations. R. Miller and J. Thatcher, eds. Plenum Press, New York, 1972, 85--103.Google Scholar
- Landsberg, J., Manivel, L., Ressayre, N. Hypersurfaces with degenerate duals and the geometric complexity theory program. arXiv:1004.4802v1 {math.AG} (2010).Google Scholar
- Levin, L. Universal sequential search problems. Probl. Inform. transm. 9 (1973), 115--116.Google Scholar
- Mignon, T., Ressayre, N. A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not. 79 (2004), 4241--4253.Google ScholarCross Ref
- Mulmuley, K. Geometric Complexity Theory IX. Technical report, under preparation.Google Scholar
- Mulmuley, K. Lower bounds in a parallel model without bit operations. SIAM J. Comput. 28, 4 (1999), 1460--1509. Google ScholarDigital Library
- Mulmuley, K. Geometric Complexity Theory VII: Nonstandard Quantum Group for the Plethysm Problem. Technical Report TR-2007-14, Computer Science Department, The University of Chicago, 2007.Google Scholar
- Mulmuley, K. Geometric Complexity Theory VIII: On Canonical Bases for the Nonstandard Quantum Groups. Technical Report TR 2007-15, Computer Science Department, The University of Chicago, 2007.Google Scholar
- Mulmuley, K. Explicit proofs and the flip. arXiv:1009.0246 v1 {cs.CC} (2010).Google Scholar
- Mulmuley, K. Geometric Complexity Theory VI: The Flip via Positivity. Technical report, The Computer Science Department, The University of Chicago, 2010.Google Scholar
- Mulmuley, K. On P vs. NP and geometric complexity theory. JACM 58, 2 (2011). Google ScholarDigital Library
- Mulmuley, K., Narayanan, H., Sohoni, M. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebr. Combinator. (Nov. 2011), 1--8. Google ScholarDigital Library
- Mulmuley, K., Sohoni, M. Geometric complexity theory I: an approach to the P vs. NP and related problems. SIAM J. Comput. 31, 2 (2001), 496--526. Google ScholarDigital Library
- Mulmuley, K., Sohoni, M. Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM J. Comput. 38, 3 (2008), 1175--1206. Google ScholarDigital Library
- Razborov, A. Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR 281 (1985), 798--801.Google Scholar
- Strassen, V. Rank and optimal computation of generic tensors. Lin. Algebra Appl. 53 (1983), 645--685.Google ScholarCross Ref
- Valiant, L. The complexity of computing the permanent. TCS 8 (1979), 189--201.Google ScholarCross Ref
- Weyl, H. Classical Groups, Princeton University Press, Princeton, NJ, 1946.Google Scholar
Index Terms
- The GCT program toward the P vs. NP problem
Recommendations
NP VS QMAlog(2)
Although it is believed unlikely that NP-hard problems admit efficient quantum algo-rithms, it has been shown that a quantum verifier can solve NP-complete problemsgiven a "short" quantum proof; more precisely, NP ⊆ QMAlog(2) where QMAlog(2) de-notes ...
Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and ArchitecturesThe theory of NP-hardness has been very successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial time algorithms, but large exponents in their time bounds can make ...
Comments