On Monotonicity Testing and Boolean Isoperimetric-type Theorems

DOI10.1137/16M1065872zbMath1409.68142MaRDI QIDQ4562273

Shmuel Safra, Subhash A. Khot, Dor Minzer

Publication date: 19 December 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Boolean functions; property testing; monotonicity testing; Boolean isoperimetry

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

06E30: Boolean functions

68W20: Randomized algorithms