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

TR97-049 | 22nd October 1997
Michael Schmitt

On the Complexity of Learning for Spiking Neurons with Temporal Coding

Spiking neurons are models for the computational units in
biological neural systems where information is considered to be encoded
mainly in the temporal pattern of their activity. In a network of
spiking neurons a new set of parameters becomes relevant which has no
counterpart in traditional ... more >>>


TR97-048 | 13th October 1997
Soren Riis, Meera Sitharam

Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

The semantics of decision problems are always essentially independent of the
underlying representation. Thus the space of input data (under appropriate
indexing) is closed
under action of the symmetrical group $S_n$ (for a specific data-size)
and the input-output relation is closed under the action of $S_n$.
more >>>


TR97-047 | 20th October 1997
Miklos Ajtai

The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

We show that the shortest vector problem in lattices
with L_2 norm is NP-hard for randomized reductions. Moreover we
also show that there is a positive absolute constant c, so that to
find a vector which is longer than the shortest non-zero vector by no
more than a factor of ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint