{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:10:00Z","timestamp":1776863400315,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540287025","type":"print"},{"value":"9783540318675","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549345_39","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:05:47Z","timestamp":1127815547000},"page":"447-458","source":"Crossref","is-referenced-by-count":31,"title":["On the Complexity of Mixed Discriminants and Related Problems"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Gurvits","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","first-page":"227","volume":"3","author":"A. Aleksandrov","year":"1938","unstructured":"Aleksandrov, A.: On the theory of mixed volumes of convex bodies, IV, Mixed discriminants and mixed volumes. Mat. Sb (N.S.)\u00a03, 227\u2013251 (1938) (in Russian)","journal-title":"Mat. Sb. (N.S.)"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0024-3795(89)90009-8","volume":"126","author":"R.B. Bapat","year":"1989","unstructured":"Bapat, R.B.: Mixed discriminants of positive semidefinite matrices. Linear Algebra and its Applications\u00a0126, 107\u2013124 (1989)","journal-title":"Linear Algebra and its Applications"},{"key":"39_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/PL00009316","volume":"18","author":"A.I. Barvinok","year":"1997","unstructured":"Barvinok, A.I.: Computing Mixed Discriminants, Mixed Volumes, and Permanents. Discrete & Computational Geometry\u00a018, 205\u2013237 (1997)","journal-title":"Discrete & Computational Geometry"},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/j.jcss.2004.06.003","volume":"69","author":"L. Gurvits","year":"2004","unstructured":"Gurvits, L.: Classical complexity and Quantum Entanglement. Jour. of Comp. and Sys. Sciences (JCSS)\u00a069, 448\u2013484 (2004)","journal-title":"Jour. of Comp. and Sys. Sciences (JCSS)"},{"key":"39_CR5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X","volume":"14","author":"A.I. Barvinok","year":"1999","unstructured":"Barvinok, A.I.: Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Random Structures & Algorithms\u00a014, 29\u201361 (1999)","journal-title":"Random Structures & Algorithms"},{"key":"39_CR6","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1287\/moor.21.1.65","volume":"21","author":"A.I. Barvinok","year":"1996","unstructured":"Barvinok, A.I.: Two algorithmic results for the Traveling Salesman Problem. Math. Oper. Res.\u00a021, 65\u201384 (1996) (2001 version from researchindex.com)","journal-title":"Math. Oper. Res."},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Classical deterministic complexity of Edmonds problem and Quantum entanglement. In: Proc. of 35 annual ACM symposium on theory of computing, San Diego (2003)","DOI":"10.1145\/780542.780545"},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00454-001-0083-2","volume":"27","author":"L. Gurvits","year":"2002","unstructured":"Gurvits, L., Samorodnitsky, A.: A deterministic algorithm for approximating mixed discriminant and mixed volume, and a combinatorial corollary. Discrete and Computational Geometry\u00a027, 531\u2013550 (2002)","journal-title":"Discrete and Computational Geometry"},{"issue":"2","key":"39_CR9","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1137\/S0097539794278384","volume":"27","author":"M. Dyer","year":"1998","unstructured":"Dyer, M., Gritzmann, P., Hufnagel, A.: On the complexity of computing mixed volumes. SIAM J. Comput.\u00a027(2), 356\u2013400 (1998)","journal-title":"SIAM J. Comput."},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Classical deterministic complexity of Edmonds problem and Quantum entanglement. In: To appear in Proc. of 35 annual ACM symposium on theory of computing (STOC 2003), San Diego (2003)","DOI":"10.1145\/780542.780545"},{"key":"39_CR11","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0001-8708(81)90044-X","volume":"42","author":"G.P. Egorychev","year":"1981","unstructured":"Egorychev, G.P.: The solution of van der Waerden\u2019s problem for permanents. Advances in Math.\u00a042, 299\u2013305 (1981)","journal-title":"Advances in Math."},{"issue":"6","key":"39_CR12","first-page":"931","volume":"29","author":"D.I. Falikman","year":"1981","unstructured":"Falikman, D.I.: Proof of the van der Waerden\u2019s conjecture on the permanent of a doubly stochastic matrix. Mat. Zametki \u00a029(6), 931-938, 957 (1981) (in Russian)","journal-title":"Mat. Zametki (in Russian)"},{"key":"39_CR13","volume-title":"Algebraic Combinatorics","author":"C.D. Godsil","year":"1993","unstructured":"Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, Boca Raton (1993)"},{"key":"39_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Van der Waerden Conjecture for Mixed Discriminants. Advances in Mathematics (2005) (Available at the journal web page)","DOI":"10.1016\/j.aim.2004.12.002"},{"key":"39_CR16","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. Comput.\u00a018, 1149\u20131178 (1989)","journal-title":"SIAM J. Comput."},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial time approximation algorithm for the permanent of a matrix with non-negative entries, ECCC, Report No. 79 (2000)","DOI":"10.1145\/380752.380877"},{"key":"39_CR18","volume-title":"Proc. 32 ACM Symp. on Theory of Computing","author":"L. Gurvits","year":"2000","unstructured":"Gurvits, L., Samorodnitsky, A.: A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume. In: Proc. 32 ACM Symp. on Theory of Computing, ACM, New York (2000)"},{"issue":"2","key":"39_CR19","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/0222021","volume":"22","author":"N. Karmarkar","year":"1993","unstructured":"Karmarkar, N., Karp, R., Lipton, R., Lovasz, L., Luby, M.: A Monte-Carlo algorithm for estimating the permanent. SIAM J. Comput.\u00a022(2), 284\u2013293 (1993)","journal-title":"SIAM J. Comput."},{"key":"39_CR20","unstructured":"Vidal, G.: Efficient classical simulation of slightly entangled quantum computations (2003), available at http:\/\/arxiv.org\/abs\/quant-ph\/0301063"},{"key":"39_CR21","volume-title":"Proc. 30 ACM Symp. on Theory of Computing","author":"N. Linial","year":"1998","unstructured":"Linial, N., Samorodnitsky, A., Wigderson, A.: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. In: Proc. 30 ACM Symp. on Theory of Computing, ACM, New York (1998)"},{"issue":"2","key":"39_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Sohoni, M.: Geometric complexity theory 1: an approach to the P vs. NP and related problems. SIAM J. Comput.\u00a031(2), 496\u2013526","DOI":"10.1137\/S009753970038715X"},{"key":"39_CR24","volume-title":"Proc. 33 ACM Symp. on Theory of Computing","author":"L. Valiant","year":"2001","unstructured":"Valiant, L.: Quantum computers that can be simulated classically in polynomial time. In: Proc. 33 ACM Symp. on Theory of Computing, ACM, New York (2001)"},{"key":"39_CR25","unstructured":"Regan, K.: Understanding the Mulmeley-Sohoni approach to P vs. NP, unpublished manuscript (2002)"},{"key":"39_CR26","doi-asserted-by":"publisher","first-page":"5267","DOI":"10.1088\/0305-4470\/36\/19\/306","volume":"36","author":"J.-G. Luque","year":"2003","unstructured":"Luque, J.-G., Thibon, J.-Y.: Hankel hyperdeterminants and Selberg integrals. J.Phys.A: Math. Gen.\u00a036, 5267\u20135292 (2003)","journal-title":"J.Phys.A: Math. Gen."},{"key":"39_CR27","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: On the complexity of mixed discriminants and related problems, Los Alamos Unclassified Technical Report (2005)","DOI":"10.1007\/11549345_39"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549345_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:41:17Z","timestamp":1605624077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/11549345_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}