[Recent Activities]
[Teaching]
[Graduate Students]
[Publications and Presentations]
I am very interested in all aspects of algorithms and computational
complexity, and I have just finished the second edition of my book:
An Introduction to the Analysis of
Algorithms —
see below for more details.
I did my PhD at the
University of Toronto,
under the supervision of
Stephen Cook. I am part of
FRAISE, and
two years ago I started teaching
Networks and Security.
My research is greatly inspired by the subject of Combinatorial
Matrix Theory, which
combines linear algebra, graph theory, and
combinatorics, and has a rich algorithmic content.
I am currently the department's graduate advisor for
computer science.
2011/2012:
Earlier courses
- Filip Jeremic, M.Eng., starting.
- Neerja Pophli, Ph.D., in progress.
- Mohamed Sabry, Ph.D., in progress.
- Dragan Rakas, M.Sc., in progress.
- Ariel Fernandez, Ph.D., in progress.
- Tim Paterson, Ph.D., in progress.
- Mohamed Sabry, M.Eng., completed May 2011, project: An
implementation of the GGH cryptosystem.
- Greg Herman,
Ph.D., completed March 2009, thesis title:
Unambiguous functions in logarithmic space
- Craig Wilson, M.Sc., completed May 2008, thesis title: Computing
winning strategies for poset games.
- Tim Paterson, M.Sc., completed April 2006, thesis title: A
propositional proof system with permutation quantification.
- Yu-Tong He, M.Sc., co-supervised with Ryszard Janicki, completed
June 2003, thesis title: Verification of the WAP transaction layer
using the model checker SPIN.
Books
-
|
|
Michael Soltys.
An introduction to the analysis of algorithms
First Edition:
152 pages, ISBN: 978-981-4271-40-0, October 2009
Second Edition:
215 pages, ISBN: 978-981-4401-15-9, May 2012
World Scientific:
[1st ed]
[2nd ed]
Amazon:
[1st ed]
[2nd ed]
|
-
|
|
Michael Soltys.
An introduction to computational complexity
[Click here for a
sample]
Published by the
Jagiellonian University Press.
143 pages, ISBN: 978-83-233-2864-3) 2009.
|
Journal articles
- Michael Soltys,
Proving properties of matrices
over Z2, accepted for publication in the Archive for
Mathematical Logic, March 2012.
[doi]
- Grzegorz Herman and Michael Soltys,
Unambiguous functions in
logarithmic space, Fundamenta Informaticae, 114(2):129-147, 2012.
[doi]
- Michael Soltys,
Feasible proofs of Szpilrajn's theorem: A
proof-complexity framework for concurrent automata,
accepted for
publication in the Journal of Automata, Languages and Combinatorics,
January 2011.
- Michael Soltys and Craig Wilson,
On the complexity of computing
winning strategies for finite poset games,
Theory of Computing Systems, 48(3):680-692, 2011.
[doi]
- Grzegorz Herman and Michael Soltys,
On the Ehrenfeucht-Mycielski
sequence,
Journal of Discrete Algorithms, 7(4):500-508, 2009.
[doi]
We used generate.c to generate the
first 30 million bits of the EM sequence in just two minutes with 2Gb
of RAM.
- Grzegorz Herman, Tim Paterson and Michael Soltys,
A propositional
proof system with quantification over permutations of variables,
Fundamenta Informaticae, 79(1-2):71-83, 2007.
[doi]
- Michael Soltys,
The proof theoretic strength of the Steinitz
Exchange Theorem, Discrete Applied Mathematics, 155(1):53-60, 2007.
[doi]
- Michael Soltys,
LA, Permutations, and the Hajos Calculus,
Theoretical Computer Science, 348(2-3):321-333, December 2005.
[doi]
- Neil Thapen and Michael Soltys,
Weak Theories of Linear Algebra,
Archive for Mathematical Logic, 44(2):195-208, 2005.
[doi]
- Michael Soltys and Stephen Cook,
The complexity of derivations of
matrix identities,
Annals of Pure and Applied Logic, 130(1-3):207-275, December 2004.
[doi]
- Michael Soltys and Alasdair Urquhart,
Matrix Identities and the
Pigeonhole Principle,
Archive for Mathematical Logic, 43(3):351-358, April 2004.
[doi]
- Michael Soltys, Extended Frege and Gaussian Elimination,
Bulletin of the Section of Logic, 31(4):1-17, 2002.
- Michael Soltys,
Berkowitz's Algorithm and Clow Sequences,
Electronic Journal of Linear Algebra, 9:42-54, 2002.
- Stephen Cook and Michael Soltys,
Boolean Programs and Quantified
Propositional Proof Systems,
Bulletin of the Section of Logic, 28(3):119-129, 1999.
Proceedings
- Katharine Blanchard and Michael Soltys,
Perceptions of
foundational knowledge by computer science students,
17th Western Canadian Conference on Computing Education (WCCCE),
University of British Columbia, Vancouver, May 2012.
[slides]
- Michael Soltys, The proof theoretic strength of the Steinitz
exchange theorem, 10th Meeting on Computer Algebra and Applications
(EACA), pages 174-177, Seville, September 2006.
[slides]
- David L. Parnas and Michael Soltys,
Basic Science for Software Developers,
14th International Symposium on Formal Methods, pages 15-20,
Canada, August 2006.
- Michael Soltys,
Feasible Proofs of Matrix Properties with Csanky's
Algorithm,
19th International Workshop Computer Science Logic (CSL),
volume 3634 of Lecture Notes in Computer Science, pages 493-508,
Oxford, August 2005.
[doi]
[slides]
- Michael Soltys,
LA, Permutations, and the Hajos Calculus,
31st International Colloquium on Automata, Languages and Programming
(ICALP), volume 3142 of Lecture Notes in Computer Science, pages
1176-1187, Turku, July 2004.
[doi]
[slides]
- Michael Soltys, Matrix algebra with quantification over
permutations, 9th Meeting on Computer Algebra and Applications (EACA),
pages 301-305, Santander,
July 2004.
- Michael Soltys, Finite Fields and Propositional Proof Systems, The
7th World Multiconference on Systemics, Cybernetics and Informatics,
pages 141-146, Orlando, Florida, July 2003.
- Michael Soltys and Stephen Cook,
The Proof Complexity of Linear Algebra,
17th Annual IEEE Symposium on Logic in Computer Science
(LICS), pages 335-344, Copenhagen, July 2002.
[slides]
Presentations
- Michael Soltys and Greg Herman, Unambiguous functions in
logarithmic space, 5th Conference on Computability in Europe (CiE),
pages 162-175, Heidelberg, August 2009.
- Michael Soltys and Craig Wilson, On the complexity of computing
winning strategies for finite poset games, 4th Conference on
Computability in Europe (CiE), pages 415-424, Athens, June 2008.
[slides]
- Michael Soltys, Feasible proofs of matrix identities with
Csanky's algorithm, The 7th International Workshop on Logic and
Computational Complexity, LCC, affiliated with the 20th Annual IEEE
Symposium on Logic in Computer Science (LICS), Chicago, June 2005.
A selection of invited presentations
- NIST Approach to Information Security,
Formal Requirements and Information Security Enhancement
(FRAISE) Research Group, McMaster University, May 2012.
- An overview of cryptography: A mathematical perspective on
public key cryptosystems, McMaster Advanced Optimization
Laboratory, October 2008.
- Computational complexity, Universidad de Rio Cuarto,
Argentina, February 2008.
- Computational complexity, Ulam Seminar, University of
Colorado at Boulder, September-December 2007.
- Computational complexity, University of Poznan, June 2007.
- Proof complexity, Algorithmics Research Group, Jagiellonian
University, Krakow, May 2007.
- Computational complexity: an overview of open problems,
Universidad Autonoma, Madrid, December 2006.
- The proof complexity of matrix algebra,
An Isaac Newton Institute Workshop, New Directions in Proof
Complexity, Cambridge, April 2006.
[slides]
- Tim Paterson and Michael Soltys, A propositional proof system
with quantification over permutations, Franco-Canadian Workshop on
Combinatorial Algorithms (COMAL), August 2005.
- Proof complexity of the Cayley-Hamilton theorem, Center for
Discrete Mathematics and Theoretical Computer Science (DIMACS),
Rutgers University, New Jersey, March 2005
- Proof complexity of matrix algebra, Oberwolfach workshop in proof
complexity, Germany, March 2005.
- Proof complexity of linear algebra, University of California at
San Diego, January 2005.
- Proof complexity, Grupo de Lenguajes y Sistemas Informaticos
(LSI), Universidad Politecnica de Cataluna (UPC), Barcelona, May 2004.
- Matrix products, Symposium for Computing in the XXI century,
McMaster University, October 2001.
- Complexity of derivations of matrix identities, Institute for
Advanced Studies (IAS), Workshop on Proof Complexity, Princeton,
December 2000.
- Boolean programs and quantified propositional proof systems,
Canadian Mathematical Society Winter Meeting, Montreal, December 1999.
[slides]
Technical reports
- Michael Soltys,
Gaussian lattice reduction algorithm terminates in
polynomial time,
McMaster Computing and Software Technical Report (CAS-11-10-MS),
2011.
- Michael Soltys,
A note on finding a
rational symmetric matrix for
a given separable polynomial,
McMaster Computing and Software
Technical Report (CAS-08-12-MS), 2008.
- Greg Herman and Michael Soltys,
A polytime proof of correctness of
the Rabin-Miller algorithm from Fermat's little theorem,
arXiv (CoRR
abs/0811.3959), 2008.
- David L. Parnas and Michael Soltys,
Basic Science for Software Developers,
McMaster SQRL Technical Report (7), 2002.
- Michael Soltys,
A Model-Theoretic Proof of the Completeness of LK Proofs,
McMaster Computing and Software Technical Report (CAS-06-05-MS), 1999.
(Originally posted on elogic, March 30, 1999.)
Other
- David Bremner, Antoine Deza and Michael Soltys,
Foreword: selected papers from the Franco-Canadian workshop on
combinatorial algorithms,
Journal of Combinatorial Optimization, 16(4):323, 2008.
[doi]
- Más que difícil,
complejo; interviewed by Bruno Massare for Information Technology
(Argentina), May 2008.
- Michael Soltys,
The complexity of derivations of matrix identities.
PhD thesis, University of Toronto, 2001.
Last modified:
Mon May 21 09:34:59 EDT 2012
