Randomized adaptive sorting

Our goal is to design practical sorting algorithms that require time proportional not only to the size of the input but also to the disorder in the input. Such sorting algorithms are said to be adaptive. We introduce randomization to achieve this goal; the first time randomization has used to obtain adaptive sorting algorithms. We investigate three randomized algorithms.

• 1 Randomized Merge Sort, which is expected Runs-optimal;
• 2 Randomized Quicksort, which is Exchange-sensitive, that is, it takes Θ(|X|[1+log(Exc(X)+1)]) time in the expected case; and
• 3 Skip Sort, whichh is Inversions-, Runs-, and Exchhange-optimal.

The three sorting algorithms are simple and practical, in contrast to previous adaptive sorting algorithms that used complex data structures. Moreover, previous claims about the performance of adaptive variants of Quicksort were baed only on simulation results,; our claims are based on a formal analysis. © 1993 John Wiley & Sons. Inc.     

Dynamic point location in arrangements of hyperplanes

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure isÕ(polylog(n)), wheren is the number of hyperplanes at any given time, and theÕ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial inn. The space requirement isÕ(n ^d). The cost of update isÕ(n ^d?1 logn. The expected cost of update isO(n ^d?1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimalÕ(logn) query time, expectedO(n ^d) space requirement, and amortizedO(n ^d?1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. Ford=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time.     

On extractors and exposure‐resilient functions for sublogarithmic entropy

We study resilient functions and exposure‐resilient functions in the low‐entropy regime. A resilient function (a.k.a. deterministic extractor for oblivious bit‐fixing sources) maps any distribution on n ‐bit strings in which k bits are uniformly random and the rest are fixed into an output distribution that is close to uniform. With exposure‐resilient functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n ‐ k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of resilient functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(log k) output bits) is optimal for extractors computable by a large class of space‐bounded streaming algorithms. Next, we show that a random function is a resilient function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random function is a static (resp. adaptive) exposure‐resilient function with high probability even if k is as small as a constant (resp. loglog n). No explicit exposure‐resilient functions achieving these parameters are known. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

A Probabilistic Analysis of the Power of Arithmetic Filters

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such capability. A geometric predicate usually consists of evaluating the sign of some algebraic expression. In most cases, rounded computations yield a reliable result, but sometimes rounded arithmetic introduces errors which may invalidate the algorithms. The rounded arithmetic may produce an incorrect result only if the exact absolute value of the algebraic expression is smaller than some (small) ε , which represents the largest error that may arise in the evaluation of the expression. The threshold ε depends on the structure of the expression and on the adopted computer arithmetic, assuming that the input operands are error-free. A pair (arithmetic engine, threshold) is an arithmetic filter. In this paper we develop a general technique for assessing the efficacy of an arithmetic filter. The analysis consists of evaluating both the threshold and the probability of failure of the filter. To exemplify the approach, under the assumption that the input points be chosen randomly in a unit ball or unit cube with uniform density, we analyze the two important predicates ``which-side' and ``insphere.' We show that the probability that the absolute values of the corresponding determinants be no larger than some positive value V , with emphasis on small V , is Θ(V) for the which-side predicate, while for the insphere predicate it is Θ(V ^2/3 ) in dimension 1, O(V ^1/2 ) in dimension 2, and O(V ^1/2 ln (1/V)) in higher dimensions. Constants are small, and are given in the paper. Received September 15, 1996, and in revised form September 9, 1997.     

On boolean decision trees with faulty nodes

We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that if f can be represented in k-DNF form and in j-CNF form, then O(n log(min(k, j)/q)) queries suffice to compute f with error probability less than q, where n is the number of input bits. © 1994 John Wiley & Sons, Inc.     

Shift error detection in standardized exams

Hundreds of millions of multiple choice exams are given every year in the United States. These exams permit form-filling shift errors, where an absent-minded mismarking displaces a long run of correct answers. A shift error can substantially alter the exam's score, and thus invalidate it.In this paper, we develop algorithms to accurately detect and correct shift errors, while guaranteeing few false detections. We propose a shift error model, and probabilistic methods to identify shifted exam regions.We describe the results of our search for shift errors in undergraduate Stony Brook exam sets, and in over 100,000 Scholastic Amplitude Tests. These results suggest that approximately 2% of all tests contain shift errors. Extrapolating these results over all multiple choice exams and forms leads us to conclude that exam takers make millions of undetected shift errors each year.Employing probabilistic shift correcting systems is inherently dangerous. Such systems may be taken advantage of by clever examinees, who seek to increase the probability of correct guessing. We conclude our paper with a short study of optimal guessing strategies when faced with a generous shift error correcting system.     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges

Phylogenetic reconstruction methods attempt to reconstruct a tree describing the evolution of a given set of species using sequences of characters (e.g. DNA) extracted from these species as input. A central goal in this area is to design algorithms which guarantee reliable reconstruction of the tree from short input sequences, assuming common stochastic models of evolution. The fast converging reconstruction algorithms introduced in the last decade dramatically reduced the sequence length required to guarantee accurate reconstruction of the entire tree. However, if the tree in question contains even few edges which cannot be reliably reconstructed from the input sequences, then known fast converging algorithms may fail to reliably reconstruct all or most of the other edges. This calls for an adaptive approach suggested in this paper, called adaptive fast convergence, in which the set of edges which can be reliably reconstructed gradually increases with the amount of information (length of input sequences) available to the algorithm. This paper presents an adaptive fast converging algorithm which returns a partially resolved topology containing no false edges: edges that cannot be reliably reconstructed are contracted into high degree vertices. We also present an upper bound on the weights of those contracted edges, which is determined by the length of input sequences and the depth of the tree. As such, the reconstruction guarantee provided by our algorithm for individual edges is significantly stronger than any previously published edge reconstruction guarantee. This fact, together with the optimal complexity of our algorithm (linear space and quadratic‐time), makes it appealing for practical use. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 350–384, 2011     

Algorithms for coloring semi-random graphs

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require n^δ (δ>0) colors even for bounded chromatic (k-colorable for fixed k) n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model, the graph is supplied by an adversary each of whose decisions regarding inclusion of edges is reversed with some probability p. In terms of randomness, this model lies between the worst case model and the usual random model where each edge is chosen with equal probability. We present polynomial time algorithms of two different types. The first type of algorithms always run in polynomial time and succeed almost surely. Blum and Spencer [J. Algorithms, 19 , 204–234 (1995)] have also obtained independently such algorithms, but our results are based on different proof techniques which are interesting in their own right. The second type of algorithms always succeed and have polynomial running time on the average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work for semirandom graphs drawn from a wide range of distributions and work as long as p≥n^−α(k)+ϵ where α(k)=(2k)/((k−1)(k+2)) and ϵ is a positive constant. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 125–158 (1998)     

Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error

In many problems involving generalized linear models, the covariates are subject to measurement error. When the number of covariates p exceeds the sample size n, regularized methods like the lasso or Dantzig selector are required. Several recent papers have studied methods which correct for measurement error in the lasso or Dantzig selector for linear models in the p > n setting. We study a correction for generalized linear models, based on Rosenbaum and Tsybakov’s matrix uncertainty selector. By not requiring an estimate of the measurement error covariance matrix, this generalized matrix uncertainty selector has a great practical advantage in problems involving high-dimensional data. We further derive an alternative method based on the lasso, and develop efficient algorithms for both methods. In our simulation studies of logistic and Poisson regression with measurement error, the proposed methods outperform the standard lasso and Dantzig selector with respect to covariate selection, by reducing the number of false positives considerably. We also consider classification of patients on the basis of gene expression data with noisy measurements. Supplementary materials for this article are available online.     

Universal Algorithms for Learning Theory. Part II: Piecewise Polynomial Functions

This paper is concerned with estimating the regression function f_ρ in supervised learning by utilizing piecewise polynomial approximations on adaptively generated partitions. The main point of interest is algorithms that with high probability are optimal in terms of the least square error achieved for a given number m of observed data. In a previous paper [1], we have developed for each β > 0 an algorithm for piecewise constant approximation which is proven to provide such optimal order estimates with probability larger than 1- m^-β. In this paper we consider the case of higher-degree polynomials. We show that for general probability measures ρ empirical least squares minimization will not provide optimal error estimates with high probability. We go further in identifying certain conditions on the probability measure ρ which will allow optimal estimates with high probability.     

Balanced allocation on graphs: A random walk approach

We propose algorithms for allocating n sequential balls into n bins that are interconnected as a d‐regular n‐vertex graph G, where d ≥ 3 can be any integer. In general, the algorithms proceeds in n succeeding rounds. Let ? > 0 be an integer, which is given as an input to the algorithms. In each round, ball 1 ≤ t ≤ n picks a node of G uniformly at random and performs a nonbacktracking random walk of length ? from the chosen node and simultaneously collects the load information of a subset of the visited nodes. It then allocates itself to one of them with the minimum load (ties are broken uniformly at random). For graphs with sufficiently large girths, we obtain upper and lower bounds for the maximum number of balls at any bin after allocating all n balls in terms of ?, with high probability.     

Accurate solution of polynomial equations using Macaulay resultant matrices

We propose an algorithm for solving two polynomial equations in two variables. Our algorithm is based on the Macaulay resultant approach combined with new techniques, including randomization, to make the algorithm accurate in the presence of roundoff error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundoff of the method, showing that with high probability the roots are computed accurately, assuming that the input data (that is, the two polynomials) are well conditioned. Our analysis requires a novel combination of algebraic and numerical techniques.

     

Conditioning of Random Conic Systems Under a General Family of Input Distributions

We consider the conic feasibility problem associated with the linear homogeneous system Ax≤0, x≠0. The complexity of iterative algorithms for solving this problem depends on a condition number C(A). When studying the typical behavior of algorithms under stochastic input, one is therefore naturally led to investigate the fatness of the tails of the distribution of C(A). Introducing the very general class of uniformly absolutely continuous probability models for the random matrix A, we show that the distribution tails of C(A) decrease at algebraic rates, both for the Goffin–Cheung–Cucker number C _G and the Renegar number C _R . The exponent that drives the decay arises naturally in the theory of uniform absolute continuity, which we also develop in this paper. In the case of C _G , we also discuss lower bounds on the tail probabilities and show that there exist absolutely continuous input models for which the tail decay is subalgebraic. R. Hauser was supported by a grant of the Nuffield Foundation under the “Newly Appointed Lecturers” grant scheme (project number NAL/00720/G) and through grant GR/S34472 from the Engineering and Physical Sciences Research Council of the UK. The research in this paper was conducted while T. Müller was a research student at the University of Oxford. He was partially supported by EPSRC, the Oxford University Department of Statistics, Bekker-la-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Queue length distributions in a markov model of a multistage clocked queueing network

In [4], we treated the problem of passage through a discrete-time clock-regulated multistage queueing network by modeling the input time series {a_n} to each queue as a Markov chain. We showed how to transform probability transition information from the input of one queue to the input of the next in order to predict mean queue length at each stage. The Markov approximation is very good for p = E(a_n) ≦ ½, which is in fact the range of practical utility. Here we carry out a Markov time series input analysis to predict the stage to stage change in the probability distribution of queue length. The main reason for estimating the queue length distribution at each stage is to locate “hot spots”, loci where unrestricted queue length would exceed queue capacity, and a quite simple expression is obtained for this purpose.     

Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error

Efficient estimation of tail probabilities involving heavy tailed random variables is amongst the most challenging problems in Monte-Carlo simulation. In the last few years, applied probabilists have achieved considerable success in developing efficient algorithms for some such simple but fundamental tail probabilities. Usually, unbiased importance sampling estimators of such tail probabilities are developed and it is proved that these estimators are asymptotically efficient or even possess the desirable bounded relative error property. In this paper, as an illustration, we consider a simple tail probability involving geometric sums of heavy tailed random variables. This is useful in estimating the probability of large delays in M/G/1 queues. In this setting we develop an unbiased estimator whose relative error decreases to zero asymptotically. The key idea is to decompose the probability of interest into a known dominant component and an unknown small component. Simulation then focuses on estimating the latter ‘residual’ probability. Here we show that the existing conditioning methods or importance sampling methods are not effective in estimating the residual probability while an appropriate combination of the two estimates it with bounded relative error. As a further illustration of the proposed ideas, we apply them to develop an estimator for the probability of large delays in stochastic activity networks that has an asymptotically zero relative error.      

On security properties of all-or-nothing transforms

All-or-nothing transforms have been defined as bijective mappings on all s-tuples over a specified finite alphabet. These mappings are required to satisfy certain “perfect security” conditions specified using entropies of the probability distribution defined on the input s-tuples. Alternatively, purely combinatorial definitions of AONTs have been given, which involve certain kinds of “unbiased arrays”. However, the combinatorial definition makes no reference to probability definitions. In this paper, we examine the security provided by AONTs that satisfy the combinatorial definition. The security of the AONT can depend on the underlying probability distribution of the s-tuples. We show that perfect security is obtained from an AONT if and only if the input s-tuples are equiprobable. However, in the case where the input s-tuples are not equiprobable, we still achieve a weaker security guarantee. We also consider the use of randomized AONTs to provide perfect security for a smaller number of inputs, even when those inputs are not equiprobable.

     

Approximation with polynomial kernels and SVM classifiers

This paper presents an error analysis for classification algorithms generated by regularization schemes with polynomial kernels. Explicit convergence rates are provided for support vector machine (SVM) soft margin classifiers. The misclassification error can be estimated by the sum of sample error and regularization error. The main difficulty for studying algorithms with polynomial kernels is the regularization error which involves deeply the degrees of the kernel polynomials. Here we overcome this difficulty by bounding the reproducing kernel Hilbert space norm of Durrmeyer operators, and estimating the rate of approximation by Durrmeyer operators in a weighted L¹ space (the weight is a probability distribution). Our study shows that the regularization parameter should decrease exponentially fast with the sample size, which is a special feature of polynomial kernels. Dedicated to Charlie Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 68T05, 62J02. Ding-Xuan Zhou: The first author is supported partially by the Research Grants Council of Hong Kong (Project No. CityU 103704).     

Efficient parallel recognition of cographs

In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P₄. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in time and require O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P₄) whenever our algorithms decide that the input graphs are not cographs.     

Optimal algorithms for global optimization in case of unknown Lipschitz constant

We consider the global optimization problem for d-variate Lipschitz functions which, in a certain sense, do not increase too slowly in a neighborhood of the global minimizer(s). On these functions, we apply optimization algorithms which use only function values. We propose two adaptive deterministic methods. The first one applies in a situation when the Lipschitz constant L is known. The second one applies if L is unknown. We show that for an optimal method, adaptiveness is necessary and that randomization (Monte Carlo) yields no further advantage. Both algorithms presented have the optimal rate of convergence.