# Tagged Questions

The tag has no usage guidance.

79 views

### NP problems with exponentially complex average time solution?

Assuming $P \ne NP$, is there a problem such that is NP such that: There is always a solution Alternatively, there is asymptotically almost surely a solution On average, it takes exponential time ...
24 views

97 views

### Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
27 views

### Show that a function is not a PRFs

I am studying cryptography and having some trouble with the PRFs How do I show that $f_{k}(x) =x+k^2$ mod $2^n$ is not a Psuedo Random function? I know that I need to show that the distignuisher can ...
76 views

### Sampling random graphs with Eulerian paths

How to generate random graphs with eulerian Paths? Its well known that there is a eulerian path if the number of nodes with odd degree is exactly 2 or zero. I'm interested in an algorithm to make ...
38 views

### Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1)

There's a problem which I had on a number of unrelated occasions which I usually work around in some way or another. Deep inside, though, it bothers me that I haven't ever found a “proper” solution to ...
244 views

### Why do we care about random Boolean SAT formula?

I've been looking for a reference for the above question. As far as I know the answer is: If we can make a solver that is efficient for all randomly generated instances, it should be efficient for ...
145 views

### Random permutations by probability matrix

I have the following problem: I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$. ...
51 views

### Sampling from a Acyclic Deterministic Finite Automaton

Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ). How can we efficiently sample a word from $L$ with uniform ...
98 views

### Can someone explain LazySelect?

The LazySelect algorithm is given in these slides as follows. We have a set $S$ of $n = 2k$ distinct numbers and want to find the $k$th smallest element. Let $R$ be a set of $n^{3/4}$ elements ...
73 views

### Randomized Algorithm with matrices [closed]

We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$. We want to check if the matrices of the computers are identical except for exactly 1 entry. Comp1 has ...
99 views

### Finding the kth element of a permutation [closed]

Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) ...
349 views

### What's the problem of using the clock to generate random numbers?

If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number? What is wrong with this form of generating random numbers? I am aware that ...
915 views

### Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution)

Presume I have the following case: int value a int value b, for which a < b int value i,...
107 views

### Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random, The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of ...