# Questions tagged [sample-complexity]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
95 views

### Lower bound for the OR problem

Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
43 views

### understanding generalized coupon collector for distributions or learning mixture of distribution

Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
153 views

### Understanding Dudley Chaining Argument for Rademacher Bound

I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know ...
230 views

### Qubit gates in google supremacy

The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
74 views

### representation of concept classes and pac learning

I was reading the book of Kearns and Vazirani and I didn't completely understand the following: Let C be a concept class and suppose we want to PAC learn C, they say first consider a larger ...
171 views

### How many samples are needed to reconstruct a path?

Consider an input set of vertices $V$ and vertices $s,t\in V$. The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
180 views

### Sampling monotone Boolean functions

I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n =$ the number ...
237 views

112 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 ...
205 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 ...
68 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 ...
94 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 ...
180 views

717 views

412 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 ...