[Recent Activities]
[Teaching]
[Graduate Students]
[Publications and Presentations]
I am the Chair and full professor in the department of Computer Science, at CSU Channel
Islands. I joined the department in 2014. Before that, starting in
2001, I was a professor in the department of Computing
and Software, at McMaster University.
I finished my Ph.D. in 2001 at the University of
Toronto, under the supervision of Stephen
Cook.
My research is in algorithms, especially in their proofs of
correctness. Currently I am working in the area of String
Algorithms and in Combinatorial Matrix Theory, where the
latter combines linear algebra, graph theory, and combinatorics, and
has a rich algorithmic content. The second edition of my book: An
Introduction to the Analysis of Algorithms has
been published in 2012. Recently I have become interested in
Ranking Algorithms, and especially in the elegant Pairwise
Comparisons Method.
A significant part of my work is in the area of Information
Security. I have taught the Networks & Security course, and I
consult for Executek and Algos.
2014/2015:
Complete list of courses
 Neerja Mhaskar, Ph.D., in progress.
 Mohamed Sabry, Ph.D., in progress.
 Ariel Fernandez, Ph.D., completed August 2013, thesis title:
Formalizing Combinatorial Matrix Theory.
 Filip Jeremic, M.Eng., completed May 2013, project title:
Parallel Lattice Basis Reduction.
 Dragan Rakas, M.Sc., completed May 2013, thesis title: A
Proof of Concept for Homomorphically Evaluating an Encrypted Assembly
Language.
 Mohamed Sabry, M.Eng., completed May 2011, project title: 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.
 YuTong He, M.Sc., cosupervised 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: 9789814271400, October 2009
Second Edition:
215 pages, ISBN: 9789814401159, May 2012
World Scientific:
[1st ed]
[2nd ed]
[Chapter 1]
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: 9788323328643, 2009.

Journal papers
 Neerja Mhaskar and Michael Soltys,
String Shuffle:
Circuits and Graphs, accepted for publication
in the Journal of Discrete Algorithms, January 2015.
[doi]
[shufflegenerator]
[blog]
 Sam Buss and Michael Soltys,
Unshuffling a Square is
NPHard, Journal of Computer
and System Sciences, 80(4):766776, 2013.
[doi]
[arXiv]
[slides]
[shufflesquare]
[shufflegenerator]
 Michael Soltys,
Proving properties of matrices
over Z2, Archive for
Mathematical Logic, 51(5):535551, 2012.
[doi]
 Grzegorz Herman and Michael Soltys,
Unambiguous functions in
logarithmic space, Fundamenta Informaticae, 114(2):129147, 2012.
[doi]
 Michael Soltys,
Feasible proofs of Szpilrajn's theorem: A
proofcomplexity framework for concurrent automata,
Journal of Automata, Languages and Combinatorics, 16(1):2738, 2011.
[journal]
 Michael Soltys and Craig Wilson,
On the complexity of computing
winning strategies for finite poset games,
Theory of Computing Systems, 48(3):680692, 2011.
[doi]
 Grzegorz Herman and Michael Soltys,
On the EhrenfeuchtMycielski
sequence,
Journal of Discrete Algorithms, 7(4):500508, 2009.
[doi]
[generateem]
(In 2008, we used generate.c in order to obtain the
first 30 million bits of the EM sequence in just under 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(12):7183, 2007.
[doi]
 Michael Soltys,
The proof theoretic strength of the Steinitz
Exchange Theorem, Discrete Applied Mathematics, 155(1):5360, 2007.
[doi]
 Michael Soltys,
LA, Permutations, and the Hajos Calculus,
Theoretical Computer Science, 348(23):321333, December 2005.
[doi]
 Neil Thapen and Michael Soltys,
Weak Theories of Linear Algebra,
Archive for Mathematical Logic, 44(2):195208, 2005.
[doi]
 Michael Soltys and Stephen Cook,
The Proof Complexity of
Linear Algebra,
Annals of Pure and Applied Logic, 130(13):207275, December 2004.
[doi]
 Michael Soltys and Alasdair Urquhart,
Matrix Identities and the
Pigeonhole Principle,
Archive for Mathematical Logic, 43(3):351358, April 2004.
[doi]
 Michael Soltys, Extended Frege and Gaussian Elimination,
Bulletin of the Section of Logic, 31(4):117, 2002.
 Michael Soltys,
Berkowitz's Algorithm and Clow Sequences,
Electronic Journal of Linear Algebra, 9:4254, 2002.
[ELA repository]
 Stephen Cook and Michael Soltys,
Boolean Programs and Quantified
Propositional Proof Systems,
Bulletin of the Section of Logic, 28(3):119129, 1999.
Proceedings
 Neerja Mhaskar and Michael Soltys,
Nonrepetitive strings over alphabet lists,
WALCOM: Algorithms and Computation, volume 8973 of
Lecture Notes in Computer Science, pages 270281,
February 2015.
[doi]
[shufflesquare]
[shufflegenerator]
[blog]
 Michael Soltys,
Fair ranking in competitive bidding procurement:
A case analysis,
18th International Conference in Knowledge Based and Intelligent
Information and Engineering Systems (KES),
volume 35,
Procedia Computer Science,
pages 11381144,
Pomorski Park NaukowoTechniczny (PPNT),
Gdynia, September 2014. Best Paper Award.
[doi]
[slides]
[blog]
 Ariel Fernández and Michael Soltys,
Feasible combinatorial
matrix theory, 38th International Symposium on
Mathematical Foundations of
Computer Science (MFCS),
volume 8087 of Lecture Notes in Computer Science, pages 777788, IST,
Klosterneuburg, Austria, August 2013.
Click here
for an expanded proof of Claim 8 in the paper.
[doi]
[slides]
 Michael Soltys,
Circuit complexity of shuffle,
the International Workshop on Combinatorial Algorithms (IWOCA),
volume 8288 of the Lecture Notes in Computer Science, pages 402411,
Rouen, France, July 2013.
[doi]
[slides]
 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.
[doi]
[slides]
 Michael Soltys, The proof theoretic strength of the Steinitz
exchange theorem, 10th Meeting on Computer Algebra and Applications
(EACA), pages 174177, Seville, September 2006.
[slides]
 David L. Parnas and Michael Soltys,
Basic Science for Software Developers,
14th International Symposium on Formal Methods, pages 1520,
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 493508,
Oxford, August 2005.
[doi]
[slides]
[arXiv]
 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
11761187, Turku, July 2004.
[doi]
[slides]
 Michael Soltys, Matrix algebra with quantification over
permutations, 9th Meeting on Computer Algebra and Applications
(EACA), pages 301305, Santander, July 2004.
 Michael Soltys, Finite Fields and Propositional Proof
Systems, The 7th World Multiconference on Systemics, Cybernetics
and Informatics, pages 141146, 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 335344, Copenhagen, July 2002.
[slides]
Presentations
 Ariel Fernández and Michael Soltys,
Feasible
combinatorial matrix theory: polytime proofs for König's MinMax
and related theorems, short presentation at LICS 2013.
[slides]
[full version]
 Michael Soltys and Greg Herman, Unambiguous functions in
logarithmic space, 5th Conference on Computability in Europe (CiE),
pages 162175, Heidelberg, August 2009.
[slides]
 Michael Soltys and Craig Wilson, On the complexity of computing
winning strategies for finite poset games, 4th Conference on
Computability in Europe (CiE), pages 415424, 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.
[slides]
Selected talks
 Algorithms on Strings, joint seminar of Mathematics and
Computer Science, California State University at Channel Islands,
February 4, 2015.
[slides]
 Fair ranking in competitive bidding procurement: A case
analysis, joint seminar of Mathematics and Computer Science,
California State University at Channel Islands, October 15, 2014.
 How safe is your data?, Toronto Association of Police and
Private Security (TAPPS), invited talk, May 12, 2014.
[slides]
[blog]
 An algorithmic view of Computer Science, Department of
Computer Science, California State University at Channel Islands,
November 1, 2013.
[slides]
 Unshuffling a Square is NPhard, Department of Computer
Science and Engineering, Theory seminar, University of California, San
Diego, December 3, 2012.
[slides]
 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, SeptemberDecember 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, FrancoCanadian Workshop on
Combinatorial Algorithms (COMAL), August 2005.
 Proof complexity of the CayleyHamilton 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 (CAS1110MS),
2011.
 Michael Soltys,
A note on finding a
rational symmetric matrix for
a given separable polynomial,
McMaster Computing and Software
Technical Report (CAS0812MS), 2008.
 Greg Herman and Michael Soltys,
A polytime proof of correctness of
the RabinMiller algorithm from Fermat's little theorem, 2008.
[arXiv]
 David L. Parnas and Michael Soltys,
Basic Science for Software Developers,
McMaster SQRL Technical Report (7), 2002.
 Michael Soltys,
A ModelTheoretic Proof of the Completeness of LK Proofs,
McMaster Computing and Software Technical Report (CAS0605MS), 1999.
(Originally posted on elogic, March 30, 1999.)
Other
 David Bremner, Antoine Deza and Michael Soltys,
Foreword: selected papers from the FrancoCanadian 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:
Sun May 3 17:53:21 PDT 2015