COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Rational ProofsAdd to your list(s) Download to your calendar using vCal - Micali, S (MIT)
- Tuesday 10 April 2012, 14:30-15:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing We unify the treatment of asymmetry of information in theoretical computer science and economics. We put forward a new type of proof system, where an unbounded Prover and a polynomial time Verifier interact, on inputs a string x and a function f, so that the Verifier may learn f(x). In our setting there no longer are “good” or “malicious” Provers, but only RATIONAL ones. In essence, (1) the Verifier gives the Prover a reward in [0,1] determined by the transcript of their interaction; (2) the Prover wishes to maximize his expected reward; and (3) the reward is maximized only if the verifier correctly learns f(x). Rational proofs are as powerful as interactive ones, but can be amazingly more efficient in the amount of communication involved: that is, the number of bits exchanged and the number of rounds of interaction. Joint work with Pablo Azar. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsKeyser Group Seminar Type the title of a new list here Cambridge University United Nations Association (CUUNA)## Other talksMacrophage-derived extracellular succinate licenses neural stem cells to suppress chronic neuroinflammation Number, probability and community: the Duckworth-Lewis-Stern data model, Monte Carlo simulations and counterfactual futures in cricket A sex-linked supergene controls sperm morphology and swimming speed in a songbird Oncological imaging: introduction and non-radionuclide techniques |