Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-020 | 13th March 2002 00:00

On one lower bound for branching programs

RSS-Feed




TR02-020
Authors: Elizaveta Okol'nishnikova
Publication: 25th March 2002 22:46
Downloads: 3244
Keywords: 


Abstract:

The method of obtaining lower bounds on the complexity
of Boolean functions for nondeterministic branching programs
is proposed.
A nonlinear lower bound on the complexity of characteristic
functions of Reed--Muller codes for nondeterministic
branching programs is obtained.



ISSN 1433-8092 | Imprint