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

TR95-052 | 4th October 1995
Douglas R. Stinson

On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

In this primarily expository
paper, we discuss the connections between two popular and useful
tools in theoretical computer science, namely,
universal hashing and pairwise
independent random variables; and classical combinatorial stuctures
such as error-correcting codes, balanced incomplete block designs,
difference matrices
... more >>>


TR95-051 | 16th October 1995
Pascal Koiran

VC Dimension in Circuit Complexity

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ... more >>>


TR95-050 | 15th October 1995
Oded Goldreich, Noam Nisan, Avi Wigderson

On Yao's XOR-Lemma

Revisions: 2 , Comments: 1


previous PreviousNext next


ISSN 1433-8092 | Imprint