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-024 | 24th April 2002
Piotr Indyk

List-decoding in Linear Time

Spielman showed that one can construct error-correcting codes capable
of correcting a constant fraction $\delta << 1/2$ of errors,
and that are encodable/decodable in linear time.
Guruswami and Sudan showed that it is possible to correct
more than $50\%$ of errors (and thus exceed the ``half of the ... more >>>


TR02-023 | 16th April 2002
Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

We prove a quasi-polynomial lower bound on the size of bounded-depth
Frege proofs of the pigeonhole principle $PHP^{m}_n$ where
$m= (1+1/{\polylog n})n$.
This lower bound qualitatively matches the known quasi-polynomial-size
bounded-depth Frege proofs for these principles.
Our technique, which uses a switching lemma argument like other lower bounds
for ... more >>>


TR02-022 | 12th April 2002
Henry Markram

On the Computational Power of Recurrent Circuits of Spiking Neurons

Understanding the structure of real-time neural computation in
highly recurrent neural microcircuits that consist of complex
heterogeneous components has remained a serious challenge for
computational modeling. We propose here a new conceptual framework
that strongly differs from all previous approaches based on
computational models inspired ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint