4 votes

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 ...
Aryeh's user avatar
  • 10.5k
4 votes
Accepted

Differential Privacy and Randomized Responses for Counting Queries

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives $$\mathbb{P}\left[\left|\frac{1}{n} ...
Thomas's user avatar
  • 2,803
3 votes

Sum of Independent Exponential Random Variables

For the Laplace distribution, if you use the Bernoulli bound you can write $$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$$ where $\sigma^2=2\sum_i\lambda_i^{-2}$....
Thomas Ahle's user avatar
2 votes
Accepted

Chernoff bound for weighted sums of Bernoulli random variables

Your bound (at least when $t\le E[S]$) seems to follow from the standard multiplicative Chernoff bound, as follows. Lemma 1. (a standard multiplicative Chernoff bound) Let $S$ be the sum of ...
Neal Young's user avatar
  • 10.7k
2 votes

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

Using Chandra's hint, I think I got the idea. We bounded the probability: $$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$ Now consider an item of size $s_i$ that was left. It was ...
user3508551's user avatar
  • 1,153
1 vote
Accepted

Additive chernoff bound

The generic Chernoff bound for a random variable $X$ is attained by applying Markov's inequality to $e^{t X}$. For positive $t$ this gives a bound on the right tail of $X$ in terms of its moment-...
Dotman's user avatar
  • 109
1 vote

Sample Complexity for Order Statistics

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ ...
Vaishakh Ravi's user avatar
1 vote

Janson-type inequality, limited dependence

I'm posting a suitable answer that I found for this problem. The approach linked here does not exploit the fact that no $t$-tuples of elements of $\Omega$ are present in too many subsets $Y$ (for ...
mm8511's user avatar
  • 203

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