אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We show a directed and robust analogue of a Boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes O(\sqrt{n}/\eps^2) non-adaptive queries to a function f, always accepts a monotone function and rejects a function that is \eps-far from being monotone with constant probability.