{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:54:00Z","timestamp":1764784440571},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00037-020-00196-6","type":"journal-article","created":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T08:03:49Z","timestamp":1595664229000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On $$\\epsilon$$-sensitive monotone computations"],"prefix":"10.1007","volume":"29","author":[{"given":"Pavel","family":"Hrube\u0161","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,25]]},"reference":[{"key":"196_CR1","doi-asserted-by":"crossref","unstructured":"A.\u00a0Atserias, A.\u00a0Dawar & J.\u00a0Ochremiak (2019). On the power of symmetric linear programs. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","DOI":"10.1109\/LICS.2019.8785792"},{"key":"196_CR2","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1016\/S0022-0000(02)00020-X","volume":"65","author":"A Atserias","year":"2002","unstructured":"Atserias, A., Galesi, N., Pudl\u00e1k, P.: Monotone simulations of non-monotone proofs. J. of Computer and System Sciences 65, 626\u2013638 (2002)","journal-title":"J. of Computer and System Sciences"},{"key":"196_CR3","doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack & M.F. Roy (2006). Algorithms in real algebraic geometry. Springer-Verlag.","DOI":"10.1007\/3-540-33099-2"},{"issue":"12","key":"196_CR4","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1016\/j.laa.2009.02.034","volume":"431","author":"L Beasley","year":"2009","unstructured":"Beasley, L., Laffey, T.: Real rank versus nonnegative rank. Linear Algebra and its Applications 431(12), 2330\u20132335 (2009)","journal-title":"Linear Algebra and its Applications"},{"key":"196_CR5","doi-asserted-by":"crossref","unstructured":"G.\u00a0Braun, S.\u00a0Fiorini, S.\u00a0Pokutta & D.\u00a0Steuer (2012). Approximation Limits of Linear Programs (Beyond Hierarchies). In FOCS, 480\u2013489","DOI":"10.1109\/FOCS.2012.10"},{"key":"196_CR6","doi-asserted-by":"crossref","unstructured":"P.\u00a0B\u00fcrgisser, M.\u00a0Clausen & M.\u00a0A. Shokrollahi (1997). Algebraic complexity theory, volume 315 of A series of comprehensive studies in mathematics. Springer","DOI":"10.1007\/978-3-662-03338-8"},{"key":"196_CR7","unstructured":"D.\u00a0deCaen, D.\u00a0Gregory & N.\u00a0Pullman (1981). The Boolean rank of zero one matrices. In Proceedings of the Third Caribean Conference on Combinatorics and Computing, 169\u2013173"},{"key":"196_CR8","doi-asserted-by":"crossref","unstructured":"Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans\u00a0Raj Tiwary & Ronald de\u00a0Wolf (2011). Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. CoRR arXiv:1111.0837","DOI":"10.1145\/2213977.2213988"},{"issue":"1","key":"196_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1137\/16M109884X","volume":"47","author":"M Goos","year":"2018","unstructured":"Goos, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. SIAM J. Comput. 47(1), 241\u2013269 (2018)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"196_CR10","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.ipl.2012.02.009","volume":"112","author":"P Hrube\u0161","year":"2012","unstructured":"Hrube\u0161, P.: On the nonnegative rank of distance matrices. Information Processing Letters 112(11), 457\u2013461 (2012)","journal-title":"Information Processing Letters"},{"key":"196_CR11","unstructured":"P.\u00a0Hrube\u0161 (2019). On the complexity of computing a random Boolean function over the reals. ECCC"},{"issue":"3","key":"196_CR12","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/s00037-011-0007-3","volume":"20","author":"Pavel Hrube\u0161 & Amir Yehudayoff","year":"2011","unstructured":"Pavel Hrube\u0161 & Amir Yehudayoff: Homogeneous formulas and symmetric polynomials. Computational Complexity 20(3), 559\u2013578 (2011)","journal-title":"Computational Complexity"},{"key":"196_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded arithmetic, propositional logic, and complexity theory","author":"J Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J.: Bounded arithmetic, propositional logic, and complexity theory. Cambridge University Press, USA (1995)"},{"key":"196_CR14","doi-asserted-by":"crossref","unstructured":"N.\u00a0Nisan (1991). Lower bounds for non-commutative computation. In Proceeding of the 23th STOC, 410\u2013418","DOI":"10.1145\/103418.103462"},{"key":"196_CR15","unstructured":"P.\u00a0Pudl\u00e1k & M.\u00a0de\u00a0Oliveira\u00a0Oliveira (2017). Representations of monotone Boolean functions by linear programs. In Proceedings of the 32nd Computational Complexity Conference"},{"key":"196_CR16","doi-asserted-by":"crossref","unstructured":"R.\u00a0Raz (2004). Multi-linear formulas for Permanent and Determinant are of super-polynomial size. In Proceeding of the 36th STOC, 633\u2013641","DOI":"10.1145\/1007352.1007353"},{"key":"196_CR17","doi-asserted-by":"crossref","unstructured":"A.\u00a0Razborov (1992). On submodular complexity measures. In Boolean functions complexity, 76\u201383. Cambridge University Press","DOI":"10.1017\/CBO9780511526633.007"},{"key":"196_CR18","doi-asserted-by":"crossref","unstructured":"T. Rothvoss (2017). The matching polytope has exponential extension complexity. J. of the ACM 64(6).","DOI":"10.1145\/3127497"},{"key":"196_CR19","doi-asserted-by":"crossref","unstructured":"Thomas Rothvo\u00df (2011). Some 0\/1 polytopes need exponential size extended formulations. CoRR arXiv:1105.0036","DOI":"10.1007\/s10107-012-0574-3"},{"issue":"1","key":"196_CR20","first-page":"301","volume":"13","author":"E Shamir","year":"1979","unstructured":"Shamir, E., Snir, M.: On the depth complexity of formulas. Journal Theory of Computing Systems 13(1), 301\u2013322 (1979)","journal-title":"Journal Theory of Computing Systems"},{"key":"196_CR21","unstructured":"Amir Shpilka & Avi Wigderson (1999). Depth-3 arithmetic formulae over fields of characteristic zero. In In CCC, 87. IEEE Computer Society"},{"issue":"3","key":"196_CR22","first-page":"207","volume":"5","author":"Amir Shpilka & Amir Yehudayoff","year":"2010","unstructured":"Amir Shpilka & Amir Yehudayoff: Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3), 207\u2013388 (2010)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"196_CR23","doi-asserted-by":"crossref","unstructured":"L.\u00a0G. Valiant (1979). Completeness Classes in Algebra. In STOC, 249\u2013261","DOI":"10.1145\/800135.804419"},{"key":"196_CR24","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0304-3975(80)90060-2","volume":"12","author":"LG Valiant","year":"1980","unstructured":"Valiant, L.G.: Negation can be exponentially powerful. Theoretical Computer Science 12, 303\u2013314 (1980)","journal-title":"Theoretical Computer Science"},{"key":"196_CR25","first-page":"253","volume":"28","author":"LG Valiant","year":"1982","unstructured":"Valiant, L.G.: Reducibility by algebraic projections. Enseign. Math. 28, 253\u2013268 (1982)","journal-title":"Enseign. Math."},{"issue":"2","key":"196_CR26","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/0215037","volume":"15","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G.: Negation is powerless for Boolean slice functions. SIAM J. Comput. 15(2), 531\u2013535 (1986)","journal-title":"SIAM J. Comput."},{"key":"196_CR27","doi-asserted-by":"crossref","unstructured":"S.\u00a0A. Vavasis (2008). On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization 20(3), 1364-1377","DOI":"10.1137\/070709967"},{"key":"196_CR28","doi-asserted-by":"crossref","unstructured":"I.\u00a0Wegener (1987). The complexity of Boolean functions","DOI":"10.1007\/3-540-18170-9_185"},{"issue":"3","key":"196_CR29","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"Mihalis Yannakakis","year":"1991","unstructured":"Yannakakis, Mihalis: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43(3), 441\u2013466 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"196_CR30","doi-asserted-by":"crossref","unstructured":"A.\u00a0Yehudayoff (2019). Separating monotone VP and VNP. In STOC","DOI":"10.1145\/3313276.3316311"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00196-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-020-00196-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00196-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T23:48:06Z","timestamp":1627170486000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-020-00196-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,25]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["196"],"URL":"https:\/\/doi.org\/10.1007\/s00037-020-00196-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,25]]},"assertion":[{"value":"6 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}