Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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


TR02-059 | 9th August 2002
Iordanis Kerenidis, Ronald de Wolf

Exponential Lower Bound for 2-Query Locally Decodable Codes

We prove exponential lower bounds on the length of 2-query
locally decodable codes. Goldreich et al. recently proved such bounds
for the special case of linear locally decodable codes.
Our proof shows that a 2-query locally decodable code can be decoded
with only 1 quantum query, and then ... more >>>


TR02-058 | 25th September 2002
Philippe Moser

A generalization of Lutz's measure to probabilistic classes

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes
C
such as BPP , BPE and BPEXP. Unlike former attempts,
all our measure notions satisfy all three Lutz's measure axioms, that is
every singleton {L} has measure zero ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint