{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:50:15Z","timestamp":1771573815019,"version":"3.50.1"},"reference-count":73,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000},"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":[[2021,6]]},"DOI":"10.1007\/s00037-020-00201-y","type":"journal-article","created":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T12:04:20Z","timestamp":1613131460000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling"],"prefix":"10.1007","volume":"30","author":[{"given":"Susanna F.","family":"De Rezende","sequence":"first","affiliation":[]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Robere","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,12]]},"reference":[{"key":"201_CR1","doi-asserted-by":"crossref","unstructured":"Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov & Avi Wigderson (2002). Space Complexity in Propositional Calculus. SIAM Journal on Computing 31(4), 1184\u20131211. Preliminary version in STOC '00","DOI":"10.1137\/S0097539700366735"},{"key":"201_CR2","doi-asserted-by":"crossref","unstructured":"Jo\u00ebl Alwen & Vladimir Serbinenko (2015). High Parallel Complexity Graphs and Memory-Hard Functions. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC '15), 595\u2013603","DOI":"10.1145\/2746539.2746622"},{"key":"201_CR3","unstructured":"Jo\u00ebl Alwen, Susanna F. de Rezende, Jakob Nordstr\u00f6m & Marc Vinyals (2017). Cumulative Space in Black-White Pebbling and Resolution. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS '17), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), 38:1\u201338:21"},{"key":"201_CR4","unstructured":"Albert Atserias & Tuomas Hakoniemi (2019). Size-Degree Trade- Offs for Sums-of-Squares and Positivstellensatz Proofs. In Proceedings of the 34th Annual Computational Complexity Conference (CCC '19), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), 24:1\u201324:20"},{"key":"201_CR5","doi-asserted-by":"crossref","unstructured":"Albert Atserias, Massimo Lauria & Jakob Nordstr\u00f6m (2016). Narrow Proofs May Be Maximally Long. ACM Transactions on Computational Logic 17(3), 19:1\u201319:30. Preliminary version in CCC '14","DOI":"10.1145\/2898435"},{"key":"201_CR6","doi-asserted-by":"crossref","unstructured":"Albert Atserias & Joanna Ochremiak (2019). Proof Complexity Meets Algebra. ACM Transactions on Computational Logic 20, 1:1\u20131:46. Preliminary version in ICALP '17","DOI":"10.1145\/3265985"},{"key":"201_CR7","doi-asserted-by":"crossref","unstructured":"Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo & Toniann Pitassi (1998). The Relative Complexity of NP Search Problems. Journal of Computer and System Sciences 57(1), 3\u201319. Preliminary version in STOC '95","DOI":"10.1006\/jcss.1998.1575"},{"key":"201_CR8","doi-asserted-by":"crossref","unstructured":"Paul Beame, Russell Impagliazzo, Jan Kraj\u00ed\u010dek, Toniann Pitassi & Pavel Pudl\u00e1k (1994). Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS '94), 794\u2013806","DOI":"10.1109\/SFCS.1994.365714"},{"key":"201_CR9","doi-asserted-by":"crossref","unstructured":"Chris Beck, Jakob Nordstr\u00f6m & Bangsheng Tang (2013). Some Trade-off Results for Polynomial Calculus. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC '13), 813\u2013822","DOI":"10.1145\/2488608.2488711"},{"key":"201_CR10","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson (2009). Size-Space Tradeoffs for Resolution. SIAM Journal on Computing 38(6), 2511\u20132525. Preliminary version in STOC '02","DOI":"10.1137\/080723880"},{"key":"201_CR11","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Jakob Nordstr\u00f6m (2008). Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), 709\u2013718","DOI":"10.1109\/FOCS.2008.42"},{"key":"201_CR12","unstructured":"Eli Ben-Sasson & Jakob Nordstr\u00f6m (2011). Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS '11), 401\u2013416"},{"key":"201_CR13","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Avi Wigderson (2001). Short Proofs are Narrow\u2014Resolution Made Simple. Journal of the ACM 48(2), 149\u2013169. Preliminary version in STOC '99","DOI":"10.1145\/375827.375835"},{"issue":"6","key":"201_CR14","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"Charles H Bennett","year":"1973","unstructured":"Bennett, Charles H.: Logical Reversibility of Computation. IBM Journal of Research and Development 17(6), 525\u2013532 (1973)","journal-title":"IBM Journal of Research and Development"},{"issue":"4","key":"201_CR15","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0218053","volume":"18","author":"Charles H Bennett","year":"1989","unstructured":"Bennett, Charles H.: Time\/Space Trade-offs for Reversible Computation. SIAM Journal on Computing 18(4), 766\u2013776 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"201_CR16","unstructured":"Christoph Berkholz (2018). The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS '18), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), 11:1\u201311:14"},{"key":"201_CR17","unstructured":"Archie Blake (1937). Canonical Expressions in Boolean Algebra. Ph.D. thesis, University of Chicago"},{"key":"201_CR18","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, John Tromp & Paul Vit\u00e1nyi (2001). Time and Space Bounds for Reversible Simulation. Journal of Physics A: Mathematical and general 34, 6821\u20136830. Preliminary version in ICALP '01","DOI":"10.1088\/0305-4470\/34\/35\/308"},{"key":"201_CR19","doi-asserted-by":"crossref","unstructured":"Joshua Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo & Toniann Pitassi (2002). Homogenization and the Polynomial Calculus. Computational Complexity 11(3-4), 91\u2013108. Preliminary version in ICALP '00","DOI":"10.1007\/s00037-002-0171-6"},{"key":"201_CR20","doi-asserted-by":"crossref","unstructured":"Samuel R. Buss (1998). Lower Bounds on Nullstellensatz Proofs via Designs. In Proof Complexity and Feasible Arithmetics, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59\u201371. American Mathematical Society. Available at http:\/\/www.math.ucsd.edu\/~sbuss\/ResearchWeb\/designs\/","DOI":"10.1090\/dimacs\/039\/04"},{"issue":"3","key":"201_CR21","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/BF01294258","volume":"6","author":"Samuel R Buss","year":"1997","unstructured":"Buss, Samuel R., Impagliazzo, Russell, Kraj\u00ed\u010dek, Jan, Pudl\u00e1k, Pavel, Razborov, Alexander A., Sgall, Ji\u0159\u00ed: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Computational Complexity 6(3), 256\u2013298 (1997)","journal-title":"Computational Complexity"},{"key":"201_CR22","doi-asserted-by":"crossref","unstructured":"Samuel R. Buss & Toniann Pitassi (1998). Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. Journal of Computer and System Sciences 2(57), 162\u2013171. Preliminary version in CCC '96","DOI":"10.1006\/jcss.1998.1585"},{"key":"201_CR23","doi-asserted-by":"crossref","unstructured":"David A. Carlson & John E. Savage (1980). Graph Pebbling with Many Free Pebbles Can Be Difficult. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC '80), 326\u2013332","DOI":"10.1145\/800141.804681"},{"issue":"5","key":"201_CR24","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0020-0190(82)90020-5","volume":"14","author":"David A Carlson","year":"1982","unstructured":"Carlson, David A., Savage, John E.: Extreme Time-Space Tradeoffs for Graphs with Small Space Requirements. Information Processing Letters 14(5), 223\u2013227 (1982)","journal-title":"Information Processing Letters"},{"key":"201_CR25","doi-asserted-by":"crossref","unstructured":"Siu Man Chan, Massimo Lauria, Jakob Nordstr\u00f6m & Marc Vinyals (2015). Hardness of Approximation in PSPACE and Separation Results for Pebble Games (Extended Abstract). In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS '15), 466\u2013485","DOI":"10.1109\/FOCS.2015.36"},{"key":"201_CR26","unstructured":"Siu Man Chan & Aaron Potechin (2014). Tight Bounds for Monotone Switching Networks via Fourier Analysis. Theory of Computing 10, 389\u2013419. Preliminary version in STOC '12"},{"key":"201_CR27","doi-asserted-by":"crossref","unstructured":"Ashok K. Chandra (1973). Efficient Compilation of Linear Recursive Programs. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT '73), 16\u201325","DOI":"10.1109\/SWAT.1973.7"},{"key":"201_CR28","doi-asserted-by":"crossref","unstructured":"Matthew Clegg, Jeffery Edmonds & Russell Impagliazzo (1996). Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), 174\u2013183","DOI":"10.1145\/237814.237860"},{"key":"201_CR29","doi-asserted-by":"crossref","unstructured":"Stephen A. Cook (1974). An Observation on Time-Storage Trade Off. Journal of Computer and System Sciences 9(3), 308\u2013316. Preliminary version in STOC '73","DOI":"10.1016\/S0022-0000(74)80046-2"},{"issue":"21\u201323","key":"201_CR30","doi-asserted-by":"publisher","first-page":"2054","DOI":"10.1016\/j.tcs.2009.01.002","volume":"410","author":"Stefan S Dantchev","year":"2009","unstructured":"Dantchev, Stefan S., Martin, Barnaby, Rhodes, Martin: Tight Rank Lower Bounds for the Sherali-Adams Proof System. Theoretical Computer Science 410(21\u201323), 2054\u20132063 (2009)","journal-title":"Theoretical Computer Science"},{"key":"201_CR31","doi-asserted-by":"crossref","unstructured":"Susanna F. de Rezende, Or Meir, Jakob Nordstr\u00f6m, Toniann Pitassi, Robert Robere & Marc Vinyals (2020). Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). To appear","DOI":"10.1109\/FOCS46700.2020.00011"},{"key":"201_CR32","unstructured":"Susanna F. de Rezende, Jakob Nordstr\u00f6m, Or Meir & Robert Robere (2019). Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. In Proceedings of the 34th Annual Computational Complexity Conference (CCC '19), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), 18:1\u201318:16"},{"key":"201_CR33","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork, Moni Naor & Hoeteck Wee (2005). Pebbling and Proofs of Work. In Proceedings of the 25th Annual International Cryptology Conference (CRYPTO '05), volume 3621 of Lecture Notes in Computer Science, 37\u201354. Springer","DOI":"10.1007\/11535218_3"},{"key":"201_CR34","doi-asserted-by":"crossref","unstructured":"Yuval Filmus, Toniann Pitassi, Robert Robere & Stephen A Cook (2013). Average Case Lower Bounds for Monotone Switching Networks. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS '13), 598\u2013607","DOI":"10.1109\/FOCS.2013.70"},{"issue":"3","key":"201_CR35","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"Ofer Gabber & Zvi Galil","year":"1981","unstructured":"Ofer Gabber & Zvi Galil: Explicit Constructions of Linear- Sized Superconcentrators. Journal of Computer and System Sciences 22(3), 407\u2013420 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"201_CR36","doi-asserted-by":"crossref","unstructured":"John R. Gilbert, Thomas Lengauer & Robert Endre Tarjan (1980). The Pebbling Problem is Complete in Polynomial Space. SIAM Journal on Computing 9(3), 513\u2013524. Preliminary version in STOC '79","DOI":"10.1137\/0209038"},{"key":"201_CR37","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev, Edward A. Hirsch & Dmitrii V. Pasechnik (2002). Exponential Lower Bound for Static Semi-algebraic Proofs. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP '02), volume 2380 of Lecture Notes in Computer Science, 257\u2013268. Springer","DOI":"10.1007\/3-540-45465-9_23"},{"key":"201_CR38","unstructured":"Mika G\u00f6\u00f6s, Pritish Kamath, Robert Robere & Dmitry Sokolov (2019). Adventures in Monotone Complexity and TFNP. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS '19), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), 38:1\u201338:19"},{"key":"201_CR39","doi-asserted-by":"crossref","unstructured":"Isidore Heller & Charles B. Tompkins (1957). An Extension of a Theorem of Dantzig's. In Linear Inequalities and Related Systems. (AM-38), Annals of Mathematics Studies, 247\u2013254. Princeton University Press","DOI":"10.1515\/9781400881987-015"},{"key":"201_CR40","doi-asserted-by":"crossref","unstructured":"John Hopcroft, Wolfgang Paul & Leslie Valiant (1977). On Time Versus Space. Journal of the ACM 24(2), 332\u2013337. Preliminary version in FOCS '75","DOI":"10.1145\/322003.322015"},{"issue":"2","key":"201_CR41","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s000370050024","volume":"8","author":"Russell Impagliazzo","year":"1999","unstructured":"Impagliazzo, Russell, Pudl\u00e1k, Pavel, Sgall, Ji\u0159\u00ed: Lower Bounds for the Polynomial Calculus and the Gr\u00f6bner Basis Algorithm. Computational Complexity 8(2), 127\u2013144 (1999)","journal-title":"Computational Complexity"},{"key":"201_CR42","doi-asserted-by":"crossref","unstructured":"Arist Kojevnikov & Dmitry Itsykson (2006). Lower Bounds of Static Lov\u00e1sz\u2013Schrijver Calculus Proofs for Tseitin Tautologies. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP '06), volume 4051 of Lecture Notes in Computer Science, 323\u2013334. Springer","DOI":"10.1007\/11786986_29"},{"key":"201_CR43","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.jcss.2017.07.009","volume":"91","author":"Balagopal Komarath","year":"2018","unstructured":"Komarath, Balagopal, Sarma, Jayalal, Sawlani, Saurabh: Pebbling meets coloring: Reversible pebble game on trees. Journal of Computer and System Sciences 91, 33\u201341 (2018)","journal-title":"Journal of Computer and System Sciences"},{"issue":"02","key":"201_CR44","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1051\/ita:2004008","volume":"38","author":"Richard Kr\u00e1lovi\u010d","year":"2004","unstructured":"Kr\u00e1lovi\u010d, Richard: Time and Space Complexity of Reversible Pebbling. RAIRO - Theoretical Informatics and Applications 38(02), 137\u2013161 (2004)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"201_CR45","unstructured":"Guillaume Lagarde, Jakob Nordstr\u00f6m, Dmitry Sokolov & Joseph Swernofsky (2020). Trade-offs Between Size and Degree in Polynomial Calculus. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS '20), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), 72:1\u201372:16"},{"issue":"2","key":"201_CR46","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1006\/jcss.1999.1672","volume":"60","author":"Klaus-J\u00f6rn Lange","year":"2000","unstructured":"Lange, Klaus-J\u00f6rn, McKenzie, Pierre, Tapp, Alain: Reversible Space Equals Deterministic Space. Journal of Computer and System Sciences 60(2), 354\u2013367 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"201_CR47","doi-asserted-by":"crossref","unstructured":"Thomas Lengauer & Robert Endre Tarjan (1982). Asymptotically Tight Bounds on Time-Space Trade-offs in a Pebble Game. Journal of the ACM 29(4), 1087\u20131130. Preliminary version in STOC '79","DOI":"10.1145\/322344.322354"},{"issue":"4","key":"201_CR48","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/0219046","volume":"19","author":"Robert Y Levin","year":"1990","unstructured":"Levin, Robert Y., Sherman, Alan T.: A Note on Bennett's Time-Space Tradeoff for Reversible Computation. SIAM Journal on Computing 19(4), 673\u2013677 (1990)","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20132","key":"201_CR49","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/S0167-2789(98)00052-9","volume":"120","author":"Ming Li","year":"1998","unstructured":"Li, Ming, Tromp, John, Vit\u00e1nyi, Paul: Reversible Simulation of Irreversible Computation. Physica D: Nonlinear Phenomena 120(1\u20132), 168\u2013176 (1998)","journal-title":"Physica D: Nonlinear Phenomena"},{"issue":"1947","key":"201_CR50","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1098\/rspa.1996.0039","volume":"452","author":"Ming Li & Paul Vit\u00e1nyi","year":"1996","unstructured":"Ming Li & Paul Vit\u00e1nyi: Reversibility and Adiabatic Computation: Trading Time and Space for Energy. Proceedings of the Royal Society of London, Series A 452(1947), 769\u2013789 (1996)","journal-title":"Proceedings of the Royal Society of London, Series A"},{"issue":"4","key":"201_CR51","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1017\/S0963548309009894","volume":"18","author":"Jes\u00fas A De Loera","year":"2009","unstructured":"De Loera, Jes\u00fas A., Lee, Jon, Margulies, Susan, Onn, Shmuel: Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz. Combinatorics, Probability and Computing 18(4), 551\u2013582 (2009)","journal-title":"Combinatorics, Probability and Computing"},{"key":"201_CR52","doi-asserted-by":"crossref","unstructured":"Giulia Meuli, Mathias Soeken, Martin Roetteler, Nikolaj Bj\u00f8rner & Giovanni De Micheli (2019). Reversible Pebbling Game for Quantum Memory Management. In Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE '19), 288\u2013291","DOI":"10.23919\/DATE.2019.8715092"},{"issue":"18","key":"201_CR53","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1016\/j.ipl.2009.06.006","volume":"109","author":"Jakob Nordstr\u00f6m","year":"2009","unstructured":"Nordstr\u00f6m, Jakob: A Simplified Way of Proving Tradeoff Results for Resolution. Information Processing Letters 109(18), 1030\u20131035 (2009)","journal-title":"Information Processing Letters"},{"key":"201_CR54","doi-asserted-by":"crossref","unstructured":"Jakob Nordstr\u00f6m (2012). On the Relative Strength of Pebbling and Resolution. ACM Transactions on Computational Logic 13(2), 16:1\u201316:43. Preliminary version in CCC '10","DOI":"10.1145\/2159531.2159538"},{"key":"201_CR55","doi-asserted-by":"crossref","unstructured":"Jakob Nordstr\u00f6m (2013). Pebble Games, Proof Complexity and Time-Space Trade-offs. Logical Methods in Computer Science 9(3), 15:1\u201315:63","DOI":"10.2168\/LMCS-9(3:15)2013"},{"key":"201_CR56","unstructured":"Jakob Nordstr\u00f6m (2020). New Wine into Old Wineskins: A Survey of Some Pebbling Classics with Supplemental Results. Manuscript in preparation. To appear in Foundations and Trends in Theoretical Computer Science. Current draft version available at http:\/\/www.csc.kth.se\/~jakobn\/research\/"},{"key":"201_CR57","unstructured":"Michael S. Paterson & Carl E. Hewitt (1970). Comparative Schematology. In Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, 119\u2013127"},{"issue":"2","key":"201_CR58","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0206022","volume":"6","author":"Nicholas Pippenger","year":"1977","unstructured":"Pippenger, Nicholas: Superconcentrators. SIAM Journal on Computing 6(2), 298\u2013304 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"201_CR59","unstructured":"Nicholas Pippenger (1980). Pebbling. Technical Report RC8258, IBM Watson Research Center. In Proceedings of the 5th IBM Symposium on Mathematical Foundations of Computer Science, Japan"},{"key":"201_CR60","doi-asserted-by":"crossref","unstructured":"Toniann Pitassi & Robert Robere (2017). Strongly Exponential Lower Bounds for Monotone Computation. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC '17), 1246\u20131255","DOI":"10.1145\/3055399.3055478"},{"key":"201_CR61","doi-asserted-by":"crossref","unstructured":"Toniann Pitassi & Robert Robere (2018). Lifting Nullstellensatz to Monotone Span Programs over Any Field. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC '18), 1207\u20131219","DOI":"10.1145\/3188745.3188914"},{"key":"201_CR62","doi-asserted-by":"crossref","unstructured":"Aaron Potechin (2010). Bounds on Monotone Switching Networks for Directed Connectivity. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS '10), 553\u2013562","DOI":"10.1109\/FOCS.2010.58"},{"key":"201_CR63","doi-asserted-by":"crossref","unstructured":"Pavel Pudl\u00e1k & Ji\u0159\u00ed Sgall (1998). Algebraic Models of Computation and Interpolation for Algebraic Proof Systems. In Proof Complexity and Feasible Arithmetics, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 279\u2013296. American Mathematical Society. Available at http:\/\/users.math.cas.cz\/~pudlak\/span.pdf","DOI":"10.1090\/dimacs\/039\/15"},{"key":"201_CR64","doi-asserted-by":"crossref","unstructured":"Robert Robere, Toniann Pitassi, Benjamin Rossman & Stephen A. Cook (2016). Exponential Lower Bounds for Monotone Span Programs. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS '16), 406\u2013415","DOI":"10.1109\/FOCS.2016.51"},{"key":"201_CR65","unstructured":"John E. Savage (1998). Models of Computation: Exploring the Power of Computing. Addison-Wesley. Available at http:\/\/www.modelsofcomputation.org"},{"key":"201_CR66","doi-asserted-by":"crossref","unstructured":"John E. Savage & Sowmitri Swamy (1979). Space-Time Tradeoffs for Oblivious Integer Multiplications. In Proceedings of the 6th International Colloquium on Automata, Languages and Programming (ICALP '79), 498\u2013504","DOI":"10.1007\/3-540-09510-1_40"},{"issue":"3","key":"201_CR67","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"Ravi Sethi","year":"1975","unstructured":"Sethi, Ravi: Complete Register Allocation Problems. SIAM Journal on Computing 4(3), 226\u2013248 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"201_CR68","doi-asserted-by":"crossref","unstructured":"John E. Savage & Sowmitri Swamy (1978). Space-Time Trade-offs on the FFT-algorithm. IEEE Transactions on Information Theory 24(5), 563\u2013568","DOI":"10.1109\/TIT.1978.1055938"},{"issue":"1","key":"201_CR69","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF01744566","volume":"16","author":"Sowmitri Swamy","year":"1983","unstructured":"Swamy, Sowmitri, Savage, John E.: Space-Time Tradeoffs for Linear Recursion. Mathematical Systems Theory 16(1), 9\u201327 (1983)","journal-title":"Mathematical Systems Theory"},{"issue":"5","key":"201_CR70","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a005","volume":"12","author":"Neil Thapen","year":"2016","unstructured":"Thapen, Neil: A Trade-off Between Length and Width in Resolution. Theory of Computing 12(5), 1\u201314 (2016)","journal-title":"Theory of Computing"},{"key":"201_CR71","doi-asserted-by":"crossref","unstructured":"Martin Tompa (1978). Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC '78), 196\u2013204","DOI":"10.1145\/800133.804348"},{"key":"201_CR72","unstructured":"Jacobo Tor\u00e1n & Florian W\u00f6rz (2020). Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS '20), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), 60:1\u201360:18"},{"key":"201_CR73","unstructured":"Ryan Williams (2000). Space-Efficient Reversible Simulations. Technical report, Cornell University. Available at http:\/\/web.stanford.edu\/~rrwill\/spacesim9_22.pdf"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00201-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-020-00201-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00201-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T04:00:24Z","timestamp":1624939224000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-020-00201-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,12]]},"references-count":73,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["201"],"URL":"https:\/\/doi.org\/10.1007\/s00037-020-00201-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,12]]},"assertion":[{"value":"31 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}