{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T21:23:20Z","timestamp":1783286600866,"version":"3.54.6"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2010,12,2]],"date-time":"2010-12-02T00:00:00Z","timestamp":1291248000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,3]]},"abstract":"Let <\/jats:private-char> be a set of terms over an arbitrary (but finite) number of Boolean variables. Let U<\/jats:italic>(<\/jats:private-char>) be the set of truth assignments that satisfy exactly one term in <\/jats:private-char>. Motivated by questions in computational complexity, Rudich conjectured that there exist \u220a, \u03b4 > 0 such that, if <\/jats:private-char> is any set of terms for which U<\/jats:italic>(<\/jats:private-char>) contains at least a (1\u2212\u220a)-fraction of all truth assignments, then there exists a term t<\/jats:italic> \u2208 <\/jats:private-char> such that at least a \u03b4-fraction of assignments satisfy some term of <\/jats:private-char> sharing a variable with t<\/jats:italic> [8].<\/jats:p>We prove a stronger version: for any independent assignment of the variables (not necessarily the uniform one), if the measure of U<\/jats:italic>(<\/jats:private-char>) is at least 1 \u2212 \u220a, there exists a t<\/jats:italic> \u2208 <\/jats:private-char> such that the measure of the set of assignments satisfying either t<\/jats:italic> or some term incompatible with t<\/jats:italic> (i.e.<\/jats:italic>, having no satisfying assignments in common with t<\/jats:italic>) is at least $\\Gd = 1- \\Ge - \\frac{4\\Ge}{1-\\Ge}$<\/jats:alt-text><\/jats:inline-graphic>. (A key part of the proof is a correlation-like inequality on events in a finite product probability space that is in some sense dual to Reimer's inequality [11], a.k.a. the BKR inequality [5], or the van den Berg\u2013Kesten conjecture [3].)<\/jats:p>","DOI":"10.1017\/s0963548310000465","type":"journal-article","created":{"date-parts":[[2010,12,2]],"date-time":"2010-12-02T11:58:46Z","timestamp":1291291126000},"page":"257-266","source":"Crossref","is-referenced-by-count":12,"title":["The Dual BKR Inequality and Rudich's Conjecture"],"prefix":"10.1017","volume":"20","author":[{"given":"JEFF","family":"KAHN","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MICHAEL","family":"SAKS","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"CLIFFORD","family":"SMYTH","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2010,12,2]]},"reference":[{"key":"S0963548310000465_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34799-2_2"},{"key":"S0963548310000465_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-007-0068-z"},{"key":"S0963548310000465_ref12","unstructured":"[12] Rudich S. (ca. 1990) Unpublished."},{"key":"S0963548310000465_ref16","unstructured":"[16] Tardos G. (ca. 1990) Unpublished."},{"key":"S0963548310000465_ref7","unstructured":"[7] Impagliazzo R. and Rudich S. Personal communication."},{"key":"S0963548310000465_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176992274"},{"key":"S0963548310000465_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399004113"},{"key":"S0963548310000465_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80012-1"},{"key":"S0963548310000465_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034241"},{"key":"S0963548310000465_ref14","unstructured":"[14] Szegedy M. (ca. 1990) Unpublished."},{"key":"S0963548310000465_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"S0963548310000465_ref13","first-page":"218","volume-title":"Proc. 34th Annual ACM Symposium on Theory of Computing","author":"Smyth","year":"2002"},{"key":"S0963548310000465_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200029326"},{"key":"S0963548310000465_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548310000465_ref4","first-page":"609","volume-title":"Infinite and Finite Sets: Colloq., Keszthely, 1973; Dedicated to P. Erd\u0151s on his 60th Birthday","author":"Erd\u0151s","year":"1975"},{"key":"S0963548310000465_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2000.856739"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000465","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T19:18:04Z","timestamp":1556392684000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000465\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,2]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["S0963548310000465"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000465","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,2]]}}}