Questions tagged [bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers

Tail bounds for sum of weighted Poisson random variables

Let $X_1,X_2,\ldots,X_n$ be $n$ independent Poisson random variables with $\mu(X_i) = \lambda_i$. I am interested in upper tail bounds for the random variable $Z = \sum_{i} a_i X_i$ where $a_i \in [0,...
user avatar
11 votes
2 answers

Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = ...
user avatar
0 votes
1 answer

What relations has different bounds for NP?

this is my first question here so I hope I've done everything correctly. I know that if someone finds a polynomial solution to any of the famous NP problems, all of them has one (polynomial solution)....
user avatar
  • 165
17 votes
3 answers

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...
user avatar