Grant: Discovery Grants Program - Individual
York University
$23,000.00
Branching Program Lower Bounds
EF 2019-20
Résumé
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.**
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2019-06288
Name nom
Edmonds, Jeffrey
Department département
Electrical Engineering & Computer Science
Organization id
38
Institution établissement
York University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2019
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Branching Program Lower Bounds
Keyword
NSERC
Application summary
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.**