|
|
Prof. Shafi Goldwasser
Simons Institute for the Theory of
Computing at UC Berkeley, USA
The Cryptographic Lens
Going beyond the basic challenge of private communication, in the last 35 years, cryptography has become the general study of correctness and privacy of computation in the presence of a computationally bounded adversary, and as such has changed how we think of proofs, randomness, secrets, and information. In this talk I will discuss some beautiful developments in the theory of computing through this Cryptographic Lens, as well as recent developments in cryptography that may allow the next successful shift from local to cloud computing.
Montag, 7. Oktober 2019, 19.30 Uhr
Pseudo Deterministic Algorithms and Proofs
Probabilistic algorithms for both decision and search problems can offer significant complexity improvements over deterministic algorithms. One major difference, however, is that they may output different solutions for different choices of randomness. This is less than desirable in settings where uniqueness of output is important such as in the generation of system-wide cryptographic parameters or in a distributed setting where different sources of randomness are used. Pseudo-deterministic algorithms are a class of randomized search algorithms, which output a unique answer with high probability. Intuitively, they are indistinguishable from deterministic algorithms by a polynomial time observer of their input/output behavior. In this talk I will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. I will also describe an extension of pseudo-deterministic algorithms to interactive proofs for search problems where the verifier is guaranteed with high probability to deliver the same output on different executions, regardless of the prover strategies.
Dienstag, 8. Oktober 2019, 17.15 Uhr
Safe Machine Learning
Cryptography and Computational Learning have shared a curious history: a scientific success for one often provided an example of an impossible task for the other. Today, the goals of the two fields are aligned. Cryptographic models and tools can and should play a role in ensuring the safe use of machine learning. I will discuss this development with its challenges and opportunities.
Mittwoch, 9. Oktober 2019, 19.30 Uhr
|
