# Tag Info

Accepted

• 451
Accepted

### A question on combinatorial algorithm

[EDIT: Added second proof, using Hall's theorem.] Theorem 1. There is a poly-time algorithm for the problem. We give a direct proof, then another proof using Hall's theorem. Both proofs use the ...
• 10.9k

### Random point in a d-dimensional ball

For the latter, this discussion is a good starting point. For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.
• 191

### Max cut problem between two connected subgraphs

Here is a straightforward reduction from the max-cut problem: Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a ...
• 3,440
Accepted

### What is a very simple pseudodeterministic algorithm (for educational purposes)?

The Tonelli–Shanks algorithm for computing square roots modulo primes. More generally, factorization of polynomials over finite fields using the Cantor–Zassenhaus algorithm. Both can be made ...
• 18.2k

### Is there a linear space lower bound for streaming set equality?

There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and ...
• 51.1k

### Random sampling data structure with removal

Here's an idea: Store the weights in the leaves of a balanced binary tree, and at each intermediate node store the sum of weights at the leaves underneath. Now we can sample it in log time by taking ...
• 548

### Can we fast generate perfectly uniformly mod 3 or solve NP problem?

So here is an extension of Emil's argument that shows that search problems where the number of solutions is 1, 2 or 4 (we do not need to know which) can be solved in the above way. I'm posting it as ...
• 14.1k
Accepted

### Naive shuffle algorithm

You can also try to get some intuition from the "correct" version, Fisher-Yeates / Knuth shuffle. for i in range(len(vec)-1): swap(i, randint(i, len(vec)-1)) ...
• 7,748

### How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time?

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up ...
• 10.6k
Yes. You can generate a random polynomial of degree $k$, then evaluate this polynomial at $n$ different points in $\tilde{O}(n)$ time using the DFT (the DFT lets you evaluate a polynomial of degree \$...