# Questions tagged [lower-bounds]

The tag has no usage guidance.

135 questions
Filter by
Sorted by
Tagged with
1 vote
49 views

### Counting the number of local minima of a function that is the sum of square roots of cosines

Suppose you are given a set of functions $f_1, \ldots, f_n$. Every function is defined as follows $$f_i(x) = \sqrt{1+C^2_i-2C_i\cos (x-D_i)}$$ where $0<C_i<1$ and $0\leq D_i<2\pi$ are real-...
• 21
319 views

• 145
679 views

### The expected value of product of random variables which have the same distribution but are not independent

Given a positive integer $k$, is there a positive real number $c(k)$ such that $\mathbb{E}\left(\prod_{i=1}^k X_i\right)\geq c(k)$ for any $k$-random variables $X_1,X_2,\ldots,X_k$ which all have the ...
• 99
1 vote
351 views

### Markov Inequality for lower bounds

In a paper I found a strange application of Markovs inequality which I couldn't follow maybe you can help. $X_k$ is the set of $k$-element Subsets of $\mathbb{Z}_d^n$ we fix a $C^{-1} \in X_{k-1}$ and ...
1 vote
106 views

### What is known about the average growth rate of the denominators of $n$ Egyptian fractions summing to one?

Motivation In the following question posted here on MO and over at MSE, user Noah Schweber asks about a weighted count on Egyptian fraction representations (EFRs). To that end, he defines the ...
• 4,605
46 views

237 views

• 3,929
1 vote
279 views

### Tree width and clique width of regular graphs

Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular ...
169 views

• 129
381 views

• 145
263 views

### An inequality involving binomial coefficients and the powers of two

I came across the following inequality, which should hold for any integer $k\geq 1$: $$\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-j)}{2k+1-j}\leq \frac{1}{3}.$$ I have been struggling with ...
• 145
195 views

### When does Le Cam's method give tight lower bounds for distribution testing?

In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: ...
• 33