F. Bergadano, N.H. Bshouty, Stefano Varricchio

It has been shown in previous recent work that

multiplicity automata are predictable from multiplicity

and equivalence queries. In this paper we generalize

related notions in a matrix representation

and obtain a basis for the solution

of a number of open problems in learnability theory.

Membership queries are generalized ...
more >>>

Sanjeev Arora, Madhu Sudan

NP = PCP(log n, 1) and related results crucially depend upon

the close connection between the probability with which a

function passes a ``low degree test'' and the distance of

this function to the nearest degree d polynomial. In this

paper we study a test ...
more >>>

Scott Aaronson, Paul Christiano

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that ... more >>>