Local property reconstruction and monotonicity

Michael Saks, C. Seshadhri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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).

Original languageEnglish (US)
Title of host publicationProperty Testing - Current Research and Surveys
Pages346-354
Number of pages9
DOIs
StatePublished - 2010
EventMini-Workshop on Property Testing - Beijing, China
Duration: Jan 8 2010Jan 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6390 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherMini-Workshop on Property Testing
Country/TerritoryChina
CityBeijing
Period1/8/101/10/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Local property reconstruction and monotonicity'. Together they form a unique fingerprint.

Cite this