Grant: Discovery Grants Program - Individual
McMaster University
$24,000.00
Proof complexity of matrix algebra
FY 2011-12
Summary
Proof Complexity (PC) is an area of theoretical computer science that deals with the computational complexity of formal reasoning. PC is intimately connected to major open problems in complexity theory (notably the famous ""P vs NP"" problem, which lately received a high-degree of notoriety in the press; see, for example, the Globe and Mail article by Kate Allen from August 20, 2010), and to the field of automated theorem proving.
My research is particularly concerned with the complexity of reasoning required for matrix algebra. The language of matrices has become universal in computer science; matrices are used to express all kinds of incidence relationships (such as, for example, connectivity in a network), and formalizing reasoning about matrices, in low complexity, would extend greatly the fields of automated deduction and reverse mathematics.
The Canadian scientific milieu is especially well positioned to work in the field of proof complexity, since the field's motivating question, the aforementioned ""P vs NP"" problem, was posed in 1971 by Prof. Stephen Cook at the University of Toronto. Thus, Canada has traditionally been a hub of activity in this area. The high degree of attention is justified by both the practical importance of the ""P vs NP"" problem, and its status as a ""Millennium Problem"" with a one million dollar prize offered for a solution by the Clay Mathematical institute.
My short-term objective is to apply the techniques of the proof complexity of matrix algebra to lattice-based cryptography, and to give a low circuit-complexity proof of standard matrix identities, employing ideas from finite fields and combinatorial constructions such as clow sequences. My long-term objective is to build a strong case for the security of lattice based cryptography and a low circuit-complexity framework for matrix algebra. All this falls under my program of reverse mathematics of linear algebra, a sub-program of Cook's research thrust.
Finally, I have developed contacts with the industry, and I am training two graduate students, Tim Paterson (Toronto Centre for Forensic Sciences) and Mohamed Sabry (Pitney Bowes Canada) in cryptography.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
249895-2011
Name nom
SoltysKulinicz, Michael
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2011
Award amount
24000
Program id
RGPIN
Program nane 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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Partie
1
Nb partie
5
Application title
Proof complexity of matrix algebra
Keyword
NSERC
Application summary
Proof Complexity (PC) is an area of theoretical computer science that deals with the computational complexity of formal reasoning. PC is intimately connected to major open problems in complexity theory (notably the famous ""P vs NP"" problem, which lately received a high-degree of notoriety in the press; see, for example, the Globe and Mail article by Kate Allen from August 20, 2010), and to the field of automated theorem proving.
My research is particularly concerned with the complexity of reasoning required for matrix algebra. The language of matrices has become universal in computer science; matrices are used to express all kinds of incidence relationships (such as, for example, connectivity in a network), and formalizing reasoning about matrices, in low complexity, would extend greatly the fields of automated deduction and reverse mathematics.
The Canadian scientific milieu is especially well positioned to work in the field of proof complexity, since the field's motivating question, the aforementioned ""P vs NP"" problem, was posed in 1971 by Prof. Stephen Cook at the University of Toronto. Thus, Canada has traditionally been a hub of activity in this area. The high degree of attention is justified by both the practical importance of the ""P vs NP"" problem, and its status as a ""Millennium Problem"" with a one million dollar prize offered for a solution by the Clay Mathematical institute.
My short-term objective is to apply the techniques of the proof complexity of matrix algebra to lattice-based cryptography, and to give a low circuit-complexity proof of standard matrix identities, employing ideas from finite fields and combinatorial constructions such as clow sequences. My long-term objective is to build a strong case for the security of lattice based cryptography and a low circuit-complexity framework for matrix algebra. All this falls under my program of reverse mathematics of linear algebra, a sub-program of Cook's research thrust.
Finally, I have developed contacts with the industry, and I am training two graduate students, Tim Paterson (Toronto Centre for Forensic Sciences) and Mohamed Sabry (Pitney Bowes Canada) in cryptography.