Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > STATISTICAL QUERY:
Reports tagged with statistical query:
TR01-098 | 19th November 2001
Ke Yang

#### On Learning Correlated Boolean Functions Using Statistical Query

In this paper, we study the problem of using statistical
query (SQ) to learn highly correlated boolean functions, namely, a
class of functions where any
pair agree on significantly more than a fraction 1/2 of the inputs.
We give a limit on how well ... more >>>

TR02-060 | 15th July 2002
Ke Yang

#### New Lower Bounds for Statistical Query Learning

We prove two lower bounds on the Statistical Query (SQ) learning
model. The first lower bound is on weak-learning. We prove that for a
concept class of SQ-dimension $d$, a running time of
$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is
defined to be the maximum number ... more >>>

TR03-014 | 28th February 2003
Avrim Blum, Ke Yang

#### On Statistical Query Sampling and NMR Quantum Computing

We introduce a Statistical Query Sampling'' model, in which
the goal of an algorithm is to produce an element in a hidden set
$S\subseteq\bit^n$ with reasonable probability. The algorithm
gains information about $S$ through oracle calls (statistical
queries), where the algorithm submits a query function $g(\cdot)$

TR15-126 | 27th July 2015
Jacob Steinhardt, Gregory Valiant, Stefan Wager

#### Memory, Communication, and Statistical Queries

Revisions: 1

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>

ISSN 1433-8092 | Imprint