23 citations · 149 across the 33 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
David Gamarnik, Elchanan Mossel, Ilias Zadik
We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough thre…
math.ST2023
Sharp thresholds in inference of planted subgraphs
Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn +2
A major question in the study of the Erdős--Rényi random graph is to understand the probability that it contains a given subgraph. This study originated in classical work of Erdős…