Volume 2, 1995
: New Lower Bounds and Hierarchy Results for Restricted Branching Programs.
: A Note on Realizing Iterated Multiplication by Small Depth Threshold Circuits.
, Jie Wang
: Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions.
: Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate.
, Erez Petrank
: An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions.
, Omer Reingold
: Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions.
Douglas R. Stinson
: On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes.
: Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems.
: On Extracting Randomness From Weak Random Sources.
Nader H. Bshouty
: A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries.