{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:23Z","timestamp":1763468123534},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,5,4]],"date-time":"2013-05-04T00:00:00Z","timestamp":1367625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1007\/s00037-013-0067-7","type":"journal-article","created":{"date-parts":[[2013,5,3]],"date-time":"2013-05-03T12:21:34Z","timestamp":1367583694000},"page":"245-274","source":"Crossref","is-referenced-by-count":19,"title":["A satisfiability algorithm and average-case hardness for formulas over the full binary basis"],"prefix":"10.1007","volume":"22","author":[{"given":"Kazuhisa","family":"Seto","sequence":"first","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,5,4]]},"reference":[{"issue":"1","key":"67_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"Ajtai Mikl\u00f3s","year":"1983","unstructured":"Mikl\u00f3s Ajtai (1983) $${\\Sigma^{1}_{1}}$$ -formulae on finite structures. Ann. Pure Appl. Logic 24(1): 1\u201348","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"67_CR2","first-page":"63","volume":"42","author":"A.E. Andreev","year":"1987","unstructured":"Andreev A.E. (1987) On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0-schemes. Moscow Univ. Math. Bull. 42(1): 63\u201366","journal-title":"Moscow Univ. Math. Bull."},{"key":"67_CR3","unstructured":"Vikraman Arvind & Rainer Schuler (2003). The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems. In Proceedings of the 14th Annual International Symposium on Algorithm and Computation (ISAAC), 168\u2013177."},{"key":"67_CR4","unstructured":"Armin Biere, Marijn Heule, Hans van Maaren & Toby Walsh (editors) (2009). Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications. IOS Press."},{"issue":"1","key":"67_CR5","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00039-007-0593-z","volume":"17","author":"Bourgain Jean","year":"2007","unstructured":"Jean Bourgain (2007). On the construction of affine-source extractors. Geometric and Functional Analysis 17(1): 33\u201357","journal-title":"Geometric and Functional Analysis"},{"key":"67_CR6","doi-asserted-by":"crossref","unstructured":"Chris Calabro, Russell Impagliazzo & Ramamohan Paturi (2006). A Duality between Clause Width and Clause Density for SAT. In Proceedings of the 21st Annual IEEE Conference Computational Complexity (CCC), 252\u2013260.","DOI":"10.1109\/CCC.2006.6"},{"key":"67_CR7","doi-asserted-by":"crossref","unstructured":"Chris Calabro, Russell Impagliazzo & Ramamohan Paturi (2009). The Complexity of Satisfiability of Small Depth Circuits. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC), 75\u201385.","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"67_CR8","unstructured":"Evgeny Dantsin & Edward A. Hirsch (2009). Worst-Case Upper Bounds. In Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, 403\u2013424. IOS Press."},{"key":"67_CR9","doi-asserted-by":"crossref","unstructured":"Evgeny Dantsin, Edward A. Hirsch & Alexander Wolpert (2004). Algorithms for SAT Based on Search in Hamming Balls. In Proceedings of the 21st Annual Symposuim on Theoretical Aspects of Computer Science (STACS), 141\u2013151.","DOI":"10.1007\/978-3-540-24749-4_13"},{"key":"67_CR10","doi-asserted-by":"crossref","unstructured":"Evgeny Dantsin, Edward A. Hirsch & Alexander Wolpert (2006). Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms. In Proceedings of the 6th Conference on Algorithms and Complexity (CIAC), 60\u201368.","DOI":"10.1007\/11758471_9"},{"key":"67_CR11","doi-asserted-by":"crossref","unstructured":"Merrick L. Furst, James B. Saxe & Michael Sipser (1984). Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1), 13\u201327","DOI":"10.1007\/BF01744431"},{"key":"67_CR12","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad (1986). Almost Optimal Lower Bounds for Small Depth Circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), 6\u201320.","DOI":"10.1145\/12130.12132"},{"issue":"1","key":"67_CR13","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"H\u00e5stad Johan","year":"1998","unstructured":"Johan H\u00e5stad (1998) The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput. 27(1): 48\u201364","journal-title":"SIAM J. Comput."},{"key":"67_CR14","doi-asserted-by":"crossref","unstructured":"Timon Hertli (2011). 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 277\u2013284.","DOI":"10.1109\/FOCS.2011.22"},{"key":"67_CR15","doi-asserted-by":"crossref","unstructured":"Edward A. Hirsch (2008). Exact Algorithms for General CNF SAT. In Encyclopedia of Algorithms. Springer-Verlag.","DOI":"10.1007\/978-0-387-30162-4_133"},{"key":"67_CR16","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, William Matthews & Ramamohan Paturi (2012). A satisfiability algorithm for AC0. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 961\u2013972.","DOI":"10.1137\/1.9781611973099.77"},{"issue":"2","key":"67_CR17","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/rsa.3240040202","volume":"4","author":"Impagliazzo Russell","year":"1993","unstructured":"Russell Impagliazzo, Noam Nisan (1993) The Effect of Random Restrictions on Formula Size. Random Struct. Algorithms 4(2): 121\u2013134","journal-title":"Random Struct. Algorithms"},{"key":"67_CR18","doi-asserted-by":"crossref","unstructured":"Xin Li (2011). A New Approach to Affine Extractors and Dispersers. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC), 137\u2013147.","DOI":"10.1109\/CCC.2011.27"},{"key":"67_CR19","unstructured":"Chi-Jen Lu & Hsin-Lung Wu (2010). On the Hardness against Constant-Depth Linear-Size Circuits. In Proceedings of the 16th Annual International Computings and Combinatorics Conference (COCOON), 13\u201322."},{"key":"67_CR20","doi-asserted-by":"crossref","unstructured":"Kazuhisa Makino, Suguru Tamaki & Masaki Yamamoto (2011). Derandomizing HSSW Algorithm for 3-SAT. In Proceedings of the 17th Annual International Computings and Combinatorics Conference (COCOON), 1\u201312.","DOI":"10.1007\/978-3-642-22685-4_1"},{"key":"67_CR21","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"Monien Burkhard","year":"1985","unstructured":"Burkhard Monien, Ewald Speckenmeyer (1985) Solving satisfiability in less than 2 n steps. Discrete Applied Mathematics 10: 287\u2013295","journal-title":"Discrete Applied Mathematics"},{"key":"67_CR22","unstructured":"Robin A. Moser & Dominik Scheder (2011). A Full Derandomization of Sch\u00f6ning\u2019s k-SAT Algorithm. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 245\u2013252."},{"issue":"2","key":"67_CR23","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan, Avi Wigderson (1994) Hardness vs Randomness. J. Comput. Syst. Sci. 49(2): 149\u2013167","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"67_CR24","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"Paturi Ramamohan","year":"2005","unstructured":"Ramamohan Paturi, Pavel Pudl\u00e1k, Michael E. Saks, Francis Zane (2005) An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337\u2013364","journal-title":"J. ACM"},{"key":"67_CR25","unstructured":"Ramamohan Paturi, Pavel Pudl\u00e1k & Francis Zane (1999). Satisfiability Coding Lemma. Chicago J. Theor. Comput. Sci. 1999, 19 pages."},{"key":"67_CR26","doi-asserted-by":"crossref","unstructured":"Pavel Pudl\u00e1k (1998). Satisfiability - Algorithms and Logic. In Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 129\u2013141.","DOI":"10.1007\/BFb0055762"},{"key":"67_CR27","doi-asserted-by":"crossref","unstructured":"Rahul Santhanam (2010). Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. In Proceedings of the 51st International Symposium on Foundations of Computer Science (FOCS), 183\u2013192.","DOI":"10.1109\/FOCS.2010.25"},{"key":"67_CR28","doi-asserted-by":"crossref","unstructured":"Uwe Sch\u00f6ning (1999). A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), 410\u2013414.","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"1","key":"67_CR29","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.jalgor.2004.04.012","volume":"54","author":"Schuler Rainer","year":"2005","unstructured":"Rainer Schuler (2005) An algorithm for the satisfiability problem of formulas in conjunctive normal form. J. Algorithms 54(1): 40\u201344","journal-title":"J. Algorithms"},{"key":"67_CR30","first-page":"110","volume":"2","author":"B.A. Subbotovskaya","year":"1961","unstructured":"Subbotovskaya B.A. (1961) Realizations of linear functions by formulas using and, or, not. Soviet Mathematics Doklady 2: 110\u2013112","journal-title":"Soviet Mathematics Doklady"},{"key":"67_CR31","doi-asserted-by":"crossref","unstructured":"Ryan Williams (2010). Improving exhaustive search implies superpolynomial lower bounds. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 231\u2013240.","DOI":"10.1145\/1806689.1806723"},{"key":"67_CR32","doi-asserted-by":"crossref","unstructured":"Ryan Williams (2011). Non-uniform ACC Circuit Lower Bounds. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC), 115\u2013125.","DOI":"10.1109\/CCC.2011.36"},{"key":"67_CR33","unstructured":"Andrew Chi-Chih Yao (1985). Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version). In Proceedings of the 26th International Symposium on Foundations of Computer Science (FOCS), 1\u201310."},{"issue":"2","key":"67_CR34","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00493-011-2604-9","volume":"31","author":"Yehudayoff Amir","year":"2011","unstructured":"Amir Yehudayoff (2011) Affine extractors over prime fields. Combinatorica 31(2): 245\u2013256","journal-title":"Combinatorica"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0067-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0067-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0067-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T10:43:37Z","timestamp":1563014617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0067-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,4]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["67"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0067-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,4]]}}}