The Dual BKR Inequality and Rudich's Conjecture

DOI10.1017/S0963548310000465zbMath1237.05190OpenAlexW2102294749WikidataQ123242254 ScholiaQ123242254MaRDI QIDQ3081331

Jeffry Kahn, Clifford D. Smyth, Michael E. Saks

Publication date: 7 March 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548310000465

zbMATH Keywords

Berg-Kesten-Reimer (BKR)

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60) Combinatorial codes (94B25)

Related Items

The Journey from NP to TFNP Hardness ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ BK-type inequalities and generalized random-cluster representations ⋮ On constructing one-way permutations from indistinguishability obfuscation ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ On Constructing One-Way Permutations from Indistinguishability Obfuscation ⋮ Edge-statistics on large graphs

Cites Work

• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• On a combinatorial conjecture concerning disjoint occurrences of events
• Functional BKR inequalities, and their duals, with applications
• Inequalities with applications to percolation and reliability
• Proof of the Van den Berg–Kesten Conjecture
• Families of Non-disjoint subsets