1,355,494 research outputs found
Statistics in the Courtroom: Building on Rubinfeld
No full textAs the use of statistics in litigation has burgeoned and as more complicated statistical techniques have entered the courtroom, concern for the way courts use statistics has mounted and efforts to instruct lawyers and judges on the wise use of statistics have begun. Professor Rubinfeld\u27s paper is a contribution toward this end. Two ideas at the core of this paper are particularly important if we are to develop a more satisfactory approach to the use of statistics in the courtroom. The first is Professor Rubinfeld\u27s caution against the talismanic use of the .05 level of significances as a test of what aspects of a statistical study are important to a legal factfinder. The second is his call for more attention to sensitivity testing than is customary in litigation research
Local Computation Algorithms (Invited Talk)
No full textConsider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of local computation algorithms which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed - we will give special focus to finding maximal independent sets and sparse spanning graphs
Approximating the Noise Sensitivity of a Monotone Boolean Function
No full textThe noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure.
The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]).
Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n.
We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias
Statistics in the Courtroom: Building on Rubinfeld
No full textAs the use of statistics in litigation has burgeoned and as more complicated statistical techniques have entered the courtroom, concern for the way courts use statistics has mounted and efforts to instruct lawyers and judges on the wise use of statistics have begun. Professor Rubinfeld\u27s paper is a contribution toward this end. Two ideas at the core of this paper are particularly important if we are to develop a more satisfactory approach to the use of statistics in the courtroom. The first is Professor Rubinfeld\u27s caution against the talismanic use of the .05 level of significances as a test of what aspects of a statistical study are important to a legal factfinder. The second is his call for more attention to sensitivity testing than is customary in litigation research
A local decision test for sparse polynomials
No full textAn ℓ-sparse (multivariate) polynomial is a polynomial containing at most ℓ-monomials in its explicit description. We assume that a polynomial is implicitly represented as a black-box: on an input query from the domain, the black-box replies with the evaluation of the polynomial at that input. We provide an efficient, randomized algorithm, that can decide whether a polynomial [MathML] given as a black-box is ℓ-sparse or not, provided that q is large compared to the polynomial's total degree. The algorithm makes only queries, which is independent of the domain size. The running time of our algorithm (in the bit-complexity model) is , where d is an upper bound on the degree of each variable. Existing interpolation algorithms for polynomials in the same model run in time . We provide a similar test for polynomials with integer coefficients
Upward Pricing Pressure in Horizontal Merger Analysis: Reply to Epstein and Rubinfeld
No full textWe reply here to a comment by Epstein and Rubinfeld to our paper on the antitrust evaluation of horizontal mergers.</jats:p
Space-Efficient Local Computation Algorithms
No full textRecently Rubinfeld et al. (ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called local computation algorithms. In this model, a computation problem F may have more than one legal solution and each of them consists of many bits. The local computation algorithm for F should answer in an online fashion, for any index i, the i[superscript th] bit of some legal solution of F. Further, all the answers given by the algorithm should be consistent with at least one solution of F. In this work, we continue the study of local computation algorithms. In particular, we develop a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time but also in polylogarithmic space. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. Our main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.Marie Curie International Reintegration Grants (Grant number PIRG03-GA-2008-231077)Israel Science Foundation (Grant number 1147/09)Israel Science Foundation (Grant number 1675/09)National Science Foundation (U.S.). (Grant number CCF-0728645)National Science Foundation (U.S.). (Grant number CCF-1065125)National Science Foundation (U.S.). (Grant number CCF-0729011
Upward Pricing Pressure in Horizontal Merger Analysis: Reply to Epstein and Rubinfeld
No full textWe reply here to a comment by Epstein and Rubinfeld to our paper on the antitrust evaluation of horizontal mergers.
Maintaining a large matching and a small vertex cover
No full textWe consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. Each update to the graph is either an edge deletion or an edge insertion. We give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of K updates in K*polylog(n) time, where n is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.National Science Foundation (U.S.). (Grant number 0732334)National Science Foundation (U.S.). (Grant number 0728645)Marie Curie International Reintegration Grants (Grant number PIRG03-GA-2008-231077)Israel Science Foundation (Grant number 1147/09)Israel Science Foundation (Grant number 1675/09
- …
