scientific article

Publication date: 17 November 2016

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Markov chains martingales Markov processes random graphs hashing continuous random variables discrete probability theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computational methods for problems pertaining to probability theory (60-08) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to probability theory (60-01) Combinatorial probability (60C05) Randomized algorithms (68W20)

Related Items

Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture, Local boxicity, Expected size of random Tukey layers and convex layers, How to meet ternary LWE keys, Unnamed Item, The probabilistic travelling salesman problem with crowdsourcing, Higher criticism to compare two large frequency tables, with sensitivity to possible rare and weak differences, Fast spectral analysis for approximate nearest neighbor search, Fairness in Influence Maximization through Randomization, An FPTAS for the hardcore model on random regular bipartite graphs, Sliding-window probabilistic threshold aggregate queries on uncertain data streams, On binomial and Poisson sums arising from the displacement of randomly placed sensors, Parallel load balancing on constrained client-server topologies, Splits with forbidden subgraphs, Edge-ordered Ramsey numbers, Concentration of maximum degree in random planar graphs, Disjoint isomorphic balanced clique subdivisions, Solving sparse principal component analysis with global support, On the union-closed sets conjecture, Approximating ( k,ℓ )-Median Clustering for Polygonal Curves, Online Predictions for Online TSP on the Line, Shotgun reconstruction in the hypercube, Algebraic and combinatorial expansion in random simplicial complexes, A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs, Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension, Haystack hunting hints and locker room communication, Secure two-party input-size reduction: challenges, solutions and applications, Approximate NFA universality and related problems motivated by information theory, Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations, A new definition of hitting time and an embedded Markov chain in continuous-time quantum walks, Parking on the integers, Efficient computation of tight approximations to Chernoff bounds, Estimating the clustering coefficient using sample complexity analysis, Matching points in compositions and words, Probabilistic Rounding Error Analysis of Householder QR Factorization, 3-party distributed ORAM from oblivious set membership, Emergence of interlacements from the finite volume Bose soup, Brakedown: linear-time and field-agnostic SNARKs for R1CS, Revisiting time-space tradeoffs for function inversion, Packet forwarding with swaps, Some examples of noncentral moderate deviations for sequences of real random variables, Parameterized Counting and Cayley Graph Expanders, Near-linear convergence of the random Osborne algorithm for matrix balancing, Decomposing Random Permutations into Order-Isomorphic Subpermutations, Heavy and light paths and Hamilton cycles, Simplified Chernoff bounds with powers-of-two probabilities, Unnamed Item, Approximating length-restricted means under dynamic time warping, Estimation of misclassification rate in the Asymptotic Rare and Weak model with sub-Gaussian noises, Zip-zip trees: making zip trees more balanced, biased, compact, or persistent, Finding groups with maximum betweenness centrality via integer programming with random path sampling, Core size of a random partition for the Plancherel measure, The Power of Filling in Balanced Allocations, Distributed MIS in O(log log n) Awake Complexity, BKW meets Fourier new algorithms for LPN with sparse parities, Bankrupting Sybil despite churn, A quantified approach of predicting suitability of using the unscented Kalman filter in a non-linear application, A random growth model with any real or theoretical degree distribution, On the number of driver nodes for controlling a Boolean network when the targets are restricted to attractors, Sharper Probabilistic Backward Error Analysis for Basic Linear Algebra Kernels with Random Data, A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs, Using error decay prediction to overcome practical issues of deep active learning for named entity recognition, Descriptive complexity of \#P functions: a new perspective, Stimulated Raman adiabatic passage-like protocols for amplitude transfer generalize to many bipartite graphs, Exceptional graphs for the random walk, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, The complexity of leader election in diameter-two networks, Quantum algorithm for the multicollision problem, Unnamed Item, Unnamed Item, Unnamed Item, Cellular string generators, Estimating multi-index models with response-conditional least squares, Scale-free percolation in continuous space: quenched degree and clustering coefficient, Optimal bounds for single-source Kolmogorov extractors, Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness, Behavioural isomorphism, cognitive economy and recursive thought in non-transitive game strategy, Upper tail analysis of bucket sort and random tries, Upper tail analysis of bucket sort and random tries, The Complexity of Counting Surjective Homomorphisms and Compactions, Approximate minimum selection with unreliable comparisons, Shotgun assembly of Erdős-Rényi random graphs, Range minimum queries in minimal space, Percolation centrality via Rademacher Complexity, Nonparametric intensity estimation from noisy observations of a Poisson process under unknown error distribution, Stochastic Rounding and Its Probabilistic Backward Error Analysis, Connectivity and choosability of graphs with no $K_t$ minor, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, Noisy beeping networks, Efficient and competitive broadcast in multi-channel radio networks, Adaptive Cuckoo Filters, Polymer dynamics via cliques: new conditions for approximations, Approximate NFA universality motivated by information theory