Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Random Access Machine:
TR96-025 | 22nd March 1996
Berthold Ruf

The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials

Recently one has started to investigate the
computational power of spiking neurons (also called ``integrate and
fire neurons''). These are neuron models that are substantially
more realistic from the biological point of view than the
ones which are traditionally employed in artificial neural nets.
It has turned out that the ... more >>>

TR08-076 | 17th June 2008
Ryan Williams

Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

ISSN 1433-8092 | Imprint