Cryptography is a beautiful branch of theoretical computer science that seeks to provide guarantees to the art of secret keeping. The questions it poses are fundamental -- does the universe permit asymmetry of computation?
One of the fundamental issues facing deployment of supervised learning models in real life applications is the issue of out-of-distribution (OOD) generalization.
Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)).
The \emph{orbit} of an n-variate polynomial f(\var x) over a field \F, denoted by \orbit{f}, is the set of polynomials obtained by applying invertible affine transformations on the variables of f(\var x), and the orbit of a polynomial class is the
Prof. Arkadev Chattopadhayay (TIFR), Prof. Prahladh Harsha (TIFR), Prof. Mahan Maharaj (TIFR), Prof. Hariharan Narayanan (TIFR), Prof. Jaikumar Radhakrishnan (TIFR)
Time:
Wednesday, 19 May 2021, 16:00 to 17:30
Covering Contributions of Abel Laureate Avi Wigderson
Arkadev Chattopadhyay "Games Avi Plays To Prove Hardness"
Prahlad Harsha "How Avi copes with Difficulty: A computational perspective on randomness and knowledge"