Branching Program Lower Bounds

点击翻译按钮获取中文摘要

Two Topics:***I am proposing two quite independent topics: Branching program lower***bounds and machine learning. I have 30 years of experience and a great***deal of success in the first and the last six months I have taken a***few courses and read a few books in the second. In today's job market,***students tend to be drawn to Machine Learning rather than Logic (such***as Lower Bounds).There is also a large job market for HQP with Machine***Learning expertise. In addition to already existing expertise in AI***and Deep Learning, York U is starting a new program dedicated to***Machine Learning to address this need. My plan is to include training***students in this discipline in the future.******Lower Bounds in Branching Programs: ***For both practical and theoretical reasons, we would like to know the***minimum amount of time (or space) needed to solve a given***computational problem on an input of a given size. An upper bound***provides an algorithm that achieves some time bound. A lower bound***proves that no algorithm correctly solves the problem faster no matter***how clever. Proving lower bounds on general models of computation***(eg. in JAVA or a Turing Machine) is beyond our reach. For this***reason, researchers often prove lower bounds on weaker modes of***computation. The most powerful model of computation measuring the***amount of space used by an algorithm is branching programs. We will***continue in this important area of fundamental research in order to***understand more about the limits of computation.******Machine Learning:***Computers can now drive cars and find cancer in x-rays. For better or***worse, this will change the world (and the job market). Strangely,***designing these algorithms is not done by telling the computer what to***do or even by understanding what the computer does. The computers***learn themselves from lots and lots of data and lots of trial and***error. This learning process is more analogous to how brains evolved***over billions of years of learning. The machine itself is a neural***network which models both the brain circuits, which are great for***computing. The only difference with neural networks is that what they***compute is determined by weights and small changes in these weights***give you small changes in the result of the computation. The process***for finding an optimal setting of these weights is analogous to***finding the bottom of a valley. If a machine can give the correct***answers on randomly chosen training data without simply memorizing,***then we can prove that with high probability the same machine will***also work well on never seen before instances.**