scientific article; zbMATH DE number 819814

Publication date: 23 November 1995

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

Markov chains random walks hashing fingerprinting perfect pattern matching

Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10) Discrete geometry (52C99) Probability theory on algebraic and topological structures (60B99)

Related Items

Estimation of singular values of very large matrices using random sampling ⋮ Random walks with ``back buttons ⋮ On the complexity of pattern matching for highly compressed two-dimensional texts. ⋮ Diffusion without false rumors: On propagating updates in a Byzantine environment. ⋮ Towards optimal lower bounds for clique and chromatic number. ⋮ On finding common neighborhoods in massive graphs. ⋮ When can you fold a map? ⋮ Approximate constrained bipartite edge coloring ⋮ The Missing Difference problem, and its applications to counter mode encryption ⋮ Is Shapley cost sharing optimal? ⋮ Localization of VC classes: beyond local Rademacher complexities ⋮ Exact learning of juntas from membership queries ⋮ Randomized nonlinear projections uncover high-dimensional structure ⋮ Multiple (truncated) differential cryptanalysis: explicit upper bounds on data complexity ⋮ Rigorous upper bounds on data complexities of block cipher cryptanalysis ⋮ Some results on the strength of relaxations of multilinear functions ⋮ A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring ⋮ Phylogenetic mixtures: concentration of measure in the large-tree limit ⋮ Strengthening hash families and compressive sensing ⋮ Information gathering in ad-hoc radio networks with tree topology ⋮ Indexing moving points ⋮ When distributed computation is communication expensive ⋮ Analysis of a randomized rendezvous algorithm ⋮ News from the online traveling repairman. ⋮ Distributed broadcast in radio networks of unknown topology. ⋮ Optimal aggregation algorithms for middleware. ⋮ Poly-symmetry in processor-sharing systems ⋮ On stability of fuzzy formal concepts over randomized one-sided formal context ⋮ Triggering cascades on undirected connected graphs ⋮ Black-box search by unbiased variation ⋮ On reversible cascades in scale-free and Erdős-Rényi random graphs ⋮ Comparing the strength of query types in property testing: the case of $k$-colorability ⋮ Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ Game-theoretic discussion of quantum state estimation and cloning ⋮ Uncovering the riffled independence structure of ranked data ⋮ Randomized registers and iterative algorithms ⋮ Efficient adaptive collect using randomization ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Optimal deterministic broadcasting in known topology radio networks ⋮ Summarizing numeric spatial data streams by trend cluster discovery ⋮ On the number of driver nodes for controlling a Boolean network when the targets are restricted to attractors ⋮ Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels. ⋮ Hardness of approximation for non-overlapping local alignments. ⋮ Distinguishing string selection problems. ⋮ Sublinear time motif discovery from multiple sequences ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ Communication and location discovery in geometric ring networks ⋮ Online estimation of discrete, continuous, and conditional joint densities using classifier chains ⋮ On the smoothness of paging algorithms ⋮ Convergence theorems for operators sequences on functionals of discrete-time normal martingales ⋮ The $(1+1)$ elitist black-box complexity of LeadingOnes ⋮ Quantum walks: a comprehensive review ⋮ An approximation algorithm for the traveling tournament problem ⋮ Fun-Sort -- or the chaos of unordered binary search ⋮ Efficiency test of pseudorandom number generators using random walks ⋮ Uncertain convex programs: randomized solutions and confidence levels ⋮ New bounds for randomized busing ⋮ The analysis of evolutionary algorithms on sorting and shortest paths problems ⋮ Computing the optimal partition of variables in multi-homogeneous homotopy methods ⋮ On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions ⋮ Balanced vertex-orderings of graphs ⋮ A probabilistic model of computing with words ⋮ Core instances for testing: a case study ⋮ Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme ⋮ Social integration in two-sided matching markets ⋮ On cutting a few vertices from a graph ⋮ A space lower bound for $st$-connectivity on node-named JAGs ⋮ Random walks on a finite graph with congestion points ⋮ On the complexity of the discrete logarithm and Diffie-Hellman problems ⋮ Popularity based random graph models leading to a scale-free degree sequence ⋮ Quantum analog computing ⋮ A discipline of evolutionary programming ⋮ On the complexity of multi-dimensional interval routing schemes ⋮ Interactive and probabilistic proof-checking ⋮ Randomized algorithms over finite fields for the exact parity base problem. ⋮ Polynomial-time counting and sampling of two-rowed contingency tables ⋮ Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots ⋮ Clique is hard to approximate within $n^{1-\epsilon}$ ⋮ Measure and probability for concurrency theorists ⋮ Efficient searching with linear constraints ⋮ Randomized local elections. ⋮ How to analyse evolutionary algorithms. ⋮ Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions. ⋮ On computing the diameter of a point set in high dimensional Euclidean space. ⋮ On the Hamming distance of constraint satisfaction problems. ⋮ Randomized path coloring on binary trees. ⋮ Probabilistic quorum systems ⋮ Distributed probabilistic polling and applications to proportionate agreement ⋮ The nonapproximability of OBDD minimization ⋮ On asymptotically optimal methods of prediction and adaptive coding for Markov sources ⋮ On approximating planar metrics by tree metrics. ⋮ Small generic hardcore subsets for the discrete logarithm: short secret DL-keys. ⋮ Algorithms, nymphs, and shepherds ⋮ On the analysis of the $(1+1)$ evolutionary algorithm ⋮ A 3-approximation algorithm for the $k$-level uncapacitated facility location problem ⋮ Competitive on-line scheduling of continuous-media streams ⋮ Approximate congruence in nearly linear time ⋮ Finding similar regions in many sequences ⋮ A simple greedy algorithm for finding functional relations: Efficient implementation and average case analysis ⋮ Randomized Group Testing Both Query-Optimal and Minimal Adaptive ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Understanding Probabilistic Programs ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence ⋮ Improved Approximations for the Max k-Colored Clustering Problem ⋮ Asymptotic density, computable traceability, and 1-randomness ⋮ No Free Lunch Theorems: Limitations and Perspectives of Metaheuristics ⋮ Black-Box Complexity for Bounding the Performance of Randomized Search Heuristics ⋮ Quantized consensus ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ On the asymptotic behavior of a sequence of random variables of interest in the classical occupancy problem ⋮ A second look at counting triangles in graph streams (corrected) ⋮ Convex hulls under uncertainty ⋮ Resilient consensus of second-order agent networks: asynchronous update rules with delays ⋮ Robust recoverable and two-stage selection problems ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ Randomized Monte Carlo algorithms for matrix iterations and solving large systems of linear equations ⋮ A sequential Stackelberg game for dynamic inspection problems ⋮ Derandomized Construction of Combinatorial Batch Codes ⋮ A randomized algorithm for a sequence 2-clustering problem ⋮ Topological quantum structures from association schemes ⋮ Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security ⋮ Do additional target points speed up evolutionary algorithms? ⋮ How many needles are in a haystack, or how to solve \#P-complete counting problems fast ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Sublinear-space approximation algorithms for Max $r$-SAT ⋮ Optimal cover time for a graph-based coupon collector process ⋮ Leader election in well-connected graphs ⋮ Nearly exact mining of frequent trees in large networks ⋮ EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ Generic properties of subgroups of free groups and finite presentations ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ Renormalization of the unitary evolution equation for coined quantum walks ⋮ Consensus for Quantum Networks: Symmetry From Gossip Interactions ⋮ Bisimplicial edges in bipartite graphs ⋮ Probabilistic Termination by Monadic Affine Sized Typing ⋮ Exploiting independent subformulas: a faster approximation scheme for $\# k$-SAT ⋮ Decoherence in quantum Markov chains ⋮ Finding large cliques in sparse semi-random graphs by simple randomized search heuristics ⋮ Approximating the fixed linear crossing number ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ Co-evolution of networks and quantum dynamics: a generalization of preferential attachment ⋮ Analysis of randomized protocols for conflict-free distributed access ⋮ Choosing a random peer in Chord ⋮ A general comparison of language learning from examples and from queries ⋮ Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity ⋮ Approximability of Capacitated Network Design ⋮ On the complexity of matrix reduction over finite fields ⋮ Runtime Analysis of Probabilistic Programs with Unbounded Recursion ⋮ A class of algorithms for collision resolution with multiplicity estimation ⋮ Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms ⋮ Approximating the online set multicover problems via randomized winnowing ⋮ Structural filtering: a paradigm for efficient and exact geometric programs ⋮ A randomized satisfiability procedure for arithmetic and uninterpreted function symbols ⋮ Subset-conjunctive rules for breast cancer diagnosis ⋮ On certain connectivity properties of the internet topology ⋮ Uniform generation in spatial constraint databases and applications ⋮ Broadcast in the rendezvous model ⋮ Rare event simulation and splitting for discontinuous random variables ⋮ A class of random number generators based on Weyl sequence ⋮ Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ Tradeoffs in worst-case equilibria ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Competitive auctions ⋮ Negative dependence in the balls and bins experiment with applications to order statistics ⋮ Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms ⋮ Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview ⋮ Construction of sequences of zeros and ones with complex finite sequences ⋮ Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs ⋮ Population size versus runtime of a simple evolutionary algorithm ⋮ The Routing of Complex Contagion in Kleinberg’s Small-World Networks ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Randomness and Computation ⋮ Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs ⋮ Breaking Anonymity by Learning a Unique Minimum Hitting Set ⋮ Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers ⋮ Near-Optimal Dominating Sets via Random Sampling ⋮ Computing the Expected Edit Distance from a String to a PFA ⋮ Topology matters: smoothed competitiveness of metrical task systems ⋮ Covering minimum spanning trees of random subgraphs ⋮ Probabilistic strategies for the partition and plurality problems ⋮ Shortest‐path metric approximation for random subgraphs ⋮ Learning DNF from random walks ⋮ Discrete quantum walks hit exponentially faster ⋮ On Dinur’s proof of the PCP theorem ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ On Floyd and Rivest's SELECT algorithm ⋮ On non-Abelian homomorphic public-key cryptosystems ⋮ Locally consistent constraint satisfaction problems ⋮ Selfish unsplittable flows ⋮ The black-box complexity of nearest-neighbor search ⋮ A Mechanism for Communication-Efficient Broadcast Encryption over Wireless Ad Hoc Networks ⋮ \textsc{OneMax} in black-box models with several restrictions ⋮ Reductions in binary search trees ⋮ Direct routing: Algorithms and complexity ⋮ On the cover time and mixing time of random geometric graphs ⋮ Balanced allocation and dictionaries with tightly packed constant size bins ⋮ Constant time approximation scheme for largest well predicted subset ⋮ A divide-and-conquer approach for reconstruction of $\{C_{ \geq 5}\}$-free graphs via betweenness queries ⋮ Union acceptable profit maximization in social networks ⋮ Simulated annealing versus Metropolis for a TSP instance ⋮ A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs ⋮ Maximize the probability of union-influenced in social networks ⋮ Relaxing the independence assumption in sequential posted pricing, prophet inequality, and random bipartite matching ⋮ Real royal road functions -- where crossover provably is essential ⋮ A lower bound for testing juntas ⋮ Strongly competitive algorithms for caching with pipelined prefetching ⋮ External matrix multiplication and all-pairs shortest path ⋮ Probabilistic sorting and stabilization of switched systems ⋮ Derandomized constructions of $k$-wise (almost) independent permutations ⋮ On random perfect matchings in metric spaces with not-too-large diameters ⋮ The parameterized complexity of unique coverage and its variants ⋮ Stochastic budget optimization in internet advertising ⋮ Fast and simple compact hashing via bucketing ⋮ Randomization and entropy in machine learning and data processing ⋮ SPEck: mining statistically-significant sequential patterns efficiently with exact sampling ⋮ Measurement of the number of molecules of a single mRNA species in a complex mRNA preparation ⋮ Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation ⋮ A cutoff time strategy based on the coupon collector's problem ⋮ Prior-free multi-unit auctions with ordered bidders ⋮ Memetic algorithms outperform evolutionary algorithms in multimodal optimisation ⋮ Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ Precedence constrained scheduling to minimize sum of weighted completion times on a single machine ⋮ Multivariate network traffic analysis using clustered patterns ⋮ Mixing times for uniformly ergodic Markov chains ⋮ Randomized gathering of asynchronous mobile robots ⋮ A spanner for the day after ⋮ Labeled graph sketches: keeping up with real-time graph streams ⋮ Asymptotically optimal erasure-resilient codes for large disk arrays. ⋮ Classical random walk with memory versus quantum walk on a one-dimensional infinite chain ⋮ Probabilistic verification of proofs in calculuses ⋮ Towards efficient universal planning: A randomized approach ⋮ Identification of partial disjunction, parity, and threshold functions ⋮ Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints ⋮ Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes ⋮ On approximating the stationary distribution of time-reversible Markov chains ⋮ On randomised strategies in the $\lambda $-calculus ⋮ Algorithmic probabilistic game semantics. Playing games with automata ⋮ Preemptive and non-preemptive generalized min sum set cover ⋮ Thresholds for extreme orientability ⋮ Better size estimation for sparse matrix products ⋮ The Max problem revisited: the importance of mutation in genetic programming ⋮ Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time ⋮ Playing mastermind with constant-size memory ⋮ Search on a line with faulty robots ⋮ Sigma-local graphs ⋮ Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks ⋮ A randomized algorithm for the min-Max selecting items problem with uncertain weights ⋮ Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work ⋮ On optimal randomized group testing with one defective item and a constrained number of positive responses ⋮ Approximation algorithm for the multicovering problem ⋮ On the performance of learned data structures ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ A random algorithm for profit maximization in online social networks ⋮ Dynamic interpolation search revisited ⋮ Randomized incremental construction of Delaunay triangulations of nice point sets ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Message lower bounds via efficient network synchronization ⋮ Outsourcing computing of large matrix Jordan decomposition ⋮ New bounds for truthful scheduling on two unrelated selfish machines ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Efficient Markov chain Monte Carlo for combined subset simulation and nonlinear finite element analysis ⋮ Fair resource allocation for demands with sharp lower tail inequalities ⋮ The minimum degree group Steiner problem ⋮ Beyond conventional security in sponge-based authenticated encryption modes ⋮ On the welfare effects of affirmative actions in school choice ⋮ Size versus truthfulness in the house allocation problem ⋮ A resource-competitive jamming defense ⋮ A new randomized vector algorithm for iterative solution of large linear systems ⋮ Eigenvector-based identification of bipartite subgraphs ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ Sex: the power of randomization ⋮ Data source selection for approximate query ⋮ New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions ⋮ Non-standard analysis in dynamic geometry ⋮ A binomial sum of harmonic numbers ⋮ The metric distortion of multiwinner voting ⋮ Directed graph encoding in quantum computing supporting edge-failures ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ Global random walk on grid algorithm for solving Navier-Stokes and Burgers equations ⋮ Probabilistic computability and choice ⋮ Revenue maximization with a single sample ⋮ Quantum walks on regular graphs with realizations in a system of anyons ⋮ Sparse learning via Boolean relaxations ⋮ Fitness levels with tail bounds for the analysis of randomized search heuristics ⋮ Data structures on event graphs ⋮ Approximability of capacitated network design ⋮ A randomized algorithm for two-cluster partition of a set of vectors ⋮ On the efficiency of a randomized mirror descent algorithm in online optimization problems ⋮ A probabilistic algorithm for aggregating vastly undersampled large Markov chains ⋮ Collecting coupons is faster with friends ⋮ Graph pricing with limited supply ⋮ Performance analysis of a greedy algorithm for inferring Boolean functions ⋮ A comparative runtime analysis of heuristic algorithms for satisfiability problems ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ Degree-optimal routing for P2P systems ⋮ On the approximation of the minimum disturbance $p$-facility location problem ⋮ Large alphabets and incompressibility ⋮ Efficiently pricing European-Asian options-ultimate implementation and analysis of the AMO algorithm ⋮ A short proof of optimality for the MIN cache replacement algorithm ⋮ A universal online caching algorithm based on pattern matching ⋮ Stability in the self-organized evolution of networks ⋮ Analysis of evolutionary algorithms for the longest common subsequence problem ⋮ On mixing and edge expansion properties in randomized broadcasting ⋮ Approximation algorithms for requirement cut on graphs ⋮ Simple learning algorithms using divide and conquer ⋮ On-board vehicle data stream monitoring using mine-fleet and fast resource constrained monitoring of correlation matrices ⋮ A network flow approach to the minimum common integer partition problem ⋮ A rigorous analysis of the compact genetic algorithm for linear functions ⋮ Random path method with pivoting for computing permanents of matrices ⋮ Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks ⋮ Asymptotic expected number of base pairs in optimal secondary structure for random RNA using the Nussinov--Jacobson energy model ⋮ Investigation of continuous-time quantum walk via spectral distribution associated with adjacency matrix ⋮ The price of validity in dynamic networks ⋮ Analysis of two-dimensional approximate pattern matching algorithms ⋮ On the random generation and counting of matchings in dense graphs ⋮ Randomized local search, evolutionary algorithms, and the minimum spanning tree problem ⋮ Extended results on privacy against coalitions of users in user-private information retrieval protocols ⋮ Another look at XCB ⋮ Runtime analysis of the $(1+1)$ EA on computing unique input output sequences ⋮ Galois geometries and coding theory ⋮ Using the doubling dimension to analyze the generalization of learning algorithms ⋮ Nonstochastic bandits: Countable decision set, unbounded costs and reactive environments ⋮ Sublinear time width-bounded separators and their application to the protein side-chain packing problem ⋮ Sparse geometric graphs with small dilation ⋮ Modelling the dynamics of stochastic local search on $k$-SAT ⋮ How to meet in anonymous network ⋮ Semi-iterative minimum cross-entropy algorithms for rare-events, counting, combinatorial and integer programming ⋮ A randomized competitive algorithm for evaluating priced AND/OR trees ⋮ Scheduling to maximize participation ⋮ Asymmetric information embedding ⋮ The complexity of optimizing over a simplex, hypercube or sphere: a short survey ⋮ Two refinements of the Chernoff bound for the sum of nonidentical Bernoulli random variables ⋮ Performance evaluation of a novel sampling-based texture synthesis technique using different sized patches ⋮ Improved random graph isomorphism ⋮ High-multiplicity cyclic job shop scheduling ⋮ The distant-2 chromatic number of random proximity and random geometric graphs ⋮ Average-case analysis for the MAX-2SAT problem ⋮ Comparing first-fit and next-fit for online edge coloring ⋮ The hitting and cover times of Metropolis walks ⋮ A new approximation algorithm for the multilevel facility location problem ⋮ A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions ⋮ A note on the security of $\text{MST} _{3}$ ⋮ Combinatorial sublinear-time Fourier algorithms ⋮ Ant colony optimization and the minimum spanning tree problem ⋮ Runtime analysis of a binary particle swarm optimizer ⋮ Randomized priority algorithms ⋮ On the false-positive rate of Bloom filters ⋮ Gossiping by processors prone to omission failures ⋮ Finding paths of length $k$ in $O^{*}(2^k)$ time ⋮ Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes ⋮ Atomic congestion games: fast, myopic and concurrent ⋮ TCP is competitive with resource augmentation ⋮ New lower bounds for online $k$-server routing problems ⋮ Communication tree problems ⋮ On a cycle partition problem ⋮ The hitting and cover times of random walks on finite graphs using local degree information ⋮ Randomized strategies for the plurality problem ⋮ Parameterizing above or below guaranteed values ⋮ Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm ⋮ Random walks for selected Boolean implication and equivalence problems ⋮ A practical approximation algorithm for the LMS line estimator ⋮ Expectations for nonreversible Markov chains ⋮ Attribute-efficient learning in query and mistake-bound models ⋮ Near-optimal, distributed edge colouring via the nibble method ⋮ DNA models and algorithms for NP-complete problems ⋮ Smoothed analysis of probabilistic roadmaps ⋮ Estimating network size from local information ⋮ Energy efficient randomised communication in unknown AdHoc networks ⋮ Spreading messages ⋮ Balanced cut approximation in random geometric graphs ⋮ On the $L_2$-discrepancy for anchored boxes ⋮ Navigable small-world networks with few random bits ⋮ Length of prime implicants and number of solutions of random CNF formulae ⋮ Fast RNC and NC algorithms for maximal path sets ⋮ Approximate string matching with address bit errors ⋮ Fault tolerant sorting -- theoretical and empirical analyses of the randomized quickmergesort algorithm ⋮ The Gibbs cloner for combinatorial optimization, counting and sampling ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ A generalization of the 0-1 principle for sorting ⋮ On a simple randomized algorithm for finding a 2-factor in sparse graphs ⋮ Approximating the longest path length of a stochastic DAG by a normal distribution in linear time ⋮ On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering ⋮ $\mathcal{MOQA}$; unlocking the potential of compositional static average-case analysis ⋮ A framework for pursuit evasion games in ⋮ On the hardness of approximating max-satisfy ⋮ A polynomial time approximation scheme for embedding a directed hypergraph on a ring ⋮ On the local distinguishing numbers of cycles ⋮ Mining optimized association rules for numeric attributes ⋮ Extracting randomness: A survey and new constructions ⋮ On-line scheduling to minimize Max flow time: an optimal preemptive algorithm ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Collision resistance of the OAM-based quantum hashing ⋮ Smoothed counting of 0–1 points in polyhedra ⋮ Deterministic Massively Parallel Connectivity ⋮ Sampling from the low temperature Potts model through a Markov chain on flows ⋮ Discrete Morse functions and watersheds ⋮ Compression with wildcards: all exact or all minimal hitting sets ⋮ Online conflict resolution: algorithm design and analysis ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ A new definition of hitting time and an embedded Markov chain in continuous-time quantum walks ⋮ Fairness in temporal slot assignment ⋮ Maximizing the influence with $\kappa$-grouping constraint ⋮ Quantum encoding of dynamic directed graphs ⋮ Some examples of noncentral moderate deviations for sequences of real random variables ⋮ The distribution function for the maximal height of $N$ non-intersecting Bessel paths ⋮ Gradient vector fields of discrete Morse functions and watershed-cuts ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ Simplified Chernoff bounds with powers-of-two probabilities ⋮ Learning Polytopes with Fixed Facet Directions ⋮ Finite-sample complexity of sequential Monte Carlo estimators ⋮ Zip-zip trees: making zip trees more balanced, biased, compact, or persistent ⋮ Fast RNC and NC algorithms for finding a maximal set of paths with an application ⋮ IM2Vec: representation learning-based preference maximization in geo-social networks ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ Unnamed Item ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ The intrinsic dimensionality of graphs ⋮ Repetition-free longest common subsequence ⋮ On approximate range counting and depth ⋮ A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions ⋮ Approaches for scaling DBSCAN algorithm to large spatial databases ⋮ Algorithm portfolios ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Efficient randomized routing algorithms on the two-dimensional mesh of buses ⋮ Counting by quantum eigenvalue estimation ⋮ Transmitting once to elect a leader on wireless networks ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ Opinion dynamics with limited information ⋮ A $\frac 32$-approximation algorithm for parallel machine scheduling with controllable processing times ⋮ Easiness assumptions and hardness tests: Trading time for zero error ⋮ Efficient web searching using temporal factors ⋮ On-line load balancing of temporary tasks revisited ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ Continuous ranking on uncertain streams ⋮ Scalable and dynamic quorum systems ⋮ Approximate set union via approximate randomization ⋮ Maximum box problem on stochastic points ⋮ Distributed MST for constant diameter graphs ⋮ Finding a mediocre player ⋮ Near optimal multiple alignment within a band in polynomial time ⋮ Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs ⋮ On the mixing time of coordinate Hit-and-Run ⋮ Bounded Degree Group Steiner Tree Problems ⋮ Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations ⋮ Construction of one special minimum storage regenerating code when α=2 ⋮ Lower bounds for dynamic transitive closure, planar point location, and parentheses matching ⋮ Extractors for weak random sources and their applications ⋮ Fast Distributed Approximation for Max-Cut ⋮ On dependent randomized rounding algorithms ⋮ The VCG Mechanism for Bayesian Scheduling ⋮ Higher-dimensional open quantum walk in environment of quantum Bernoulli noises ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ An ergodic theorem for the weighted ensemble method ⋮ I/O-Efficient Generation of Massive Graphs Following the LFR Benchmark ⋮ Multiple Round Random Ball Placement: Power of Second Chance ⋮ Summary Data Structures for Massive Data ⋮ Modeling the effects of multiple exposures with unknown group memberships: a Bayesian latent variable approach ⋮ Online Buy-at-Bulk Network Design ⋮ Tail bounds for occupancy and the satisfiability threshold conjecture ⋮ Parallel Weighted Random Sampling ⋮ How to deal with malicious users in privacy‐preserving distributed data mining ⋮ A communication efficient probabilistic algorithm for mining frequent itemsets from a peer‐to‐peer network ⋮ Geometric Packing under Nonuniform Constraints ⋮ Randomness – A Computational Complexity Perspective ⋮ Approximate String Matching with Address Bit Errors ⋮ The fractional congestion bound for efficient edge disjoint routing ⋮ Spreading Messages ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ Unnamed Item ⋮ Expander graphs and their applications ⋮ Computing thejth solution of a first-order query ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Probability distributions for Markov chain based quantum walks ⋮ Query Complexity of Sampling and Small Geometric Partitions ⋮ Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton ⋮ Randomized Algorithms for Lexicographic Inference ⋮ Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality ⋮ Tight Bounds for Online Vector Scheduling ⋮ Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems ⋮ Unnamed Item ⋮ Range Medians ⋮ On Mixing and Edge Expansion Properties in Randomized Broadcasting ⋮ Depth of Field and Cautious-Greedy Routing in Social Networks ⋮ The Monomial Ideal Membership Problem and Polynomial Identity Testing ⋮ One-dimensional quantum walks with a position-dependent coin ⋮ Markov incremental constructions ⋮ On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes ⋮ A Practical Randomized CP Tensor Decomposition ⋮ The Splitting Method for Decision Making ⋮ Unnamed Item ⋮ A model of self‐avoiding random walks for searching complex networks ⋮ Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions ⋮ Random Construction of Interpolating Sets for High-Dimensional Integration ⋮ Visualization of Distributed Algorithms Based on Graph Relabelling Systems1 1This work has been supported by the European TMR research network GETGRATS, and by the “Conseil Régional d' Aquitane”. ⋮ Near-Optimal Algorithms for Online Matrix Prediction ⋮ Quick Detection of Nodes with Large Degrees ⋮ Hypergraph Coloring Games and Voter Models ⋮ Unnamed Item ⋮ Parameterized Traveling Salesman Problem: Beating the Average ⋮ Unnamed Item ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ An Algorithmic Theory of Mobile Agents ⋮ Scheduling to Maximize Participation ⋮ Simple and efficient local codes for distributed stable network construction ⋮ Weak communication in single‐hop radio networks: adjusting algorithms to industrial standards ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ Atomic Congestion Games: Fast, Myopic and Concurrent ⋮ Frugal Routing on Wireless Ad-Hoc Networks ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ ORIGAMI: A Novel and Effective Approach for Mining Representative Orthogonal Graph Patterns ⋮ Interactive knowledge discovery from hidden data through sampling of frequent patterns ⋮ Cryptanalysis of Vortex ⋮ A probabilistic model for the survivability of cells ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ A unified approach to tail estimates for randomized incremental construction ⋮ Unnamed Item ⋮ Quantum integral equations of Volterra type in terms of discrete-time normal martingale ⋮ Sorting Algorithms in MOQA ⋮ Why Do Simple Algorithms for Triangle Enumeration Work in the Real World? ⋮ Probabilistic analysis of shelf algorithms for strip packing ⋮ Unnamed Item ⋮ Combinatorial Problems for Horn Clauses ⋮ Approximately counting bases of bicircular matroids ⋮ Reconstructing Algebraic Functions from Mixed Data ⋮ Stochastic Contention Resolution With Short Delays ⋮ On the Complexity of Universal Leader Election ⋮ Improved Constructions of Quantum Automata ⋮ Bin Packing with Queues ⋮ On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$ ⋮ Randomness in post-selected events ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Testing Probability Distributions using Conditional Samples ⋮ Synchronizing Almost-Group Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem ⋮ Toward Fine-Grained Blackbox Separations Between Semantic and Circular-Security Notions ⋮ Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals ⋮ On incremental approximate saddle-point computation in zero-sum matrix games ⋮ Bounding duality gap for separable problems with linear constraints ⋮ Approximate Max $k$-Cut with subgraph guarantee ⋮ Randomized group testing for mutually obscuring defectives ⋮ Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees ⋮ Estimating the range of a function in an online setting ⋮ Worst case examples for operations on OBDDs ⋮ The impact of random initialization on the runtime of randomized search heuristics ⋮ Vector Monte Carlo stochastic matrix-based algorithms for large linear systems ⋮ Grover walks on a line with absorbing boundaries ⋮ Laplacian versus adjacency matrix in quantum walk search ⋮ One-dimensional three-state quantum walk with single-point phase defects ⋮ Computing rarity on uncertain data ⋮ Stochastic enumeration method for counting NP-hard problems ⋮ (Approximate) uncertain skylines ⋮ Real royal road functions for constant population size ⋮ Proximate point searching ⋮ Identifiability and inference of non-parametric rates-across-sites models on large-scale phylo\-genies ⋮ Optimal scaling of average queue sizes in an input-queued switch: an open problem ⋮ Signal-flow-based analysis of wireless security protocols ⋮ Relativization makes contradictions harder for resolution ⋮ Fast error-tolerant quartet phylogeny algorithms ⋮ Streaming algorithms for language recognition problems ⋮ On testing monomials in multivariate polynomials ⋮ Algorithmic theory of free solvable groups: randomized computations. ⋮ New approaches to multi-objective optimization ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ On the approximability of robust spanning tree problems ⋮ An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs ⋮ A note on the generalized min-sum set cover problem ⋮ Faster least squares approximation ⋮ Average-case competitive analyses for one-way trading ⋮ Crossover can be constructive when computing unique input-output sequences ⋮ Sparse reliable graph backbones ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Memoryless routing in convex subdivisions: random walks are optimal ⋮ New constructions of SSPDs and their applications ⋮ Learning random monotone DNF ⋮ Optimal partition trees ⋮ A large population size can be unhelpful in evolutionary algorithms ⋮ Free lunches on the discrete Lipschitz class ⋮ Runtime analysis of the 1-ANT ant colony optimizer ⋮ Spreading of messages in random graphs ⋮ Toward a model for backtracking and dynamic programming ⋮ Conditional e-payments with transferability ⋮ On rainbow-$k$-connectivity of random graphs ⋮ List update with probabilistic locality of reference ⋮ Distributed probabilistic inferencing in sensor networks using variational approximation ⋮ Open quantum random walks ⋮ The $K$-armed dueling bandits problem ⋮ Efficiently testing sparse $\text{GF}(2)$ polynomials ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Voting almost maximizes social welfare despite limited communication ⋮ The saga of minimum spanning trees ⋮ Worst-case equilibria ⋮ Linking operational semantics and algebraic semantics for a probabilistic timed shared-variable language ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ Book review of: D. P. Dubhashi and A. Panconesi, Concentration of measure for the analysis of randomized algorithms. ⋮ The cook-book approach to the differential equation method ⋮ Binary subtrees with few labeled paths ⋮ Derandomization in game-theoretic probability ⋮ Cache-oblivious hashing ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Rigorous error control methods for estimating means of bounded random variables ⋮ Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons ⋮ Dealing with undependable workers in decentralized network supercomputing ⋮ Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks ⋮ Randomized sampling for large zero-sum games ⋮ Controllability of system dynamics on networks, quantum walks and random walks ⋮ Characterization theorems for generalized functionals of discrete-time normal martingale ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Initializing sensor networks of non-uniform density in the weak sensor model ⋮ Sparse covers for sums of indicators ⋮ Weighted sampling without replacement from data streams ⋮ Triggering cascades on strongly connected directed graphs ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Approximating Max NAE-$k$-SAT by anonymous local search ⋮ Scalable learning and inference in Markov logic networks ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ A polynomial time approximation scheme for the closest shared center problem ⋮ Phase transition in the sample complexity of likelihood-based phylogeny inference ⋮ Finding a low-rank basis in a matrix subspace ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ Stochastic enumeration method for counting trees ⋮ Ranking-based black-box complexity ⋮ In-network estimation of frequency moments ⋮ Efficient decentralized algorithms for the distributed trigger counting problem ⋮ User-friendly tail bounds for sums of random matrices ⋮ Query strategies for priced information ⋮ On multivariate quantiles under partial orders ⋮ A simple and deterministic competitive algorithm for online facility location ⋮ The QWalk simulator of quantum walks ⋮ Near-optimal radio use for wireless network synchronization ⋮ Convergence of set-based multi-objective optimization, indicators and deteriorative cycles ⋮ A short implicant of a CNF formula with many satisfying assignments ⋮ A second look at counting triangles in graph streams ⋮ Hardness of learning loops, monoids, and semirings ⋮ Sequential importance sampling of binary sequences ⋮ Efficient distributed computation of distance sketches in networks ⋮ A note on labeling schemes for graph connectivity