All Questions
Tagged with st.statistics ds.algorithms
6 questions
2
votes
2
answers
584
views
About learning a single Gaussian in total-variation distance
I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown!
Let $G$ ...
- 1,453
7
votes
2
answers
333
views
Maximizing the number of heads in $N$ tosses by choosing which coin to toss
Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively.
We would like to make $N$ coin tosses and get the maximal number of heads possible.
Unfortunately, we know $P_B$, but $P_A$ is ...
- 9,508
11
votes
4
answers
656
views
Lower bound for testing closeness in $L_2$ norm?
I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:
Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, ...
- 4,491
7
votes
1
answer
946
views
Streaming Algorithms: Motivations for estimating frequency moments
The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,...
- 405
1
vote
1
answer
304
views
Constraint Satisfaction Problem: Choosing real numbers with certain characteristics
I have a set of n real numbers. I also have a set of functions,
f_1, f_2, ..., f_m.
Each of these functions takes a list of numbers as its argument. I also have ...
- 299
6
votes
0
answers
153
views
Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range
I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
- 299