Testing Lipschitz Functions on Hypergrid Domains
Testing Lipschitz Functions on Hypergrid Domains
复制标题
在超网格域上测试 Lipschitz 函数
DOI：
10.1007/s00453-015-9984-y
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
Raskhodnikova, Sofya
中科院分区：
文献类型：
--
作者：
Awasthi, Pranjal;Jha, Madhav;Molinaro, Marco;Raskhodnikova, Sofya
A function, where each input is an integer from 1 toand output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small changes in the input. Our main result is an efficient tester for the Lipschitz property of functions, whereandis the set of integer multiples of. A property tester is given an oracle access to a functionand a proximity parameter, and it has to distinguish, with high probability, functions that have the property from functions that differ on at least anfraction of values from every function with the property. The Lipschitz property was first studied by Jha and Raskhodnikova (FOCS’11) who motivated it by applications to data privacy and program verification. They presented efficient testers for the Lipschitz property of functions on the domainsand. Our tester for functions on the more general domainruns in timefor constantand. The main tool in the analysis of our tester is a smoothing procedure that makes a function Lipschitz by modifying it at a few points. Its analysis is already nontrivial for the 1-dimensional version, which we call Bubble Smooth, in analogy to Bubble Sort. In one step, Bubble Smooth modifies two values that violate the Lipschitz property, namely, differ by more than 1, by transferringunits from the larger to the smaller. We define atransfer graphto keep track of the transfers, and use it to show that thedistance betweenand BubbleSmoothis at most twice thedistance fromto the nearest Lipschitz function. Bubble Smooth has several other important properties that allow us to obtain adimension reduction, i.e., a reduction from testing functions on multidimensional domains to testing functions on one-dimensional domains. Our dimension reduction incurs only a small multiplicative overhead in the running time and thus avoids the exponential dependence on the dimension.
A function, where each input is an integer from 1 toand output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small changes in the input. Our main result is an efficient tester for the Lipschitz property of functions, whereandis the set of integer multiples of. A property tester is given an oracle access to a functionand a proximity parameter, and it has to distinguish, with high probability, functions that have the property from functions that differ on at least anfraction of values from every function with the property. The Lipschitz property was first studied by Jha and Raskhodnikova (FOCS’11) who motivated it by applications to data privacy and program verification. They presented efficient testers for the Lipschitz property of functions on the domainsand. Our tester for functions on the more general domainruns in timefor constantand. The main tool in the analysis of our tester is a smoothing procedure that makes a function Lipschitz by modifying it at a few points. Its analysis is already nontrivial for the 1-dimensional version, which we call Bubble Smooth, in analogy to Bubble Sort. In one step, Bubble Smooth modifies two values that violate the Lipschitz property, namely, differ by more than 1, by transferringunits from the larger to the smaller. We define atransfer graphto keep track of the transfers, and use it to show that thedistance betweenand BubbleSmoothis at most twice thedistance fromto the nearest Lipschitz function. Bubble Smooth has several other important properties that allow us to obtain adimension reduction, i.e., a reduction from testing functions on multidimensional domains to testing functions on one-dimensional domains. Our dimension reduction incurs only a small multiplicative overhead in the running time and thus avoids the exponential dependence on the dimension.