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

TR98-056 | 31st August 1998
Anna Bernasconi, Igor E. Shparlinski

Circuit Complexity of Testing Square-Free Numbers

In this paper we extend the area of applications of
the Abstract Harmonic Analysis to the field of Boolean function complexity.
In particular, we extend the class of functions to which
a spectral technique developed in a series of works of the first author
can be applied.
This extension ... more >>>


TR98-055 | 4th September 1998
Luca Trevisan

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

Comments: 1

We introduce a new approach to construct extractors -- combinatorial
objects akin to expander graphs that have several applications.
Our approach is based on error correcting codes and on the Nisan-Wigderson
pseudorandom generator. An application of our approach yields a
construction that is simple to ... more >>>


TR98-054 | 26th August 1998
Igor E. Shparlinski

On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

Lower bounds are obtained on the degree and the number of monomials of
Boolean functions, considered as a polynomial over $GF(2)$,
which decide if a given $r$-bit integer is square-free.
Similar lower bounds are also obtained for polynomials
over the reals which provide a threshold representation
more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint