On the role of shared randomness in two prover proof systems
Mihir Bellare, U. Feige, et al.
ISTCS 1995
We present a general technique to upper bound the spectral norm of an arbitrary function. At the heart of our technique is a theorem which shows how to obtain an upper bound on the spectral norm of a decision tree given the spectral norms of the functions in the nodes of this tree. The theorem applies to trees whose nodes may compute any boolean functions. Applications are to the design of efficient learning algorithms and the construction of small depth threshold circuits (or neural nets). In particular, we present polynomial time algorithms for learning O(log n) clause DNF formulas and various classes of decision trees, all under the uniform distribution with membership queries.
Mihir Bellare, U. Feige, et al.
ISTCS 1995
Yishay Mansour
ACM COLT 1992
Mihir Bellare, S. Goldwasser, et al.
STOC 1993
Mihir Bellare, J. Garayy, et al.
USENIX EC 1998