# Tag Info

Accepted

• 321

### How is additive error handled in this simple algorithm? 'Product of all elements'

Use Taylor series expansion for the function $\prod_{i=1}^{n} (u_i + y)$ around $y=0$ to obtain the error as $\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$. Note that Taylor ...
• 171
Accepted

### References on generalization bounds

For a concise overview the ideas you can read Mendelson's notes on the topic. For a bit more check out the outline (and the links in it) by Kontorovich on how the basic and most fundamental bonds ...
• 168

### OR-circuit complexity of a dense linear operator

(I tried to post this as a comment to Stasys' answer above, but this text is too long for a comment, so posting it as an answer.) Ivan Mihajlin (@ivmihajlin) came up with the following construction. ...

### Is the center of a BFS tree a good approximation of the graphs center?

In the worst case, this algorithm gives a 2-approximation (the trivial upper bound). Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. ...
• 211
1 vote

### Upper Bound for distance-two chromatic number in terms of maximum degree

Let $\Delta$ denote the maximum degree of $G$. The bound $\Delta^2+1$ cannot be improved significantly. For instance, even for a colouring variant called 2-ranking (which is a generalisation of ...
• 1,827
1 vote

### Common terminology used for lower/upper bounds

The term “tight” has multiple uses, as is mentioned in a comment. However, you seem to be interested in a combinatorial context or on a combinatorial-type problem so I’m going to assume that contexts. ...
• 1,046
1 vote
Accepted

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound. When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|... • 427 1 vote ### Probability of random variable$X$less than$max(Y_i)$We have$\Pr[\max(Y_1,Y_2) \leq k] = \Pr[Pois(\lambda) \leq k]^2 = e^{-2\lambda}(\sum_{j=0}^k\frac{\lambda^j}{j!})^2$. Therefore,$\Pr[X \geq \max(Y_1,Y_2)] = \sum_{k \in \mathbb N} \Pr[X = k] \cdot \...
• 1,927

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