{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T11:40:16Z","timestamp":1739187616631,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642027765"},{"type":"electronic","value":"9783642027772"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02777-2_12","type":"book-chapter","created":{"date-parts":[[2009,6,26]],"date-time":"2009-06-26T06:58:18Z","timestamp":1245999498000},"page":"101-113","source":"Crossref","is-referenced-by-count":3,"title":["Variable Influences in Conjunctive Normal Forms"],"prefix":"10.1007","author":[{"given":"Patrick","family":"Traxler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"Bachrach, Y., Markakis, E., Procaccia, A.D., Rosenschein, J.S., Saberi, A.: Approximating power indices. In: Proc. of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 943\u2013950 (2008)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bachrach, Y., Rosenschein, J.S.: Computing the Banzhaf power index in network flow games. In: Proc. of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 335\u2013340 (2007)","DOI":"10.1145\/1329125.1329433"},{"key":"12_CR3","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)"},{"issue":"5","key":"12_CR4","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"R.B. Boppana","year":"1997","unstructured":"Boppana, R.B.: The average sensitivity of bounded-depth circuits. Information Processing Letters\u00a063(5), 257\u2013261 (1997)","journal-title":"Information Processing Letters"},{"issue":"3","key":"12_CR5","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","volume":"74","author":"C. Calabro","year":"2008","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of Unique k-SAT: An isolation lemma for k-CNFs. J. Computer and System Sciences\u00a074(3), 386\u2013393 (2008)","journal-title":"J. Computer and System Sciences"},{"issue":"4","key":"12_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics\u00a0156(4), 511\u2013529 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Furst, M.L., Jackson, J.C., Smith, S.W.: Improved learning of AC0 functions. In: Proc. of the 4th Annual ACM Conference on Computational Learning Theory, pp. 317\u2013325 (1991)","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"key":"12_CR8","unstructured":"Gomes, C.P., Sabharwal, A., Selman, B.: Model counting: A new strategy for obtaining good bounds. In: Proc. of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference (2006)"},{"issue":"3","key":"12_CR9","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1006\/jcss.2001.1803","volume":"63","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: A slight sharpening of LMN. J. Computer and System Sciences\u00a063(3), 498\u2013508 (2001)","journal-title":"J. Computer and System Sciences"},{"issue":"1","key":"12_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1093\/jigpal\/6.1.59","volume":"6","author":"E.A. Hirsch","year":"1998","unstructured":"Hirsch, E.A.: A fast deterministic algorithm for formulas that have many satisfying assignments. Logic Journal of the IGPL\u00a06(1), 59\u201371 (1998)","journal-title":"Logic Journal of the IGPL"},{"issue":"2","key":"12_CR11","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Computer and System Sciences\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Computer and System Sciences"},{"issue":"3","key":"12_CR12","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1017\/S0963548307008474","volume":"16","author":"J. Kahn","year":"2007","unstructured":"Kahn, J., Kalai, G.: Thresholds and expectation thresholds. Combinatorics, Probability and Computing\u00a016(3), 495\u2013502 (2007)","journal-title":"Combinatorics, Probability and Computing"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions. In: Proc. of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Kalai, G., Safra, S.: Threshold phenomena and influence, with some perspectives from mathematics, computer science, and economics. Discussion Paper Series dp398, Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem (August 2005)","DOI":"10.1093\/oso\/9780195177374.003.0008"},{"issue":"1","key":"12_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.mathsocsci.2004.06.002","volume":"49","author":"B. Klinz","year":"2005","unstructured":"Klinz, B., Woeginger, G.J.: Faster algorithms for computing power indices in weighted voting games. Mathematical Social Sciences\u00a049(1), 111\u2013116 (2005)","journal-title":"Mathematical Social Sciences"},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. J. ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"issue":"1-2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0304-3975(00)00251-6","volume":"263","author":"Y. Matsui","year":"2001","unstructured":"Matsui, Y., Matsui, T.: NP-completeness for calculating power indices of weighted majority games. Theoretical Computer Science\u00a0263(1-2), 305\u2013310 (2001)","journal-title":"Theoretical Computer Science"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity\u00a04, 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R.: Some topics in analysis of boolean functions. In: Proc. of the 40th Annual ACM Symposium on Theory of Computing, pp. 569\u2013578 (2008)","DOI":"10.1145\/1374376.1374458"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Saks, M.E., Schramm, O., Servedio, R.A.: Every decision tree has an influential variable. In: Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 31\u201339 (2005)","DOI":"10.1109\/SFCS.2005.34"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wimmer, K.: Approximation by DNF: Examples and counterexamples. In: Proc. of the 34th International Colloquium on Automata, Languages and Programming, pp. 195\u2013206 (2007)","DOI":"10.1007\/978-3-540-73420-8_19"},{"key":"12_CR22","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. Chicago J. Theoretical Computer Science\u00a01999(115) (1999)"},{"issue":"1","key":"12_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01753703","volume":"19","author":"K. Prasad","year":"1990","unstructured":"Prasad, K., Kelly, J.S.: NP-completeness of some problems concerning voting games. International Journal of Game Theory\u00a019(1), 1\u20139 (1990)","journal-title":"International Journal of Game Theory"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: A note on approximate counting for k-DNF. In: Proc. of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and 8th International Workshop on Randomization and Computation, pp. 417\u2013426 (2004)","DOI":"10.1007\/978-3-540-27821-4_37"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02777-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T11:13:24Z","timestamp":1739186004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02777-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642027765","9783642027772"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02777-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}