“Cryptographers seldom sleep well. A polynomial time algorithm for factoring would certainly prove more crushing than any paltry fluctuation of the Dow Jones. The effect a proof that P=NP would have is unspeakable.” - Joe Kilian, ‘88.
To try to sleep better, we aim to base cryptosystems on the simplest possible assumptions. The most fundamental one is the existence of one-way functions: functions that are easy to compute, but hard to invert. What cryptographic capabilities can one-way functions provide? Can we use them to build public-key cryptography, secure computation and more? The work of Impagliazzo and Rudich in ‘91 showed that the answer is probably no.
How about if we had access to simple quantum resources? With quantum channels, the landscape of feasibility changes dramatically. My talk will discuss some new results and challenges in this area.
Abstract: Part of the recent flourishing of computer vision is applying a recipe: collect a lot of data with ground truth, then train a classification or regression procedure using this data. This is powerful, but awkward. I will describe some ways in which we can train methods without ground truth. In the classic problem of intrinsic image decomposition (turn an image into albedo and shading) such methods are strongly competitive with the state-of-the-art. Relighting (take an image and make it look as though the lights had changed) is a new problem for which ground truth data doesn't -- and likely can't -- exist in quantity. I will describe how one can learn to relight without ever knowing what the right answer is.
Bio: I am currently Fulton-Watson-Copp chair in computer science at U. Illinois at Urbana-Champaign, where I moved from U.C Berkeley, where I was also full professor. I have occupied the Fulton-Watson-Copp chair in Computer Science at the University of Illinois since 2014. I have published over 170 papers on computer vision, computer graphics and machine learning. I have served as program co-chair for IEEE Computer Vision and Pattern Recognition in 2000, 2011, 2018 and 2021, general co-chair for CVPR 2006 and 2015 and ICCV 2019, program co-chair for the European Conference on Computer Vision 2008, and am a regular member of the program committee of all major international conferences on computer vision. I have served six years on the SIGGRAPH program committee, and am a regular reviewer for that conference. I have received best paper awards at the International Conference on Computer Vision and at the European Conference on Computer Vision. I received an IEEE technical achievement award for 2005 for my research. I became an IEEE Fellow in 2009, and an ACM Fellow in 2014. My textbook, "Computer Vision: A Modern Approach" (joint with J. Ponce and published by Prentice Hall) is now widely adopted as a course text (adoptions include MIT, U. Wisconsin-Madison, UIUC, Georgia Tech and U.C. Berkeley). A further textbook, “Probability and Statistics for Computer Science”, came out two years ago; yet another (“Applied Machine Learning”) has just appeared. I have served two terms as Editor in Chief, IEEE TPAMI. I serve on a number of scientific advisory boards, and have an active practice as an expert witness.