Michael Soltys-Kulinicz Associate Professor Computing and Software McMaster University 1280 Main Street West Hamilton, ON., Canada L8S4K1 [Google Map] [Campus Map] Office: ITB-214 Phone: 905-525-9140 x27769 E-mail: soltys@mcmaster.ca Public Key: 9B070A58

I am currently teaching a course in Networks and Security; I am very interested in all aspects of algorithms, 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.

Recent Activities

• October 2011: BIRS Proof Complexity Workshop.
• Winner of the 2010/2011 McMaster Student Union teaching award for the faculty of Engineering.
• Academic year 2007/2008: Visiting Ulam Professor in the Department of Mathematics at the University of Colorado in Boulder.
• February 18-23, 2008: Teaching a computational complexity workshop at the XV Escuela de Verano de Ciencias Informáticas, Departamento de Computación, Universidad Nacional de Río Cuarto.
• Summer 2007: visiting scholar in the Theoretical Computer Science Department at the Jagiellonian University.

Teaching

• CAS 705: Computability and Complexity
• CS 2MJ3: Theory of Computation
• CS 3C03 / SE 4C03: Computer Networks & Security

Graduate Students

• Neerja Pophli, Ph.D., starting.
• Mohamed Sabry, Ph.D., starting.
• Dragan Rakas, M.Sc., starting.
• 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.

Publications and Presentations

Books

• Michael Soltys. An introduction to the analysis of algorithms [Click here for a sample] Published by World Scientific (also available from Amazon). 152 pages (ISBN: 978-981-4271-40-0), October 2009. 2nd edition, 215 pages, submitted to the publisher in November 2011.

• 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

• Grzegorz Herman and Michael Soltys, Unambiguous functions in logarithmic space, accepted for publication in Fundamenta Informaticae, November 2011.
• 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

• 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]
• 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]
• 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 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

• 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.

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: Tue Jan 31 09:03:35 EST 2012