How to generate random strings from Context-Free Grammar in GNF

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform n traversals of production rules, as every traversal adds exactly one symbol to the string. The problem with this approach is that the choice of productions to expand cannot … Read more

Randomized version of the class APXAPX?

Is there a class which is to APX what BPP is to P? I’m looking for a definition that is like the following: “For r>0, an r-RPCA (randomized polynomial-time constant-factor approximation) algorithm for a function problem T:Σ∗→N is a probabilistic Turing machine A with the following property: A runs in time poly(|x|) and has P(r−1T(x)≤A(x)≤rT(x))≥2/3.” … Read more

Finding a node in a binary tree by looking at the path between it and the root

There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node s. All nodes in the (s,root) path are marked somehow (yellow nodes in the picture) so we can check using a check operation if a node … Read more

An algorithm which efficiently generates random samples without replacement, from a large range [0-N], N ~ 10^12?

I want an algorithm which generates random integers, without replacement, from a large range [0-N], N~10^12. However, the whole range should not be stored in memory. The memory footprint should be O(1) relative to N. The algorithm can (probably must) retain state after every sample request. The randomness should be “strong” in the cryptographic sense. … Read more

Analyzing a randomized algorithm for finding an approximate median of an array

I’m given an array A = (a1,a2,⋯an), where n is uneven. For an element ai we denote its position in the array with p(ai). This element would be an ε-approximate median of the array, if after we sort it, the following inequality holds: \frac12 ((1 – ε) × n) < p(a_i) \leqslant \frac12 ((1 + … Read more

Heuristic algorithm for the minimum weighted s-t cut with linear running time

To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with O(n2√m) time complexity. I’m interested in solving this problem as a separation sub-problem inside a branch and cut algorithm, so I don’t always need the optimal solution. Is there a heuristic/approximation/randomized … Read more

How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits m in the array A (initialized to zeros), and number of hash functions k, an insertion of an item x corresponds to setting A[hi(x)]=1 for i=1,…,k. Similarly, for testing if an item x was … Read more

Space complexity of using a pairwise independent hash family

I’m trying to analyze the space complexity of using the coloring function f which appears in “Colorful Triangle Counting and a MapReduce Implementation”, Pagh and Tsourakakis, 2011, https://arxiv.org/abs/1103.6073. As far as I understand, f:[n]→[N] is a hash function, that should be picked uniformly at random out of a pairwise independent hash functions family H. I … Read more

Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?

Consider some problem P and let’s assume we sample the problem instance u.a.r. from some set I. Let p be a lower bound on the distributional error of a deterministic algorithm on I, i.e., every deterministic algorithm fails on at least a p-fraction of the instances in I. [Edit: For a given instance s∈I, we … Read more