TY - GEN
T1 - Local property reconstruction and monotonicity
AU - Saks, Michael
AU - Seshadhri, C.
N1 - Funding Information:
This is an extended abstract of work that will appear as “Local Monotonicity Reconstruction” in SIAM Journal on Computing [30]. A preliminary version of this work appeared as “Parallel Monotonicity Reconstruction” [29]. The work was supported in part by NSF under grants CCF-0515201 and CCF-0832787. It is partly based on material that appeared in the second author’s Ph.D. dissertation for the Department of Computer Science, Princeton University.
PY - 2010
Y1 - 2010
N2 - We propose a general model of local property reconstruction. Suppose we have a function f on domain Γ, which is supposed to have a particular property P, but may not have the property. We would like a procedure that produces a function g that has property P and is close to f (according to some suitable metric). The reconstruction procedure, called a filter, has the following form. The procedure takes as input an element x of Γ and outputs g(x). The procedure has oracle access to the function f and uses a single short random string ρ, but is otherwise deterministic. This model was inspired by a related model of online property reconstruction that was introduced by by Ailon, Chazelle, Comandur and Liu (2004). It is related to the property testing model, and extends the framework that is used in the model of locally decodable codes. A similar model, in the context of hypergraph properties, was independently proposed and studied by Austin and Tao (2008). We specifically consider the property of monotonicity and develop an efficient local filter for this property. The input f is a real valued function defined over the domain {1,...,n}d (where n is viewed as large and d as a constant). The function is monotone if the following property holds: for two domain elements x and y, if x ≤ y (in the product order) then f(x) ≤ f(y). Given x, our filter outputs the value g(x) in (logn) O(1) time and uses a random seed ρ of the same size. With high probability, the ratio of the Hamming distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n).
AB - We propose a general model of local property reconstruction. Suppose we have a function f on domain Γ, which is supposed to have a particular property P, but may not have the property. We would like a procedure that produces a function g that has property P and is close to f (according to some suitable metric). The reconstruction procedure, called a filter, has the following form. The procedure takes as input an element x of Γ and outputs g(x). The procedure has oracle access to the function f and uses a single short random string ρ, but is otherwise deterministic. This model was inspired by a related model of online property reconstruction that was introduced by by Ailon, Chazelle, Comandur and Liu (2004). It is related to the property testing model, and extends the framework that is used in the model of locally decodable codes. A similar model, in the context of hypergraph properties, was independently proposed and studied by Austin and Tao (2008). We specifically consider the property of monotonicity and develop an efficient local filter for this property. The input f is a real valued function defined over the domain {1,...,n}d (where n is viewed as large and d as a constant). The function is monotone if the following property holds: for two domain elements x and y, if x ≤ y (in the product order) then f(x) ≤ f(y). Given x, our filter outputs the value g(x) in (logn) O(1) time and uses a random seed ρ of the same size. With high probability, the ratio of the Hamming distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n).
UR - http://www.scopus.com/inward/record.url?scp=78449278264&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78449278264&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-16367-8_29
DO - 10.1007/978-3-642-16367-8_29
M3 - Conference contribution
AN - SCOPUS:78449278264
SN - 3642163661
SN - 9783642163661
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 346
EP - 354
BT - Property Testing - Current Research and Surveys
T2 - Mini-Workshop on Property Testing
Y2 - 8 January 2010 through 10 January 2010
ER -