Michael Soltys-Kulinicz Associate Professor Computing and Software McMaster University 1280 Main Street West Hamilton, ON., Canada L8S 4K1 [Google Map][Campus Map] Office: ITB-214 Phone: 905-525-9140 ext. 27769 E-mail:

I am interested in the theory of computation, in particular complexity and algorithms. I did my PhD at the University of Toronto, under the supervision of Stephen Cook.

Recent Activities

• 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

• Theory of Computation (CS2MJ3): [Fall 2009] [Fall 2006]
• Computational Complexity (CAS705): [Fall 2009] [Fall 2008] [Fall 2006] [Fall 2005] [Fall 2004] [Fall 2003]
• Intro to Cryptography (Math 4440, at the University of Colorado): [Spring 2008]
• Introducción a la Teoría de la Complejidad (Universidad Nacional de Río Cuarto) [Febrero 2008]
• Complexity Theory (Math 8815, Ulam Seminar at the University of Colorado): [Fall 2007]
• Linear Algebra (Math 3130, at the University of Colorado): [Fall 2007]
• Complexity Theory (Jagiellonian University): [Summer 2007]
• Software Design I (CS2ME3): [Winter 2010] [Winter 2009] [Winter 2007] [Winter 2006] [Winter 2005] [Winter 2004]
• Communication Skills (CS2CS3/SE3IO3): [Fall 2008]
• Computational Complexity (CAS776): [Fall 2002]
• Theoretical Foundations of Computation (SE4I03): [Fall 2005] [Fall 2004] [Fall 2003] [Fall 2002] [Fall 2001]
• Operating Systems Concepts: [Winter 2003 (CS3SH3)] [Winter 2002 (CS4SH3)]
• Computability and Complexity (University of Toronto, CSC364): [Summer 2001] [Summer 2000] [Summer 1999]

Graduate Students

• Ariel Fernandez, Ph.D., in progress.
• Tim Paterson, Ph.D., in progress.
• Mohamed Sabry, M.Sc., in progress.
• Grzegorz 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

(In chronological order)

• Book:

  Michael Soltys. An introduction to the analysis of algorithms. This is a teaser of my forthcoming book on algorithms. 2009 Published by World Scientific (also available from Amazon).

• Greg Herman and Michael Soltys. Unambiguous Functions in Logarithmic Space. Presented at Computability in Europe 2009.
• Book:

  Michael Soltys. An introduction to computational complexity. This is a teaser of my forthcoming book on computational complexity. 2009 Published by the Jagiellonian University Press.

• 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), November 2008.
• Greg Herman and Michael Soltys. A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem. See arXiv:0811.3959v1, November 2008.
• Greg Herman and Michael Soltys. On the Ehrenfeucht-Mycielski sequence. In the Journal of Discrete Algorithms, volume 7, issue 4, December 2009.
  (You can generated the successive bits of the EM sequence with our C program generate.c; we have used it to generate the first 30 million bits of the EM sequence in just two minutes with 2Gb of RAM. Here is also a very simple Perl script, generate.pl, that generates the sequence (and some stats) in a straighforward way, without the clever opitmizations of the C program--and so it is only useful for, say, the first 1,000 bits.)
• Más que difícil, complejo; interviewed by Bruno Massare for Information Technology (Argentina), May 2008.
• Michael Soltys and Craig Wilson. On the complexity of computing winning strategies for finite poset games. To appear in a special issue of Theory of Computing Systems. Also presented at Computability in Europe 2008; click here for the presentation slides.
• David Bremner, Antoine Deza and Michael Soltys (Editors). Selected papers from the Franco-Canadian Workshop on combinatorial algorithms. To appear in the Journal of Combinatorial Optimization.
• Greg Herman, Tim Paterson, Michael Soltys. A propositional proof system with quantification over permutations. Fundamenta Informaticae, Volume 79, 2007, pp. 1-13. (Tim Paterson also presented this paper at COMAL'05.)
• Michael Soltys. The proof theoretic strength of the Steinitz Exchange theorem. Algebra Computacional y Aplicaciones Workshop (EACA'06), Sevilla, September 7-9, 2006. (Click here for the presentation slides.)
• Michael Soltys. The proof theoretic strength of the Steinitz Exchange Theorem. Discrete Applied Mathematics, Volume 155, Issue 1, January 2007, pp. 53-60.
• Michael Soltys. The Proof Complexity of Matrix Algebra. New Directions in Proof Complexity, An Isaac Newton Institute Workshop, Cambridge, April 10-13, 2006.
• Michael Soltys. LA, Permutations, and the Hajos Calculus. Theoretical Computer Science, Volume 348, Issues 2-3, December 2005, pp. 321-333.
• Michael Soltys. Feasible Proofs of Matrix Properties with Csanky's Algorithm. Computer Science Logic (CSL'05), Oxford, August 2005, pp. 493-508. Click here for the presentation slides.
• Michael Soltys. Feasible Proofs of Matrix Properties with Csanky's Algorithm. Logic and Computational Complexity Workshop (LCC), affiliated with LICS, Chicago, June 24-25, 2005.
• Neil Thapen and Michael Soltys. Weak Theories of Linear Algebra. Archive for Mathematical Logic, Volume 44, Number 2, February 2005, pp. 195-208.
• Michael Soltys and Stephen Cook. The Proof Complexity of Linear Algebra. Annals of Pure and Applied Logic, Volume 130, Issues 1-3, December 2004, pp. 277-323.
• Michael Soltys. LA, Permutations, and the Hajos Calculus. 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Turku, July 2004, pp. 1176-1187. Click here for the presentation slides.
• Michael Soltys. Matrix algebra with quantifiers over permutations. Algebra Computacional y Aplicaciones Workshop (EACA'04), Santander, July 1-3, 2004.
• Michael Soltys and Alasdair Urquhart. Matrix Identities and the Pigeonhole Principle. Archive for Mathematical Logic, Volume 43/3, April 2004, pp. 351-357.
• Michael Soltys. Extended Frege and Gaussian Elimination. Bulletin of the Section of Logic, Volume 31/4 (2002), pp. 1-17.
• Michael Soltys. Berkowitz's Algorithm and Clow Sequences. Electronic Journal of Linear Algebra (ELA), Volume 9 (2002), pp. 42-54.
• Michael Soltys. Finite fields and propositional proof systems. World multiconference on Systemics, Cybernetics, and Informatics, Orlando 2003, pp. 141-146.
• Michael Soltys and Stephen Cook. The Proof Complexity of Linear Algebra. 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02), 2002, pp. 335-344. Click here for the presentation slides.
• David L. Parnas and Michael Soltys. Basic science for software developers. SQRL Report Series, #7, 2002. Click here for the (shorter) version that appeared at Formal Methods 2006, in the Education Workshop, August 2006.
• Michael Soltys. The complexity of derivations of matrix identities. PhD thesis, 2001.
• Michael Soltys. The complexity of derivations of matrix identities. Workshop on Complexity of Proofs and Computations, Institute for Advanced Study, Princeton, December 10-16, 2000.
• Michael Soltys. Boolean programs and quantified propositional proof systems. Canadian Mathematical Society Winter Meeting, December 1999.
• Stephen Cook and Michael Soltys. Boolean Programs and Quantified Propositional Proof Systems. The Bulletin of the Section of Logic, Volume 28/3 (1999), pp. 119-129.
• Michael Soltys. A model-theoretic proof of the completeness of LK proofs. March 30, 1999. (Technical report CAS-06-05-MS at McMaster University.)

Last modified: Thu Jul 30 15:24:03 EDT 2009