{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:33:03Z","timestamp":1725557583930},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_55","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T22:41:48Z","timestamp":1277246508000},"page":"612-621","source":"Crossref","is-referenced-by-count":2,"title":["On Converting CNF to DNF"],"prefix":"10.1007","author":[{"given":"Peter Bro","family":"Miltersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ingo","family":"Wegener","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"55_CR1","unstructured":"Beame, P.: A switching lemma primer. Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington (November 1994), Available online at \n                    \n                      www.cs.washington.edu\/homes\/beame\/"},{"key":"55_CR2","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0012-365X(79)90084-0","volume":"25","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: The tail of the hypergeometric distribution. Discrete Mathematics\u00a025, 285\u2013287 (1979)","journal-title":"Discrete Mathematics"},{"key":"55_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0020-0190(98)00042-8","volume":"66","author":"B. Bollig","year":"1998","unstructured":"Bollig, B., Wegener, I.: A very simple function that requires exponential size read-once branching programs. Information Processing Letters\u00a066, 53\u201357 (1998)","journal-title":"Information Processing Letters"},{"key":"55_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-45022-X_21","volume-title":"Automata, Languages and Programming","author":"E. Dantsin","year":"2000","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Sch\u00f6ning, U.: Deterministic algorithms for k-SAT based on covering codes and local search. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 236\u2013247. Springer, Heidelberg (2000)"},{"key":"55_CR5","doi-asserted-by":"crossref","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2\u2009\u2212\u20092\/(k\u2009+\u20091)\n                    n\n                   algorithm for k-SAT based on local search. Theoretical Computer Science (to appear)","DOI":"10.1016\/S0304-3975(01)00174-8"},{"key":"55_CR6","series-title":"Advances in Computing Research","first-page":"143","volume-title":"Randomness and Computation","author":"J. H\u00e5stad","year":"1989","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Micali, S. (ed.) Randomness and Computation. Advances in Computing Research, vol.\u00a05, pp. 143\u2013170. JAI Press, Greenwich (1989)"},{"key":"55_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-45841-7_15","volume-title":"STACS 2002","author":"T. Hofmeister","year":"2002","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A probabilistic 3-SAT algorithm further improved. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 192\u2013202. Springer, Heidelberg (2002)"},{"key":"55_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/3-540-45471-3_41","volume-title":"Algorithm Theory - SWAT 2002","author":"J. Katajainen","year":"2002","unstructured":"Katajainen, J., Madsen, J.N.: Performance tuning an algorithm for compressing relational tables. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 398\u2013407. Springer, Heidelberg (2002)"},{"key":"55_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2\n                    n\n                   steps. Discrete Applied Mathematics\u00a010, 287\u2013295 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"55_CR10","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e0k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: Proceedings of the 39th IEEE Symposium on the Foundations of Computer Science, pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"55_CR11","doi-asserted-by":"publisher","first-page":"755","DOI":"10.2307\/2310460","volume":"66","author":"W.V.O. Quine","year":"1959","unstructured":"Quine, W.V.O.: On cores and prime implicants of truth functions. American Mathematics Monthly\u00a066, 755\u2013760 (1959)","journal-title":"American Mathematics Monthly"},{"key":"55_CR12","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055, 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"55_CR13","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica\u00a032, 615\u2013623 (2002)","journal-title":"Algorithmica"},{"key":"55_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0890-5401(89)90047-3","volume":"83","author":"B. Voigt","year":"1989","unstructured":"Voigt, B., Wegener, I.: Minimal polynomials for the conjunctions of functions on disjoint variables an be very simple. Information and Computation\u00a083, 65\u201379 (1989)","journal-title":"Information and Computation"},{"key":"55_CR15","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley, Chichester (1987), Freely available via \n                    \n                      http:\/\/ls2-www.cs.uni-dortmund.de\/~wegener"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams \u2013 Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719789"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:57:45Z","timestamp":1552611465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}