Grant: Discovery Grants Program - Individual
York University
$23,000.00
Branching Program Lower Bounds
FY 2020-21
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-06288
Name nom
Edmonds, Jeffrey
Department département
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
2020
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 grants programs
Group fr
Programmes de subventions à 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:2-5
Partie
4
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.