On randomization in sequential and distributed algorithms

No abstract is available for this paper.

• Publication year

  1994

• Venue

  CSUR

• Publication date

  1994-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/174666.174667
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multi-prover interactive proofs: how to remove intractability assumptions

  2019cited by this paper
• The Spatial Complexity of Oblivious k-Probe Hash Functions

  2018cited by this paper
• Randomized speed-ups in parallel computation

  2015cited by this paper
• Data Structures and Algorithms 3

  2012cited by this paper
• Partitioning arrangements of lines II: Applications

  2011cited by this paper
• Simulating physics with computers

  1999cited by this paper
• Randomized data structures for the dynamic closest-pair problem

  1998cited by this paper
• Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem

  1996cited by this paper
• Introduction to algorithms

  1996cited by this paper
• k-k Routing, k-k Sorting, and Cut-Through Routing on the Mesh

  1995cited by this paper
• Randomized Algorithms: Tail Inequalities

  1995cited by this paper
• Chernoff-Hoeffding bounds for applications with limited independence

  1995cited by this paper
• Dynamic Perfect Hashing: Upper and Lower Bounds

  1994cited by this paper
• Fast construction of irreducible polynomials over finite fields

  1994cited by this paper
• Probabilistic recurrence relations

  1994cited by this paper
• What can be computed locally?

  1993cited by this paper
• A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon

  1993cited by this paper
• Graphs, Hypergraphs and Hashing

  1993cited by this paper
• Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions

  1993cited by this paper
• Randomness-optimal unique element isolation, with applications to perfect matching and related problems

  1993cited by this paper
• The biased coin problem

  1993cited by this paper
• Constructing small sample spaces satisfying given constraints

  1993cited by this paper
• On lines missing polyhedral sets in 3-space

  1993cited by this paper
• Fast asynchronous Byzantine agreement with optimal resilience

  1993cited by this paper
• Quantum complexity theory

  1993cited by this paper
• Efficient randomized algorithms for the repeated median line estimator

  1993cited by this paper
• /spl Phi/-test: Perfect hashed index test for test response validation

  1993cited by this paper
• Approximate nearest neighbor queries in fixed dimensions

  1993cited by this paper
• Dynamic Generation of Discrete Random Variates

  1993cited by this paper
• Efficient probabilistically checkable proofs and applications to approximations

  1993cited by this paper
• An Õ(n2) algorithm for minimum cuts

  1993cited by this paper
• Random Weighted Laplacians, Lovász minimum digraphs and finding minimum separators

  1993cited by this paper
• Global min-cuts in RNC, and other ramifications of a simple min-out algorithm

  1993cited by this paper
• On the Randomized Construction of the Delaunay Tree

  1993cited by this paper
• Detecting False Matches in String Matching Algorithms

  1993cited by this paper
• On traversing layered graphs on-line

  1993cited by this paper
• More deterministic simulation in logspace

  1993cited by this paper
• Efficient program transformations for resilient parallel computation via randomization (preliminary version)

  1992cited by this paper
• On the all-pairs-shortest-path problem

  1992cited by this paper
• Computing Frobenius maps and factoring polynomials

  1992cited by this paper
• Randomization yields simple O(n log* n) algorithms for difficult Omega(n) problems

  1992cited by this paper
• Efficient PRAM simulation on a distributed memory machine

  1992cited by this paper
• An Optimal Algorithm for Generating Minimal Perfect Hash Functions

  1992cited by this paper
• The Average Complexity of Parallel Comparison Merging

  1992cited by this paper
• An O(log N) deterministic packet-routing scheme

  1992influential reference
• Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks

  1992cited by this paper
• Probabilistic Estimation of the Number of Prefixes of a Trace

  1992cited by this paper
• A subexponential randomized simplex algorithm (extended abstract)

  1992cited by this paper
• Simple Construction of Almost k-wise Independent Random Variables

  1992cited by this paper
• Randomized versus nondeterministic communication complexity

  1992cited by this paper
• On the parallel complexity of computing a maximal independent set in a hypergraph

  1992cited by this paper
• IP = PSPACE

  1992influential reference
• Making zero-knowledge provers efficient

  1992cited by this paper
• Randomized consensus in expected O(n log/sup 2/ n) operations per processor

  1992cited by this paper
• e-approximations with minimum packing constraint violation (extended abstract)

  1992cited by this paper
• A subexponential bound for linear programming

  1992cited by this paper
• Randomized geometric algorithms and pseudorandom generators

  1992cited by this paper
• Randomized algorithms in “primitive” cultures or what is the oracle complexity of a dead chicken?

  1992cited by this paper
• A decomposition theorem and bounds for randomized server problems

  1992cited by this paper
• New algorithms for an ancient scheduling problem

  1992cited by this paper
• A parallel randomized approximation scheme for shortest paths

  1992cited by this paper
• Polynomial Hash Functions Are Reliable (Extended Abstract)

  1992cited by this paper
• Simple algorithms for routing on butterfly networks with bounded queues

  1992cited by this paper
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems

  1992cited by this paper
• Applications of random sampling to on-line algorithms in computational geometry

  1992cited by this paper
• Probably Approximate Learning Over Classes of Distributions

  1992cited by this paper
• Multi-Oracle Interactive Protocols with Constant Space Verifiers

  1992cited by this paper
• A note on efficient zero-knowledge proofs and arguments (extended abstract)

  1992cited by this paper
• Randomised algorithms for packet routing on the mesh

  1992cited by this paper
• Methods for message routing in parallel machines

  1992cited by this paper
• Practical minimal perfect hash functions for large databases

  1992cited by this paper
• Monte Carlo simulations: Hidden errors from "good" random number generators.

  1992cited by this paper
• On Independent Random Oracles

  1992cited by this paper
• Simulating BPP using a general weak random source

  1991cited by this paper
• Perfect hashing functions for hardware applications

  1991cited by this paper
• Dynamic Maintenance of Geometric Structures Made Easy

  1991cited by this paper
• Fast approximation algorithms for multicommodity flow problems

  1991cited by this paper
• Converting high probability into nearly-constant time—with applications to parallel hashing

  1991cited by this paper
• Non-interactive zero-knowledge proof systems

  1991cited by this paper
• Geometric algorithms for a minimum cost assignment problem

  1991cited by this paper
• Probabilistic recurrence relations

  1991cited by this paper
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

  1991cited by this paper
• Dynamic maintenance of geometric structures made easy

  1991cited by this paper
• Statistical Zero-Knowledge Languages can be Recognized in Two Rounds

  1991cited by this paper
• Public-Key Cryptography

  1991cited by this paper
• PP is closed under intersection

  1991cited by this paper
• A Catalog of Complexity Classes

  1991cited by this paper
• Counting classes are at least as hard as the polynomial-time hierarchy

  1991cited by this paper
• An introduction to randomized algorithms

  1991cited by this paper
• Fully Dynamic Delaunay Triangulation in Logarithmic Expected Time Per Operation

  1991cited by this paper
• Local expansion of vertex-transitive graphs and random generation in finite groups

  1991influential reference
• Tests for Permutation Polynomials

  1991cited by this paper
• Parallel Tree Contraction Part 2: Further Applications

  1991cited by this paper
• Randomized multidimensional search trees: further results in dynamic sampling

  1991cited by this paper
• An A Priori Approach to the Evaluation of Signature Analysis Efficiency

  1991cited by this paper
• Nondeterministic exponential time has two-prover interactive protocols

  1990cited by this paper
• Coin-flipping games immune against linear-sized coalitions

  1990cited by this paper
• A linear-time probabilistic counting algorithm for database applications

  1990cited by this paper
• Flipping Persuasively in Constant Time

  1990cited by this paper
• High-probability parallel transitive closure algorithms

  1990cited by this paper

• Gathering and Election by Mobile Robots in a Continuous Cycle

  2019cites this paper
• On the Competitive Analysis of Randomized Static Load Balancing

  2017cites this paper
• Computing models for networks of tiny objects

  2017cites this paper
• Investigating System Survivability from a Probabilistic Perspective

  2014cites this paper
• Production line buffer allocation : Genetic algorithms versus simulated annealing

  2013cites this paper
• On the server allocation in large reliable production lines with exponential processing times

  2013cites this paper
• Model checking probabilistic systems against pushdown specifications

  2012cites this paper
• Probabilistic Model of System Survivability

  2010cites this paper
• Uses of randomness in computation

  2010cites this paper
• Model Checking Linear-Time Properties of Probabilistic Systems

  2009cites this paper
• Model checking Markov chains : techniques and tools

  2008cites this paper
• Êêòòóññþþþ Äó Blockin Blockinð Ðð Blockinøøóò× Èöóóóóóðð×øø Òò Ae Blockin

  2007cites this paper
• A comparison of tools

  2007cites this paper
• Òòðý××× Óó Êêòòóññþþþ Êêòòòþúóù× Ððóööøøñ Ú× Å Øøúúúö¸aeae×××ö Ëëëëë¸ñññöö Äêá Íòòúúö××ø Óöùü Á ¹ Aeëëáêê ¿¿½ Óùö× Ðð Äää Öøøóò ¿¿¿¼¼ Ìððò Blockin¸ Öò

  2007cites this paper
• How Fast and Fat Is Your Probabilistic Model Checker? An Experimental Performance Comparison

  2007cites this paper
• Probabilistic model checking : a comparison of tools

  2007cites this paper
• Optimal matching and deterministic sampling

  2007cites this paper
• Development and Analysis of a Gravity-Simulated Particle-Packing Algorithm for Modeling Optimized Rocket Propellants

  2007cites this paper
• Biomolecular Agents as Multi-behavioural Concurrent Objects

  2006cites this paper
• Applications of Orthogonal Arrays to Computer Science

  2006cites this paper
• Effects of Cultural Difference and Task Complexity on Team Interaction Process

  2006cites this paper
• Fault Detection of Hierarchical Networks with Probabilistic Testing Algorithms

  2005cites this paper
• Randomized registers and iterative algorithms

  2005cites this paper
• Using random sampling to build approximate tries for efficient string sorting

  2004cites this paper
• A combinatorial error bound for t-point-based sampling

  2004cites this paper
• Graph Relabelling Systems a Tool for Encoding Proving and Studying Distributed Algorithms

  2003cites this paper
• Analysis of a randomized rendezvous algorithm

  2003cites this paper
• Randomized Parallel Computing

  2003cites this paper
• Convex cone conditions on the structure of designs

  2003cites this paper
• A Unified Framework for Designing, Implementing and Visualizing Distributed Algorithms

  2003cites this paper
• Exploiting design information to derive object distribution models

  2002cites this paper
• Numeric issues in test software correctness

  2002cites this paper
• Density control through random sampling: an architectural perspective

  2002cites this paper
• Probabilistic Extensions of Semantical Models

  2002cites this paper
• Introduction to Quantum Information Processing

  2002cites this paper
• Applications of probabilistic quorums to iterative algorithms

  2001cites this paper
• Visualization of Distributed Algorithms Based on Graph Relabelling Systems

  2001cites this paper
• Partial correctness for probabilistic demonic programs

  2001cites this paper
• Modular production line optimization: The exPLORE architecture

  2001cites this paper
• Randomized Non-sequential Processes

  2001cites this paper
• Fairneß, Randomisierung und Konspiration in verteilten Algorithmen

  2000cites this paper
• Stochastic Algorithms for Buffer Allocation in Reliable Production Lines

  2000cites this paper
• Äóöøóóö Óöððð× Ê Blockin Blockin Blockinö Ò Áòòóöññøøõùù

  2000cites this paper
• Randomized Rendezvous

  2000cites this paper
• Large production line optimization using simulated annealing

  2000cites this paper
• Distributing Multimedia Content to Balance Quality of Service and Cost

  2000cites this paper
• A simulated annealing approach for buffer allocation in reliable production lines

  2000cites this paper
• Petrinetze zum Entwurf selbststabilisierender Algorithmen

  2000cites this paper
• Specification, implementation and application of randomized regular registers (brief announcement)

  2000cites this paper
• Reasoning about Probabilistic Lossy Channel Systems

  2000cites this paper
• Petrinetze zum Entwurf selbststabilisierender Algorithmen

  2000cites this paper
• Supporting decision making in combinatorially explosive multicriteria situations

  1999cites this paper
• Practical considerations in protocol verification: the E-2C case study

  1999cites this paper
• The Cascade Vulnerability Problem: the detection problem and a simulated annealing approach for its correction

  1998cites this paper
• Identifying Library Functions in Executable Files Using Patterns

  1998cites this paper
• Semantic Theories and Automated Tools for Real-Time and Probabilistic Concurrent Systems

  1997cites this paper
• Perfect Hashing

  1997cites this paper
• Probabilistic Models for the Guarded Command Language

  1997cites this paper
• On growing better decision trees from data

  1996cites this paper
• The verification system by dense timing constraints and probabilities

  1996cites this paper
• Time-Randomness Trade-offs in Parallel Computation

  1996cites this paper
• A Simple Analysis of the Error Probability of Two-Point Based Sampling

  1996cites this paper
• The verification technique of real-time systems using probabilities

  1996cites this paper
• Eventual Determinism: Using Probabilistic Means to Achieve Deterministic Ends

  1996cites this paper
• A Family of Perfect Hashing Methods

  1996cites this paper
• Modeling and verification of randomized distributed real-time systems

  1996cites this paper
• Eventual determinism: using probabilistic means to achieve deterministic ends

  1995cites this paper
• A System for Induction of Oblique Decision Trees

  1994cites this paper
• .2 Two-point Based Sampling

  year unknowncites this paper
• Probabilistic Timed Automata 9.1 Adding Time

  year unknowncites this paper