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

TR05-051 | 18th March 2005
Predrag Tosic

On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

Revisions: 2

We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>>


TR05-050 | 18th April 2005
Uriel Feige, Eran Ofek

Finding a Maximum Independent Set in a Sparse Random Graph

Revisions: 1

We consider the problem of finding a maximum independent set in a
random graph. The random graph $G$ is modelled as follows. Every
edge is included independently with probability $\frac{d}{n}$, where
$d$ is some sufficiently large constant. Thereafter, for some
constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ... more >>>


TR05-049 | 1st April 2005
Joan Boyar, rene peralta

The Exact Multiplicative Complexity of the Hamming Weight Function

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint