{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T11:16:23Z","timestamp":1649157383864},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T00:00:00Z","timestamp":1193443200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s00224-007-9067-9","type":"journal-article","created":{"date-parts":[[2007,10,26]],"date-time":"2007-10-26T12:05:48Z","timestamp":1193400348000},"page":"27-42","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice"],"prefix":"10.1007","volume":"45","author":[{"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,27]]},"reference":[{"key":"9067_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Determinism versus non-determinism for linear time RAMs with memory restrictions. In: 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 632\u2013641 (1999)","DOI":"10.1145\/301250.301424"},{"key":"9067_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: A non-linear time lower bound for boolean branching programs. In: 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 60\u201370 (1999)","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"9067_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Babai, L., Hajnal, P., Koml\u00f3s, J., Pudl\u00e1k, P., R\u00f6dl, V., Szemer\u00e9di, E., Tur\u00e1n, G.: Two lower bounds for branching programs. In: Proceedings of the 18th ACM Symposium on Theory of Computing (STOC), pp. 30\u201338 (1986)","DOI":"10.1145\/12130.12134"},{"key":"9067_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/3-540-48523-6_15","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP)","author":"A.E. Andreev","year":"1999","unstructured":"Andreev, A.E., Baskakov, J.L., Clementi, A.E.F., Rolim, J.D.P.: Smal pseudo-random sets yield hard functions: new tight explicit lower bounds for branching programs. In: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 1644, pp. 179\u2013189. Springer, Berlin (1999)"},{"key":"9067_CR5","doi-asserted-by":"crossref","unstructured":"Beame, P., Saks, M., Sun, X., Vee, E.: Super-linear time-space tradeoff lower bounds for randomized computation. In: 41th Annual Symposium on Foundations of Computer Science (FOCS), pp. 169\u2013179 (2000)","DOI":"10.1109\/SFCS.2000.892078"},{"issue":"2","key":"9067_CR6","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1145\/636865.636867","volume":"50","author":"P. Beame","year":"2003","unstructured":"Beame, P., Saks, M., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM 50(2), 154\u2013195 (2003)","journal-title":"J. ACM"},{"key":"9067_CR7","doi-asserted-by":"crossref","unstructured":"Beame, P., Saks, M., Thathachar, J.S.: Time-space tradeoffs for branching programs. In: 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 254\u2013263 (1998)","DOI":"10.1109\/SFCS.1998.743453"},{"issue":"4","key":"9067_CR8","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1006\/jcss.2001.1778","volume":"63","author":"P. Beame","year":"2001","unstructured":"Beame, P., Saks, M., Thathachar, J.S.: Time-space tradeoffs for branching programs. J. Comput. Syst. Sci. 63(4), 542\u2013572 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9067_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A.A., Smolensky, R.: On lower bounds for read-k-times branching programs. Comput. Complex. 3, 1\u201318 (1993)","journal-title":"Comput. Complex."},{"issue":"2","key":"9067_CR10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"R. Bryant","year":"1991","unstructured":"Bryant, R.: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. Comput. 40(2), 205\u2013213 (1991)","journal-title":"IEEE Trans. Comput."},{"key":"9067_CR11","doi-asserted-by":"crossref","unstructured":"Cobham, A.: The recognition problem for the set of perfect squares. In: Proceedings of the 7th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 78\u201387 (1966)","DOI":"10.1109\/SWAT.1966.30"},{"key":"9067_CR12","unstructured":"Jukna, S., Razborov, A.: Neither reading few bits twice nor reading illegally helps much. ECCC report TR96-037"},{"key":"9067_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/3-540-45687-2_34","volume-title":"Proceedings of the 27th International Symposium Mathematical Foundations of Computer Science (MFCS)","author":"J. K\u00e1ra","year":"2002","unstructured":"K\u00e1ra, J., Kr\u00e1l\u2019, D.: Optimal free binary decision diagrams for computation of EAR n . In: Proceedings of the 27th International Symposium Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 2420, pp. 411\u2013422. Springer, Berlin (2002)"},{"key":"9067_CR14","unstructured":"Pudl\u00e1k, P., \u017d\u00e1k, S.: Space complexity of computations. Math. Inst., \u010cSAV, Prague (1983) 30 pp."},{"key":"9067_CR15","first-page":"47","volume-title":"Lecture Notes in Computer Science, vol. 529","author":"A.A. Razborov","year":"1991","unstructured":"Razborov, A.A.: Lower bounds for deterministic and nondeterministic branching programs. In: Lecture Notes in Computer Science, vol. 529, pp. 47\u201361. Springer, Berlin (1991)"},{"key":"9067_CR16","unstructured":"Sauerhoff, M.: On nondeterminism versus randomness for read-once branching programs. Technical report in Electronic Colloquium on Computational Complexity (ECCC), TR97-030 (1997)"},{"key":"9067_CR17","series-title":"DIMACS Series in Discrete Mathematics","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1090\/dimacs\/013\/11","volume-title":"Advances in Computational Complexity","author":"J. Simon","year":"1993","unstructured":"Simon, J., Szegedy, M.: A new lower bound theorem for read only once branching programs and its applications. In: Cai, J. (ed.) Advances in Computational Complexity. DIMACS Series in Discrete Mathematics, vol. 13, pp. 183\u2013193. Am. Math. Soc., Providence (1993)"},{"key":"9067_CR18","doi-asserted-by":"crossref","unstructured":"Thathachar, J.S.: On separating the read-k-times branching program hierarchy. In: Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), pp. 653\u2013662 (1998)","DOI":"10.1145\/276698.276881"},{"key":"9067_CR19","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Teubner, Stuttgart (1987)"},{"issue":"2","key":"9067_CR20","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"Wegener, I.: On the complexity of branching programs and decision trees for clique functions. J. ACM 35(2), 461\u2013471 (1988)","journal-title":"J. ACM"},{"key":"9067_CR21","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams\u2014Theory and Applications","author":"I. Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams\u2014Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a04. SIAM, Philadelphia (2000)"},{"key":"9067_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0030340","volume-title":"Proceedings of the 11th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"S. \u017d\u00e1k","year":"1984","unstructured":"\u017d\u00e1k, S.: An exponential lower bound for one-time-only branching programs. In: Proceedings of the 11th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 176, pp. 562\u2013566. Springer, Berlin (1984)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9067-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9067-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9067-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9067-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,27]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["9067"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9067-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,27]]}}}