<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto">Colloquium Speaker<div>Ran Raz, The Weizmann Institute of Science</div><div>Monday, November 30, 12:30pm</div><div>Computer Science 105</div><div><br></div><div><h1 class="page-header" style="box-sizing: border-box; margin: 0px 0px 20px; font-weight: 500; padding-bottom: 9px; border-bottom-width: 1px; border-bottom-style: solid; border-bottom-color: rgb(238, 238, 238);"><span style="font-size: 21px; background-color: rgba(255, 255, 255, 0);">Delegation of Computation, P-completeness of Linear Programming, and the many facets of the notion of a proof</span></h1></div><div><span style="font-size: 21px; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Suppose that Alice performs some computation for Bob, as he does not have sufficient computational power to run the computation himself. Can Bob be convinced that the computation was done correctly?<br style="box-sizing: border-box;"><br style="box-sizing: border-box;">Delegation of Computation is a central problem in modern cryptography. I will describe a recent one-round delegation protocol. The discussion will take us on a journey into the notion of a proof, through some of the most fascinating ideas in the history of theoretical computer science. I will conclude with a seemingly unrelated application to the P-completeness of Linear Programming with a fixed polytope.</span></div></body></html>