Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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)$
and receives ... more >>>

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