Probabilistic testing of Boolean functions or, How to test locally for a global property by Krzysztof Michal Majewski B . S c , M c G i l l University, 1998 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T O F THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE . in The Faculty of Graduate Studies (Department of Computer Science) We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH C O L U M B I A June 6, 2003 © Krzysztof Michal Majewski, 2003 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer Science The University of British Columbia Vancouver, Canada Abstract ii Abstract Probabilistic testing is a general problem that has fundamental scientific value as well as direct applications to important concepts in theoretical computer science, such as probabilistically checkable proofs (PCP). We consider specifically the testing of Boolean functions, discussing some key existing results and providing new results for several classes of functions. In particular, we give efficient tests for a Boolean function to be symmetric (invariant under permutation of its variables) and quasi-symmetric (a symmetric function of the variables it actually depends on). Contents iii Contents Abstract ii Contents iii 1 2 3 Introduction 1 1.1 Motivation 1 1.2 What is testing? 2 1.2.1 Basic definitions 2 1.2.2 Characterizing functions 3 Previous results 6 2.1 Monotone functions 6 2.1.1 6 Result Results 9 3.1 Self-dual functions 9 3.2 Symmetric functions 9 3.3 Quasi-monadic functions 10 3.4 Quasi-symmetric functions 14 Bibliography 20 Chapter 1. Introduction 1 Chapter 1 Introduction 1.1 Motivation The problem of testing comes up in the study of self-testing and self-correcting programs [12]. This in turn has applications to probabilistically checkable proofs [1, 2]. Probabilistically checkable proofs are especially important because they have been shown to yield an alternative characterization of the complexity class NP, and this in turn has led to proofs of the intractability of approximation problems [3, 4]. Checking a function (program) P for correctness can be done in two phases. The first phase tests whether P has a given property. If so, the second phase then checks if P is indeed the correct function, using a test that depends on the property holding. Testing whether a function is a low-degree polynomial [12] and whether various representations of a graph satisfy certain properties [6, 9, 10] are wellstudied problems: This work considers only Boolean functions, that is, functions with domain {0,1}™ and range {0,1}. We look at tests for membership in the following families: • Monotone functions • Self-dual functions • Symmetric functions • Quasi-monadic functions • Quasi-symmetric functions 2 Chapter 1. Introduction We present some previous results from the literature and some new results. In particular, we give efficient tests for a Boolean function to be symmetric (invariant under permutation of its variables) and quasi-symmetric (a symmetric function of the variables it actually depends on). The underlying theme of this work is how to test locally for a global property. 1.2 What is testing? 1.2.1 Basic definitions Boolean function A Boolean function is a function / : {0,1}" — > {0,1}. We can write Boolean functions as arithmetic expressions over Z^. For example: excl(x,y) — x + y is the function which takes on value 1 if and only if the inputs x and y differ. Family A family is a possibly infinite set of functions which possess a given property. One example is the family of monotone functions. Distance The distance d(f, g) between two functions / and g with domain D is \{x € D.f(x) ^ g(x)}\. The distance between function g and family T is minf y^d(f,g). e Function / is said to be e-far from' (respectively, e-close to) T if ^ \ ^ > (respectively, <) e. d Boolean lattice Consider the domain D = {0,1}" of binary strings XQX\ ... x . n Define the relation < on D by x < y <=J> Vi.{x, < yi). This is a partial order P on D. The smallest element is the string 0.. .0, the largest element is the string 1... 1. The Boolean lattice is the lattice formed by P. Chapter 1. Introduction 3 Boolean algebra A Boolean algebra is a Boolean lattice L in which every point x £ L has a complement x, and any two points x, y in the lattice can be combined using a disjunction operator V or a conjunction operator A to obtain a new point in L. Weight The weight of a point in the Boolean lattice is the number of ones it contains. Row A row of the Boolean lattice is the set containing all points of a given weight, and only those points. The w row is the row containing exactly the points of th weight w. Sensitivity Consider the Boolean algebra D = {0, l } and Boolean function / : D —» {0,1}. n Define N = {1,... , n}. Let flip : D x N x £ D and i £ N, flips the i th —> D be the operation which, given bit in x to obtain a new point y £ D. We say that / is sensitive to variable i £ N if there exists a point x £ D such that f(x) 1.2.2 f{flip(x,i)). Characterizing functions We want to know what properties hold of a function. Recall that we seek a local test for a global property, that is, membership in some family T. A characterization is a formalization of a property. (A property may have more than one characterization.) We are interested in characterizations to the extent that they yield tests. The following definitions are adapted from [12]. Chapter 1. Introduction 4 Exact local characterizations Consider Boolean functions on Boolean algebra D, and fc-tuples of input points (xi,X2,... ,Xk) G D . k A k-local property V is a formula A / . A ( x i , . . .,x ).R(xi,.. .,x ,f(xi),... k where R C D k x {0, l} fc k f(x )) k is some relation on /c-tuples of input points and their images under / . For example, the following is a 2-local property: A/.A(xi,x ).{xi < x 2 2 — • /(xi) < /(x )} 2 A function / satisfies fc-local property V when V(f)(xi,..., ( x i , . . . ,Xfc) € D . k x) k holds for all A fc-local property V is an exact k-local characterization of a family T when / satisfies V iff / € T. The 2-local property in the above example is an exact local characterization of the family of monotone functions: it is satisfied for all pairs of input points ( x i , X 2 ) iff / is monotone. Robust characterizations Given a fc-local characterization V of T, suppose we sample the fc-tuples using a probability distribution p on D . k V is (p, 5, t)-robust if, under the distribution p, f fails to satisfy V on at least a weighted fraction 5 of the fc-tuples when / is e-far from T. In the monotonicity example above, suppose p assigns equal probability to those pairs {(x,y) : x < y} where x and y differ in exactly one bit, and zero probability to all other pairs. It turns out that this yields a (p, e/n , 3 e)-robust characterization of the monotone functions (see Section 2.1). Robustness implies that, on average, the local property V will have something to say about the global feature, membership in T. In particular, it quantifies the relationship between the local test and the global feature in terms of the relationship between 5 and e. Efficiency We are interested in characterizations which are not only local, exact, and robust, but also efficient. The complexity of a (p, 5, e)-robust characterization is Chapter 1. Introduction 5 given by 1/(5. This is the number offc-tuplesa test must sample for the expected number of "P-violating tuples to be 1 if / is indeed e-far from T. In particular, we are interested in characterizations (tests) with complexity polynomial in n, for any n-adic Boolean function to be tested. Test A test for membership in T is an implementation of a robust exact local characterization of T. A test must accept a function / with high probability if / G T. 1 A test must reject f with high probability if / is e-far from T. Otherwise, the test may accept or reject / arbitrarily. We define high probability to be 2/3. 2 Query complexity The query complexity of a test is the number of samples the test takes. A sample is the evaluation of /.at air the points in a single fc-tuple. 1 Some definitions, for example [7, 8], require that functions in J be always accepted. That 7 is, by those definitions, a test cannot produce false negatives. 2 I n fact, this can be any probability greater than 1/2. To see this, imagine running the test k times. If it accepts most of the time, then / is probably in T. By making k arbitrarily large, we can achieve arbitrarily high accuracy. If we disallow false negatives, we can replace 2/3 with any non-zero probability. Chapter 2. Previous results 6 Chapter 2 Previous results 2.1 Monotone functions Goldreich et al. [7, 8] present a monotonicity test of complexity poly(n/e). This test samples the function at arguments of its choice. The authors also analyze testing with random examples, and discuss extensions to other domains and ranges. We summarize their main result here. . 2.1.1 • • Result The test selects a random x G {0,1}" and i G 1,..., n. We obtain y from x by flipping the i th bit in x. The test rejects if x, y is a monotonicity-violating tuple. Otherwise the steps above are repeated up to n /e times. Let 5M (/) denote the 3 fraction of such pairs (x, y) which violate monotonicity for a function / . Let e(/) be the distance of / from the family of monotone functions. The main result is 0M\J) > —r- from which the correctness of the test follows. Strategy The result is proved with the aid of two lemmas. The first lemma shows the existence of a particular matching between two large sets R and S of vertices (points) in the Boolean n-lattice. The weights of the points in R are disjoint from the weights of the points in S. The matching maps vertices x in R to vertices y in S, such that x -< y but f(x) > f(y). The second lemma shows that Chapter 2. Previous results 7 for any such matching there exist vertex disjoint paths from one set to the other. If x and y are the endpoints of such a path, then since x <y and f(x) > f(y), it follows that the path contains an edge (x',y') with x' ~< y' and f(x') > f(y'). In other words, at some point along the path the value of / decreases while the input increases. Then (x',y') is a monotonicity-violating pair. The size of the sets R and S is shown to be at at least ( e M ( / ) / 2 n ) • 2™. 2 Since vertex disjointness implies edge disjointness, and every path contains a violating pair, there are at least (eM(/)/2n ) • 2™ violating edges (pairs). The 2 total number of edges in the Boolean n-lattice is \ •• 2 • n. The fraction of n violating edges is then (^f- • 2")'/(§ • 2" • n) = e (f)/n , 3 M which is the result. Extensions The authors prove two theorems about monotonicity testing with random examples. The first gives a lower bound on the number of such examples needed by a monotonicity tester. The second shows that this bound is tight up to a poly(n) factor. Recall that when we sample the function / at arguments of our choosing, the number of samples required is 0( °^^). p In the case of uni- formly and independently chosen random examples, however, this number is fi(V2"/e (/)). M Also presented are two generalizations of the main result. The first extends the monotonicity test to unate functions. A unate function can be viewed as a monotone function with a constant exclusive-or bitmask applied to its inputs. For a monotone function, the output can't decrease if one of the input bits is flipped up (from a zero to a one). Each input bit to a unate function, on the other hand, is either an "up" bit or a "down" bit. The value of the function can't decrease if an "up" bit is flipped up or a "down" bit is flipped down. The extended test has complexity 0 ( n / e M ( / ) ) 3 5 The second generalization treats extended domains and ranges. The complexity of this algorithm scales quadratically with the domain size and linearly with the range. Chapter 2. Previous results 8 The paper also poses the problem of whether there exist monotonicity testing algorithms for which the number of required samples is independent of n. Chapter 3. Results 9 Chapter 3 Results 3.1 Self-dual functions A Boolean function / over Boolean algebra D is self-dual if Va; g D {f(x) = f(x)}. Let S be the set of self-dual functions over D. A function / is e-far from self-dual if d(f,S) > e. If we choose 1/e points at random, we expect one bad point, that is, a point x such that f(x) =fc f{x). The number k of points that must be chosen to obtain a probability at least 2/3 of hitting a bad point is given by l-(l-e) > f c 2/3 or, equivalently, k > In 3 •ln(l - e ) Since — ln(l — e) > e, it suffices to take In 3 This is the complexity of our test. Note that this complexity is independent of n. 3.2 Symmetric functions A function / is symmetric if weight(x) = weight(y) —> f(x) = f(y). If / is e-far from symmetric, we would have to change its value on at least e2™ points Chapter 3. Results 10 to get a symmetric function. Choose any minimal set of such points, and call these points bad. Now, uniformly choose a point x in the domain. With probability e, x is bad. Now choose (again uniformly) another point y, such that weight(x) = weight(y). We call (x,y) a symmetric pair. We call this pair a violating pair if f(x) ^ f(y)- Consider that at most half the points of a given weight can be bad (otherwise, our set of bad points is not minimal). The probability that (x,y) is a violating pair is then at least e/2. By the same argument as in the preceding section, it suffices to choose |~_ i n ( i - e / 2 ) ] — l"^eHH symmetric pairs in this fashion to have probability at least 2/3 of finding a violating pair. This yields a 0(1 /e) symmetry test in the obvious way, since a violating pair is a witness to the asymmetry of / . 3.3 Quasi-monadic functions A Boolean function / is quasi-monadic if it is sensitive to at most one of its input variables [5, 11]. We give an 0(n/e) test for quasi-monadicity. First of all, here is an 0(1/e) test which always accepts if / is the projection function proj(n,i), and rejects with high probability if / is e-far from proj(n, i). Algorithm 3.3.1: PROJ~(i,/) main Result <— ACCEPT repeat up to ^ times Uniformly choose a point x in the domain < Let Xi be the value in point x of the i-th variable i f(x) ^ f [ Xi {Result <- until Result = return (Result) REJECT REJECT Chapter 3. Results 11 If / is proj(n, i), rejection will never happen, and the test accepts. If / is e-far from proj(n, i), it means that on an e-fraction of the domain, f(x) =£ proj(n, i) and thus f(x) j£ X j . So if we choose 0(1/e) points, we expect to find at least one such "bad" point. Similarly, here's an 0(1/e) test which always accepts if / is the negated projection function ->proj(n,i), and rejects with high probability if / is e-far from -^proj(n, i). A l g o r i t h m 3.3.2: N O T P R O j ( i , / ) main Result «- ACCEPT repeat u p t o ^ times Uniformly choose a point x in the domain Let Xi be the value in point x of the i-th variable if f(x) =xi ^Result«u n t i l Result = REJECT REJECT r e t u r n (Result) Here's an 0(1/e) test which always accepts if / is the constant function constl, and rejects with high probability if / is e-far from constl. A l g o r i t h m 3.3.3: C O N S T l ( / ) main Result <- ACCEPT repeat u p to ^ ' times Uniformly choose a point x in the domain jif/(s)^l [ ^Result <- u n t i l Result = r e t u r n (Result) REJECT REJECT Chapter 3. Results 12 If / is constl, rejection will never happen, and the test accepts. If / is e-far from constl, it means that on an e-fraction of the domain, f(x) ^ 1. So if we choose 0(l/e) points, we expect to find at least one such "bad" point. Similarly, here's an 0(l/e) test which always accepts if / is the constant function constO, and rejects with high probability if / is e-far from constO. Algorithm 3 . 3 . 4 : CONST0(/) main Result <- ACCEPT repeat up to ^ times ("Uniformly choose a point x in the domain < if f(x) ^ 0 Result <until Result = return (Result) REJECT REJECT 13 Chapter 3. Results Now for the quasi-monadicity test. Algorithm 3 . 3 . 5 : QUASIMONADICITY^/) main Result <— CONSTU(/) if Result = ACCEPT return (Result) Result <— CONSTl(/) if Result = ACCEPT return (Result) for each variable i in the domain do Result <— PROj(i,/) if Result = ACCEPT break Result <— NOTPROj(l, /) if Result = ACCEPT break v return (Result) If / is quasi-monadic, it must be a constant function, or a projection function, or a negated projection function. In each of these cases, QUASIMONADICITY accepts. If / is e-far from quasi-monadic, it must be e-far from every quasi-monadic function. Thus, CONSTO, C O N S T I , PROJ(I), and NOTPROJ(I) will all reject, and the test rejects. CONSTO, C O N S T I , PROJ(I), and NOTPROJ(I) all have running time 0(l/e), since they sample 1/e points and perform an 0(1) computation on each point. The for loop in QUASIMONADICITY runs at most n times, so has complexity 0(n/e). QUASIMONADICITY Chapter 3. Results 3.4 14 Quasi-symmetric functions We now move on to the quasi-symmetric functions, that is, functions which are symmetric if we consider only their significant inputs [5, 11]. Given function / on Boolean algebra D = Pow(N), let / ' be the section of./ to the Boolean algebra D' = Pow(N'), where N' C N contains exactly those variables in N to which / is sensitive. Then / is quasi-symmetric iff / ' is symmetric. Since quasi-symmetry is more general than symmetry, the symmetry test is now too strict: two points with same weight and different image need not be a counterexample (namely, if the points swap a significant bit with a differently valued insignificant bit). In other words, the symmetry test gives false negatives when applied to a quasi-symmetric function. Our test proceeds in two phases. The first phase attempts to isolate the significant inputs of / . The second phase performs a symmetry test (as in Section 3.2) on a section of / to those variables which have been discovered in the first phase. Although Phase I may or may not succeed in finding all the significant variables, all the variables in X are guaranteed to be significant. Since the symmetry test of Phase II is performed on only those variables, there can be no false negatives - / is rejected only if it is not quasi-symmetric. Algorithm 3.4.1: main J <- P H A S E J ( / ) PHASE JI(-/,J) QUASISYMMETRY(/) Chapter 3. Results Algorithm 3.4.2: procedure Z«- PHASE_I(/) PHASEJ(/) 0 while true repeat up to k times { Uniformly choose an assignment w t o l Uniformly choose a pair (w.x, w.y) (w need not be a prefix) do { until f(w.x) ^ f(w.y) if f{w.x) = f{w.y) else then break % <- W A L K ( / , i u , a ; , y ) IU{ } t return (X) procedure WALK(/, W, X, y) Walk from x to y until you encounter two points x', y' such that x' differs from y' on exactly one bit i, and f(w.x') ^ f(w.y'). return (i) 15 Chapter 3. Results Algorithm 16 3.4.3: P H A S E _ I I ( / ) procedure P H A S E _ I I ( / , X ) Result <- ACCEPT repeat up to k times { / ' < — R E S T R I C T ( / , J , z) Result <— S Y M M E T R Y ( / ' ) until Result = REJECT return (Result) procedure RESTRICT^/, Z, z) D *— Variables of / assign z to D — X / ' <— Restriction of / given z return (/') procedure SYMMETRY(/) Perform one step of the symmetry test [Section 3.2] on / It remains to show that the test is complete, in the sense that / is indeed rejected with probability at least 2/3 if it is e-far from quasi-symmetric. The following analysis will establish the completeness of the test and determine its efficiency. Phase I maintains as loop invariant the set X of significant variables found at each step. Let Fx be the family of n-adic functions that depend on only the set X. Let g € Fx be a function in Fj that is closest to / . Let B = e/5. We now consider two cases - Case I, where d(f, g) > 8; and Case II, where d(f, g) < 8. In the following, we choose "51n6" > In 6 •ln(l-e/5) Chapter 3. IT Results Consider a given iteration of the outer while loop of P H A S E J . Suppose Case I holds at this moment. The probability of reaching the break statement in this iteration is simply the probability that f(w.x) = f(w.y) in each of the k trials: Pr(break) = Pr(f(w.x) = f(w.y)) k = (1-Pr(f(w.x)^f(w.y))) k = (1-<*(/, )) fc 5 < 1/6 by the above choice of A;. Thus, the probability of breaking out of the outer loop prematurely is acceptably low. In other words, when we eventually break out of the loop, it is likely that we are in Case II, which we now analyze. Let QS be the set of n-adic quasisymmetric functions. B y the triangle inequality, we know that d(f,QS) < d(f,g) + d(g,QS). In Case II, we know that d(f, g) is small. Now, we are interested in the situation where / is at least e-far from QS (since we've already shown the test accepts functions in QS, and we're allowed to be wrong for. functions that are e-close to QS). So if d(f, QS) is at least e, and d(f, g) is at most /3, then d(g, QS) must be at least e — f3 = 4/3. Let S be the set of i-adic symmetric functions, where i = \T\. d We have d(g(-,z),S) > d(g,QS) 1 (since g{-,z) is the same for all z). So d(g(-, z), S) is also at least 4/3. Now, d(f,g) 1 = 2-" f(*)^9(x) = 2— J2 2 - ^ . % , T h e notation <?(•, z) refers t o the i-adic function obtained by fixing the values for variables not i n I t o the bits of z. Chapter 3. Results = J2 T~ n 18 d(f(;z),g(-,z)). Recall that d(f, g) is at most (3. B y Markov's inequality, the probability of picking a z such that d(f(-,z),g(-,z)) < 2(3 is at least 1/2. Combining the last two paragraphs with another use of the triangle inequality, we obtain d(g(; ),S) < d(f(; ),S)+d(f(;z),g(;z)),OT d(f(.,z),S) > d(g(;z),S)-d(f(;z),g(;z)) Z Z > (4/3)-2/? = 2e/5 with probability at least 1/2. Weighing this by the probability 1/2 from the previous paragraph, we obtain e/5 as the lower bound on the probability of rejecting an / e-far from QS (in Case II). We have already shown there can be no false negatives. Thus the probability that none of the k iterations in Phase II rejects / is at most (l-e/5) f c < 1/6. There are two ways a false positive might happen: 1. Case I holds at the end of Phase I (and thus we make no claims about the ability of Phase II to reject / ) , or, 2. Case II holds at the end of Phase I, and yet despite this Phase II fails to reject / . We have seen that each of these possibilities has probability at most 1/6. Thus we reject a function that is e-far from QS with probability at least 2/3. It is easy to see that procedure WALK has complexity 0(n). Consider the n-hypercube. O n any path from x to y, f(x) ^ f(y), there must be a pair of points (x\ y'), f(y') / f(x'), such that x' and y' differ on exactly one bit. Thus it is sufficient to arbitrarily pick any such path, and walk along it until one finds (x',y'). T h e length of a path is at most n. Chapter 3. Results 19 The outer while loop of Phase I executes O(n) times, since \I\ is at most n. Each inner while loop executes at most 0(kn) times, giving a total complexity of 0(n ) for Phase I. 2 Phase II has complexity O(k), since it consists of at most k iterations of the symmetry test from Section 3.2. This gives us a grand total of 0(n ). Given that k is 0(1/e), the complexity 2 of the quasi-symmetry test is 0(n /e). 2 Chapter 4. Conclusions 20 Chapter 4 Conclusions We have considered tests for several common properties of Boolean functions. These tests, by implementing a characterization of the family of functions satisfying the given property, are able to reveal some combinatorial properties of this family which can be interesting in their own right. Moreover, these tests rely on local characterizations of properties which are, by definition, global over the boolean n-lattice. The complexity of a test is a measure of the relationship between this local characterization and the global one. The complexities of the tests are in all cases dependent on e, the maximum distance beyond which a family and a putative member are no longer considered "close". This is not surprising, since e is the main parameter governing the classification performed by the test - in the language of Probably Almost Correct (PAC) algorithms, it is the value of "Almost". Moreover, this dependence on e is always linear (that is, 0(l/e) is a factor in the complexity). The complexities of some tests - namely, the monotonicity test of [7, 8], the quasi-monadicity test, and the quasi-symmetry test - are also dependent on n, the arity of the given function. Others (the symmetry test and the self-duality test) are not. This is perhaps more surprising in the case of symmetry than it is for the more obviously trivial self-duality test. It is tempting to ask whether we can classify families of Boolean functions according to whether or not they are amenable to tests independent of n. We have not answered the question in this work. We note that the quasi-monadicity and quasi-symmetry tests both provide some additional information about the function under scrutiny. The quasi- Chapter 4. Conclusions 21 raonadicity test , if it accepts, also tells us which of the' 2n + 2 quasi-monadic functions the candidate is probably close to. The quasi-symmetry test tells us which variables the candidate is certain to depend on (although this set is not guaranteed to be complete). This is in contrast to the results of [5, 11], which are stronger, but do not yield tests which provide this information. Bibliography 22 Bibliography [1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario' Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 1423, Pittsburgh, Pennsylvania, 24-27 October 1992. I E E E . [2] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In Journal of the ACM, volume 45, pages 501-555. A C M , 1998. [3] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; A new characterization of N P . In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. I E E E . [4] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; A new characterization of N P . In Journal of the ACM, volume 45, pages 70-122. A C M , 1998. [5] E . Fischer, G . Kindler, D . Ron, S. Safra, and A . Samorodnitsky. Testing juntas. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, pages 103-112, Vancouver, Canada, 16-19 November 2002. F O C S . [6] 0. Goldreich. CCTR: Combinatorial property testing (a survey). In EC- Electronic Colloquium on Computational Complexity, 1997. ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1997/TR97-056/index.html. Bibliography 23 [7] O. Goldreich, S. Goldwasser, E. Lehman, and D. Ron. Testing monotonicity. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 426-435, Los Alamitos, CA, 8-11 November 1998. IEEE Computer Society. [8] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky. Testing monotonicity. Combinatorics, 20:301-337, 2000. [9] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning arid approximation. Journal of the ACM, 45:653-750, 1998. [10] O. Goldreich and D. Ron. Property testing in bounded degree graphs. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 406-415, E l Paso, Texas, 4-6 May 1997. [11] M . Parnas, D. Ron, and A. Samorodnitsky. Proclaiming dictators and juntas or testing boolean formulae. ECCC, 63, 2001. [12] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, April 1996.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Probabilistic testing of Boolean functions, or, How...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Probabilistic testing of Boolean functions, or, How to test locally for a global property Majewski, Krzysztof Michał 2003
pdf
Page Metadata
Item Metadata
Title | Probabilistic testing of Boolean functions, or, How to test locally for a global property |
Creator |
Majewski, Krzysztof Michał |
Date Issued | 2003 |
Description | Probabilistic testing is a general problem that has fundamental scientific value as well as direct applications to important concepts in theoretical computer science, such as probabilistically checkable proofs (PCP). We consider specifically the testing of Boolean functions, discussing some key existing results and providing new results for several classes of functions. In particular, we give efficient tests for a Boolean function to be symmetric (invariant under permutation of its variables) and quasi-symmetric (a symmetric function of the variables it actually depends on). |
Extent | 929856 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-10-29 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051650 |
URI | http://hdl.handle.net/2429/14328 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2003-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2003-0458.pdf [ 908.06kB ]
- Metadata
- JSON: 831-1.0051650.json
- JSON-LD: 831-1.0051650-ld.json
- RDF/XML (Pretty): 831-1.0051650-rdf.xml
- RDF/JSON: 831-1.0051650-rdf.json
- Turtle: 831-1.0051650-turtle.txt
- N-Triples: 831-1.0051650-rdf-ntriples.txt
- Original Record: 831-1.0051650-source.json
- Full Text
- 831-1.0051650-fulltext.txt
- Citation
- 831-1.0051650.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051650/manifest