Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

1
vote
1answer
50 views

Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
9
votes
0answers
114 views

How to sample a lot of independent uniform spanning trees?

There are a bunch of good algorithms for sampling a uniform spanning tree from a graph $G$. For example, Aldous/Broder and Wilson's algorithm are pretty efficient. However, each of these graphs only ...
1
vote
0answers
62 views

Complexity of Proportional Sampling

Let $p_1,...,p_n$ be a list of numbers, each specified by $n^{O(1)}$ bits. Let $\mu = \sum_{i} p_i$ be the sum of all numbers in the list. I want to sample from the set $\{1,...,n\}$ where each $j$ is ...
4
votes
0answers
86 views

Sampling Functions Efficiently vs Pseudorandom Generators

Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions ...
4
votes
1answer
147 views

How well do subspaces hit sets

Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$. Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$. I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\...
3
votes
0answers
154 views

About lower bounding the sample complexity of a distribution

Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
1
vote
0answers
138 views

How does one sample uniformly at random from an uncountably infinite set?

I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible) Does it help if the sample ...
2
votes
2answers
261 views

Coreset and VC dimension

I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation ...
1
vote
1answer
214 views

Evaluating the expected value of negatively correlated random variables

A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, ...
4
votes
1answer
469 views

Sample complexity of distinguishing two Gaussian distributions?

Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples $X_1^{(...
3
votes
1answer
154 views

Almost uniform sampling implies approximate counting

I began studying papers about approximate counting and I keep seeing the above being quoted, without further explanation. I suppose the procedure that yields the result is very well known and that is ...
2
votes
1answer
155 views

Determining the number of clusters using property testing algorithm

We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of ...
2
votes
1answer
95 views

Approximating the value of k in $k$-mean clustering problem

Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
11
votes
1answer
230 views

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas: Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$. ...
22
votes
1answer
432 views

Sampling satisfiable 3-SAT formulas

Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned ...
1
vote
2answers
308 views

algorithms to split data into roughly equal sized quantiles

What is the state-of-the art on algorithms that calculate/estimate approximate quantiles? I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having ...
17
votes
1answer
957 views

The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and ...
5
votes
1answer
240 views

VC-Dimension and sample complexity dependent on size of subsets

I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ ...
9
votes
1answer
373 views

What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?

Since no answer was given, a flag has been set requesting that this question be converted to a community wiki. The comments by Aaron Sterling, Sasho Nikolov, and Vor have been synthesized into the ...
6
votes
1answer
441 views

Efficiently Samplable Distributions

What does it mean for a distribution to be efficiently samplable? This came up in the discussions about the distributions used in the recent attempted P!=NP proof. The context was that a ...
12
votes
2answers
313 views

Computational query complexity of SQ-learning

It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...