Skip to main content
Share Your Experience: Take the 2024 Developer Survey
6 votes
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 ...
Neal Young's user avatar
  • 10.8k
5 votes
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 ...
Emil Jeřábek's user avatar
2 votes
Accepted

Moments and Deviation (Motwani and Raghavan, 3.7)

I think you're overthinking this. Construct the witness set $W=\{0, 1, ..., \epsilon n\}$ (or really any contigious sequence of size $\epsilon n$). Consider the events where $b$ was selected from $\{\...
user3508551's user avatar
  • 1,153
1 vote

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

Here is a bit artificial example, not sure whether you'll like it: Given $m=pq$, where $p$ and $q$ are large primes, and a primitive root $g$ of $\mathbb Z_m^*$, compute $1/g$ or factorize $m$. ...
domotorp's user avatar
  • 14k
1 vote

Generalized assignment problem with overall budget

The problem is NP-hard, by reduction from the the knapsack problem. ($B$ represents the maximum weight capacity of the knapsack, and for each item, add a new pair of task and worker with cost equal ...
D.W.'s user avatar
  • 12.1k

Only top scored, non community-wiki answers of a minimum length are eligible