FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 |

«Abstract. For positive integers n, d, consider the hypergrid [n]d with the coordinate-wise product partial ordering denoted by. A function f : [n]d ...»

-- [ Page 1 ] --

An Optimal Lower Bound for Monotonicity

Testing over Hypergrids

Deeparnab Chakrabarty1 and C. Seshadhri2


Microsoft Research India



Sandia National Labs, Livermore


Abstract. For positive integers n, d, consider the hypergrid [n]d with

the coordinate-wise product partial ordering denoted by. A function

f : [n]d → N is monotone if ∀x y, f (x) ≤ f (y). A function f is ε-

far from monotone if at least an ε-fraction of values must be changed to make f monotone. Given a parameter ε, a monotonicity tester must distinguish with high probability a monotone function from one that is ε-far.

We prove that any (adaptive, two-sided) monotonicity tester for func- tions f : [n]d → N must make Ω(ε−1 d log n − ε−1 log ε−1 ) queries. Recent upper bounds show the existence of O(ε−1 d log n) query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of Ω(d log n).

Keywords: Monotonicity testing, sublinear algorithms, lower bounds 1 Introduction Given query access to a function f : D → R, the field of property testing [1,2] deals with the problem of determining properties of f without reading all of it. Monotonicity testing [3] is a classic problem in property testing. Consider a function f : D → R, where D is some partial order given by “ ”, and R is a y (in D), f (x) ≤ f (y).

total order. The function f is monotone if for all x The distance to monotonicity of f is the minimum fraction of values that need to be modified to make f monotone. More precisely, define the distance between functions d(f, g) as |{x : f (x) = g(x)}|/|D|. Let M be the set of all monotone functions. Then the distance to monotonicity of f is ming∈M d(f, g).

A function is called ε-far from monotone if the distance to monotonicity is at least ε. A property tester for monotonicity is a, possibly randomized, algorithm that takes as input a distance parameter ε ∈ (0, 1), error parameter δ ∈ [0, 1], Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.

and query access to an arbitrary f. If f is monotone, then the tester must accept with probability 1 − δ. If it is ε-far from monotone, then the tester rejects with probability 1 − δ. (If neither, then the tester is allowed to do anything.) The aim is to design a property tester using as few queries as possible. A tester is called one-sided if it always accepts a monotone function. A tester is called nonadaptive if the queries made do not depend on the function values. The most general tester is an adaptive two-sided tester.

Monotonicity testing has a rich history and the hypergrid domain, [n]d, has received special attention. The boolean hypercube (n = 2) and the total order (d = 1) are special instances of hypergrids. Following a long line of work [4,3,5,6,7,8,9,10,11,12,13,14], previous work of the authors [15] shows the existence of O(ε−1 d log n)-query monotonicity testers. Our result is a matching adaptive lower bound that is optimal in all parameters (for unbounded range functions). This closes the question of monotonicity testing for unbounded ranges on hypergrids. This is also the first adaptive bound for monotonicity testing on general hypergrids.

Theorem 1. Any (adaptive, two-sided) monotonicity tester for functions f :

[n]d → N requires Ω(ε−1 d log n − ε−1 log ε−1 ) queries.

1.1 Previous work The problem of monotonicity testing was introduced by Goldreich et al. [3], with an O(n/ε) tester for functions f : {0, 1}n → {0, 1}. The first tester for general hypergrids was given by Dodis et al. [5]. The upper bound of O(ε−1 d log n) for monotonicity testing was recently proven in [15]. We refer the interested reader to the introduction of [15] for a more detailed history of previous upper bounds.

There have been numerous lower bounds for monotonicity testing. We begin by summarizing the state of the art. The known adaptive lower bounds are Ω(log n) for the total order [n] by Fischer [9], and Ω(d/ε) for the boolean hypercube {0, 1}d by Brody [16]. For general hypergrids, Blais, Raskhodnikova, and Yaroslavtsev [17] recently proved the first result, a non-adaptive lower bound of Ω(d log n). Theorem 1 is the first adaptive bound for monotonicity testing on hypergrids and is optimal (for arbitrary ranges) in all parameters.

Now for the chronological documentation. The first lower bound was the non-adaptive bound of Ω(log n) for the total order [n] by Ergun et al. [4]. This was extended by Fischer [9] to an (optimal) adaptive bound. For the hypercube domain {0, 1}d, Fischer et al. [7] proved the first non-adaptive lower bound of √ Ω( d). (This was proven even for the range {0, 1}.) This was improved to Ω(d/ε) by Br¨ et al. [18]. Blais, Brody, and Matulef [14] gave an ingenious reduction ıet from communication complexity to prove an adaptive, two-sided bound of Ω(d).

(Honing this reduction, Brody [16] improved this bound to Ω(d/ε).) The nonadaptive lower bounds of Blais, Raskhodnikova, and Yaroslavtsev [17] were also achieved through communication complexity reductions.

We note that our theorem only holds when the range is N, while some previous results hold for restricted ranges. The results of [14,16] provide lower bounds for √ range [ d]. The non-adaptive bound of [17] holds even when the range is [nd].

In that sense, the communication complexity reductions provide stronger lower bounds than our result.

1.2 Main ideas

The starting point of this work is the result of Fischer [9], an adaptive lower bound for monotonicity testing for functions f : [n] → N. He shows that adaptive testers can be converted to comparison-based testers, using Ramsey theory arguments. A comparison-based tester for [n] can be easily converted to a non-adaptive tester, for which an Ω(log n) bound was previously known. We make a fairly simple observation. The main part of Fischer’s proof actually goes through for functions over any partial order, so it suffices to prove lower bounds for comparison-based testers. (The reduction to non-adaptive testers only holds for [n].) We then prove a comparison-based lower bound of Ω(ε−1 d log n−ε−1 log ε−1 ) for the domain [n]d. As usual, Yao’s minimax lemma allows us to focus on determinstic lower bounds over some distribution of functions. The major challenge in proving (even non-adaptive) lower bounds for monotonicity is that the tester might make decisions based on the actual values that it sees. Great care is required to construct a distribution over functions whose monotonicity status cannot be decided by simply looking at the values. But a comparison-based tester has no such power, and optimal lower bounds over all parameters can be obtained with a fairly clean distribution.

2 The reduction to comparison based testers Consider the family of functions f : D → R, where D is some partial order, and R ⊆ N. We will assume that f always takes distinct values, so ∀x, y, f (x) = f (y).

Since we are proving lower bounds, this is no loss of generality.

Definition 1. An algorithm A is a (t, ε, δ)-monotonicity tester if A has the following properties. For any f : D → R, the algorithm A makes t (possibly randomized) queries to f and then outputs either “accept” or “reject”. If f is monotone, then A accepts with probability 1 − δ. If f is ε-far from monotone, then A rejects with probability 1 − δ.

–  –  –

Eq. (1) ensures the decisions of the tester at step (s + 1) must form a probability distribution. Eq. (2) implies that the tester makes at most t queries.

For any positive integer s, let R(s) denote the set of unordered subets of R of cardinality s. For reasons that will soon become clear, we introduce new functions as follows. For each s, x ∈ Ds, y ∈ D, and each permutation σ : [s] → [s], we associate functions qx,σ : R(s) → [0, 1], with the semantic y

–  –  –

function on R(s). In other words, the (s + 1)th decision of the tester given that the first s questions is x, depends only on the ordering of the answers received, and not on the values of the answers.

The following theorem is implicit in the work of Fischer [9].

Theorem 2. Suppose there exists a (t, ε, δ)-monotonicity tester for functions f : D → N.

Then there exists a comparison-based (t, ε, 2δ)-monotonicity tester for functions f : D → N.

This implies that a comparison-based lower bound suffices for proving a general lower bound on monotonicity testing. We provide a proof of the above theorem in the next section for completeness.

–  –  –

Furthermore, prej (a) ≥ prej (a).

ˆx x The p-functions describe a new discrete tester A that makes at most t ˆ queries. We argue that A is a (t, ε, 2δ)-tester. Given a function f that is either monotone or ε-far from monotone, consider a sequence of queries x1,..., xs after which A returns a correct decision ℵ. Call such a sequence good, and let α denote the probability this occurs. We know that the sum of probabilities over all good query sequences is at least (1 − δ). Now, α := px1 · px2 (f (x1 )) · px31,x2 ) (f (x1 ), f (x2 )) · · · · pℵ 1,...,xs ) (f (x1 ),..., f (xs )) x1 (x (x Two cases arise. Suppose all of the probabilities in the RHS are ≥ 10t/δK.

Then, the probability of this good sequence arising in A is at least (1−δ/10t)t α ≥ α(1 − δ/2). Otherwise, suppose some probability in the RHS is 10t/δK. Then the total probability mass on such good sequences in A is at most 10t/δK · |D|t ≤ δ/2. Therefore, the probability of good sequences in A is at least (1 − 3δ/2)(1 − δ/2) ≥ 1 − 2δ. That is, A is a (t, ε, 2δ) tester.

We introduce some Ramsey theory terminology. For any positive integer i, a finite coloring of N(i) is a function coli : N(i) → {1,..., C} for some finite number C. An infinite set X ⊆ N is called monochromatic w.r.t coli if for all sets A, B ∈ X (i), coli (A) = coli (B). A k-wise finite coloring of N is a collection of k colorings col1,..., colk. (Note that each coloring is over different sized tuples.) An infinite set X ⊆ N is k-wise monochromatic if X is monochromatic w.r.t. all the coli s.

The following is a simple variant of Ramsey’s original theorem. (We closely follow the proof of Ramsey’s theorem as given in Chap VI, Theorem 4 of [19].) Theorem 3. For any k-wise finite coloring of N, there is an infinite k-wise monochromatic set X ⊆ N.

Proof. We proceed by induction on k. If k = 1, then this is trivially true; let X be the maximum color class. Since the coloring is finite, X is infinite. We will now iteratively construct an infinite set of N via induction.

Start with a0 being the minimum element in N. Consider a (k − 1)-wise coloring of (N \ {a0 }) col1,..., colk−1, where coli (S) := coli+1 (S ∪ a0 ). By the induction hypothesis, there exists an infinite (k − 1)-wise monochromatic set A0 ⊆ N \ {a0 } with respect to coloring coli s. That is, for 1 ≤ i ≤ k, and any set 0 S, T ⊆ A0 with |S| = |T | = i − 1, we have coli (a0 ∪ S) = coli (a0 ∪ T ) = Ci, 0 0 0 say. Denote the collection of these colors as a vector C0 = (C1, C2,..., Ck ).

Subsequently, let a1 be the minimum element in A0, and consider the (k −1)wise coloring col of (A0 \ {a1 }) where coli (S) = coli+1 (S ∪ {a1 }) for S ⊆ A0 \ {a1 }. Again, the induction hypothesis yields an infinite (k − 1)-wise monochromatic set A1 as before, and similarly the vector C1. Continuing this procedure, we get an infinite sequence a0, a1, a2,... of natural numbers, an infinite sequence of vectors of k colors C0, C1,..., and an infinite nested sequence of infinite sets A0 ⊃ A1 ⊃ A2.... Every Ar contains as, ∀s r and by construction, any set i ({ar } ∪ S), S ⊆ Ar, |S| = i − 1, has color Cr. Since there are only finitely many colors, some vector of colors occurs infinitely often as Cr1, Cr2,.... The corresponding infinite sequence of elements ar1, ar2,... is k-wise monochromatic.

Proof. (of Theorem 2) Suppose there exists a (t, ε, δ)-tester for functions f :

D → N. We need to show there is a comparison-based (t, ε, 2δ)-tester for such functions.

By Lemma 1, there is a discrete (t, ε, 2δ)-tester A. Equivalently, we have the y functions qx,σ as described in the previous section. We now describe a t-wise finite coloring of N. Consider s ∈ [t]. Given a set A ⊆ N(s), cols (A) is a vector indexed by (y, x, σ), where y ∈ D, x ∈ Ds, and σ is a s-permutation, whose y entry is qx,σ (A). The domain is finite, so the number of dimensions is finite. Since the tester is discrete, the number of possible colors entries is finite. Applying Theorem 3, we know the existence of a t-wise monochromatic infinite set R ⊆ N.

We have the property that for any y, x, σ, and any two sets A, B ∈ R(s), we have y y qx,σ (A) = qx,σ (B). That is, the algorithm A is a comparison based tester for functions with range R.

Consider the strictly monotone map φ : N → R, where φ(b) is the bth element of R in sorted order. Now given any function f : D → N, consider the function φ ◦ f : D → R. Consider an algorithm A which on input f runs A on φ ◦ f.

More precisely, whenever A queries a point x, it gets answer φ ◦ f (x). Observe that if f is monotone (or ε-far from monotone), then so is φ ◦ f, and therefore, the algorithm A is a (t, ε, 2δ)-tester of φ ◦ f. Since the range of φ ◦ f is R, A is comparison-based.

3 Lower bounds

We assume that n is a power of 2, set := log2 n, and think of [n] as {0, 1,..., n− 1}. For any number 0 ≤ z n, we think of the binary representation of z as an

-bit vector (z1, z2,..., z ), where z1 is the least significant bit.

Consider the following canonical, one-to-one mapping φ : [n]d → {0, 1}d.

Pages:   || 2 |

Similar works:

«CURRICULUM VITAE PER ASLAK MYKLAND July 2009 Department of Statistics mykland@galton.uchicago.edu University of Chicago http://galton.uchicago.edu/∼mykland/ 5734 University Ave. phone: + 1 (773) 702 8044/8333 Chicago, IL 60637 fax: + 1 (773) 702 9810 USA EDUCATION Ph.D. University of California, Berkeley, 1989 (Statistics) M.Sc. (Cand.Scient.) University of Bergen (Norway), 1984 (Statistics) B.Sc. (Cand.Mag.) University of Bergen (Norway), 1983 (Mathematics/Computer Science) Baccalaur´at e...»

«Testimony of Ann F. Miles Director, Office of Energy Projects Federal Energy Regulatory Commission 888 First Street, N.E. Washington, DC, 20426 202-502-8700 Committee on Energy and Commerce Subcommittee on Energy and Power United States House of Representatives Hearing on Discussion Drafts Addressing Hydropower Regulatory Modernization and FERC Process Coordination under the Natural Gas Act May 13, 2015 Chairman Whitfield, Ranking Member Rush, and Members of the Subcommittee: My name is Ann...»

«The Factory of Facts and Other Writings DZIGA VERTOV translated by KEVIN O'BRIAN On the Film Kino-Glazl The world's first attempt to create a film-object without the participation of actors, artists, directors; without using a studio, sets, costumes. All members of the cast continue doing what they usually do in life. The present film represents an assault on our reality by movie cameras, and prepares the theme of creative labor against a background of class contradictions and of everyday life....»

«1. The frigate Méduse On 17 June 1816, a French naval convoy led by the frigate Méduse, under the command of Hugues Duroy de Chaumareys (a Royalist and Captain lacking real naval experience, appointed by king Louis XVIII) departed Rochefort harbor, accompanied by the storeship Loire, the brig Argus and the corvette Écho, to receive the British handover of the port of Saint-Louis in Senegal. The Méduse carried passengers, including the appointed French governor of Senegal, Colonel...»

«GUÍA DE ATENCIÓN MÉDICA PARA MIEMBROS SU GUÍA DE COBERTURA MÉDICA AmeriCorps NCCC FEMA Corps ÍNDICE 2 Inscripción 2 Credencial de identificación 2 Pérdida o extravío de credenciales 3 Contacto 3 Sitio Web 4 Portal seguro para miembros 5 Coordinación de beneficios 6 Copago 6 Afecciones preexistentes 7 Servicios cubiertos 7 Servicios de emergencia 7 Servicios de hospitalización 7 Alojamiento y comidas 8 Servicios profesionales 8 Medicamentos recetados 8 Atención obstétrica 9...»

«How to Read Like a Writer by Mike Bunn This essay is a chapter in Writing Spaces: Readings on Writing, Volume 2, a peer-reviewed open textbook series for the writing classroom.Download the full volume and individual chapters from: • Writing Spaces: http://writingspaces.org/essays • Parlor Press: http://parlorpress.com/writingspaces • WAC Clearinghouse: http://wac.colostate.edu/books/ Print versions of the volume are available for purchase directly from Parlor Press and through other...»

«Sensors 2012, 12, 7080-7094; doi:10.3390/s120607080 OPEN ACCESS sensors ISSN 1424-8220 www.mdpi.com/journal/sensors Article Quartz Crystal Microbalance Aptasensor for Sensitive Detection of Mercury(II) Based on Signal Amplification with Gold Nanoparticles Zong-Mu Dong 1 and Guang-Chao Zhao 1,2,* 1 College of Environmental Science and engineering, Anhui Normal University, Wuhu 241000, China; E-Mail: dzongmu@mail.ahnu.edu.cn 2 Anhui Key Laboratory of Chem-Biosensing, School of Chemistry and...»

«2016-2017 CHARTERING PACKET Club Name: Instructions for Chartering a Student Club Thank you for picking up an application to become an Edmonds Community College Student Club. This is your opportunity to gather students together and involve them in activities that enhance not only the student club but student life at Edmonds Community College. Please do not hesitate to ask questions, find support and get involved with Student Programs. We are here to support you and your club’s efforts....»

«XA9847627 Chapter 30 NUCLEAR IMAGING OF THE SKELETAL SYSTEM Yong Whee Bahk Introduction Bone may well present as a mere inert weight-bearing scaffold of the human body to those who acquired the anatomical knowledge of the skeleton with the aid of dried bone specimens. Nevertheless, like all other active organ systems, the bone changes dynamically as it undergoes incessant turnover with modelling and remodelling through the physiological and metabolic activities of osteoblasts and osteoclasts....»

«380 Alien Intrusion prove a pet theory. Masquerading angels have also concocted a pseudophilosophy to closely parallel the texts for their own evil aims. The Bible has become “fair game” for those with their own agenda. I recall an investigator at a UFO meeting glowingly using the passage in Ezekiel to say that “even the Bible mentions UFOs.” When I challenged his comment, pointing out that nowhere does Ezekiel use the term “ship,” “craft,” or any other word to describe a...»

«COLECCIÓN Pastoral Fe y Alegría 5 COLECCIÓN Pastoral Fe y Alegría Publicaciones de temas teológico – pastorales trabajados en la perspectiva de la educación popular, bajo responsabilidad del Área de Educación y Desarrollo Integral Popular (AEDIP), Equipo Pastoral de Fe y Alegría – Ecuador Ulloa N 34 – 141 y Lallement, Quito Tel:(02) 2245 155 e–mail:falegria@andinanet.net pastoralfya@yahoo.com 1. Primer Encuentro Latinoamericano de Pastoral de Fe y Alegría.Documentos VVAA 2....»

«Town of Waynesville, NC Board of Aldermen – Regular Meeting Town Hall, 9 South Main Street, Waynesville, NC 28786 Date: January 12, 2016 Time: 6:30 p.m. The agenda and all related documentation may be accessed electronically at www.waynesvillenc.gov. Click on “Government/Mayor & Board” to download materials for town board meetings. Consider the environment  Conserve resources  Print only when necessary The Town of Waynesville provides accessible facilities, programs and services for...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.