Seminar by Mr. C Sheshadri
Estimating the distance to a monotone function
C Sheshadri
Graduate Student
Department of Computer Science
Princeton University
Princeton, NJ, USA
Date: Tue, Jan 25, 2005
Time: 4:00 PM
Venue: CS-101
Abstract
In standard property testing, we first define a notion of distance of an input from a given property P. The task is to distinguish between inputs that have property P and those that are eps-far (in terms of the defined distance) from P, for some eps > 0, usually in less than linear time. In this setting, we cannot be expected to find any information whatsoever about the actual distance from the input to the property. First, this model will be discussed. Next, we will look at a specific problem, that of monotonicity testing. A function f:{1,...,n} -> R is at distance eps_f from being monotone if it can (and must) be modified at eps_f n places to become monotone. For any fixed delta>0, we compute, with probability at least 2/3, an interval [(1/2 - delta)eps, eps] that encloses eps_f. The running time of our algorithm is O( (1/eps_f)loglog(1/eps_f) log n ). Wireless Local Area Networks (WLANs) are rapidly becoming the medium of choice for network connectivity in enterprises. However, invisibility of wireless transmission and unregulated deployments are created new challenges for security, planning and monitoring of these networks.