Given oracle access to some boolean function f, how many queries do we need to test whether f is linear? Or monotone? Or whether its output is completely determined by a small number of the input variables? This thesis studies these and related questions in the framework of prop…
"2" Result
Sort By:
The Lipschitz property is a fundamental property of functions with many applications in mathematics and computer science. Intuitively, a function is Lipschitz if it is not too sensitive to small changes in its inputs. In various applications, it is important (often crucial) that…