CCI Department Of Computer Science Dr. Werner Krandick Lecture: Dr. Erich Kaltofen
Monday, January 25, 2021
11:00 AM-12:00 PM
The Department of Computer Science at Drexel's College of Computing & Informatics is pleased to welcome Dr. Erich Kaltofen for its Dr. Werner Krandick Lecture.
Talk Title: "Proof-of-Work Certificates for Cloud Delegated Massive Computations"
About the Talk:
Computations done by high-power cloud servers such as a Google data center can yield outputs that are easy to verify, such as the factors of an integer, but outputs can also be non-trivial to certify quickly, such as minimum number of face-turns required to solve Rubik's Cube from any possible permutation.
Interactive proof protocols speed the complexity of the output verification by interaction between the high-power `Prover' and the `Verifie', in fact, a polynomial-time `Verifier' can certify all computational problems of PSPACE. The interaction can be removed to yield a proof-of-work certificate whose correctness is based on cryptographic assumptions on what even the high-power `Prover' cannot compute. Dr. Kaltofen will give a selection of certificates, among them our certificate for the rank profile of a matrix and the sum of all determinants of n by n symmetric
matrices with entries either 0 or 1. The latter is the famous sum-check protocol, which can be generalized to certify Rubik's Cube minimal solution. He will also give an example of an argument for protocol-soundness, which establishes that the `Prover' cannot cheat the `Verifier'.
About the Speaker:
Erich Kaltofen received his PhD degree in Computer Science in 1982 from Rensselaer Polytechnic Institute. He was an Assistant Professor of Computer Science at the University of Toronto and an Assistant, Associate, and Professor at Rensselaer Polytechnic Institute. Since 1996 he is a Professor of Mathematics at North Carolina State University. He has held visiting positions at ENS Lyon, MIT, UPMC Paris, U. Grenoble, and U. Waterloo. Kaltofen's current interests in the symbolic computation discipline are hybrid symbolic/numeric algorithms, efficient algorithms for sparse interpolation and error correction and interactive proofs. Kaltofen has designed several algorithms for polynomial factorization including one for polynomials in straight-line representation. Kaltofen was the Chair of ACM's Special Interest
Group on Symbolic & Algebraic Manipulation 1993-95. From 1985-87 he held an IBM Faculty Development Award. In 2009 Kaltofen was selected an ACM Fellow. Learn more at: https://math.sciences.ncsu.edu/people/kaltofen/
About Dr. Werner Krandick:
The Department of Computer Science annually hosts a distinguished lecturer in honor of the late Werner Krandick, PhD. Dr. Krandick joined Drexel University as an Assistant Professor of Mathematics and Computer Science in 2001 and was promoted to Associate Professor in 2006. Dr. Krandick was an outstanding professor whose lectures were detailed and precise, allowing students to fully comprehend complicated mathematical reasoning. He received his PhD in Computer Science from Ohio State University in 1992 where he wrote his thesis, "Symbolic Methods for Polynomial Complex Root Calculation," under the supervision of his advisor, Dr. George Collins. Prior to achieving his PhD, he received his BS and MS in Mathematics respectively at Universität Freiburg in 1981 and Universität Bonn in 1987. Before working at Drexel, Dr. Krandick was a postdoctoral researcher at the Universität Paderborn in Germany, as well as the Research Institute for Symbolic Computation (RISC) in Linz, Austria where he was a Lise Meitner Fellow.