Michael Soltys
Michael Soltys-Kulinicz
Professor and Chair
Computer Science
CSU Channel Islands

Office: Bell Tower West 2265
E-mail: michael.soltys@csuci.edu
Public Key: 9B070A58



Michael Soltys ResearchGate Michael Soltys GitHub Repository Michael Soltys Blog Michael Soltys ACM Digital Library View Michael Soltys's profile on LinkedIn
CV of Michael Soltys
[PDF, 95K]

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


Recent Activities


Teaching

2014/2015: Complete list of courses

Graduate Students


Publications and Presentations

Books

  1. Intro to Algorithms Intro to Algorithms 2ed
    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] [Chapter 1]
    Amazon: [1st ed] [2nd ed]
  2. Intro to Complexity
    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 papers

  1. Neerja Mhaskar and Michael Soltys, String Shuffle: Circuits and Graphs, accepted for publication in the Journal of Discrete Algorithms, January 2015. [doi] [shuffle-generator] [blog]
  2. Sam Buss and Michael Soltys, Unshuffling a Square is NP-Hard, Journal of Computer and System Sciences, 80(4):766-776, 2013. [doi] [arXiv] [slides] [shuffle-square] [shuffle-generator]
  3. Michael Soltys, Proving properties of matrices over Z2, Archive for Mathematical Logic, 51(5):535-551, 2012. [doi]
  4. Grzegorz Herman and Michael Soltys, Unambiguous functions in logarithmic space, Fundamenta Informaticae, 114(2):129-147, 2012. [doi]
  5. Michael Soltys, Feasible proofs of Szpilrajn's theorem: A proof-complexity framework for concurrent automata, Journal of Automata, Languages and Combinatorics, 16(1):27-38, 2011. [journal]
  6. 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]
  7. Grzegorz Herman and Michael Soltys, On the Ehrenfeucht-Mycielski sequence, Journal of Discrete Algorithms, 7(4):500-508, 2009. [doi] [generate-em] (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).
  8. 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]
  9. Michael Soltys, The proof theoretic strength of the Steinitz Exchange Theorem, Discrete Applied Mathematics, 155(1):53-60, 2007. [doi]
  10. Michael Soltys, LA, Permutations, and the Hajos Calculus, Theoretical Computer Science, 348(2-3):321-333, December 2005. [doi]
  11. Neil Thapen and Michael Soltys, Weak Theories of Linear Algebra, Archive for Mathematical Logic, 44(2):195-208, 2005. [doi]
  12. Michael Soltys and Stephen Cook, The Proof Complexity of Linear Algebra, Annals of Pure and Applied Logic, 130(1-3):207-275, December 2004. [doi]
  13. Michael Soltys and Alasdair Urquhart, Matrix Identities and the Pigeonhole Principle, Archive for Mathematical Logic, 43(3):351-358, April 2004. [doi]
  14. Michael Soltys, Extended Frege and Gaussian Elimination, Bulletin of the Section of Logic, 31(4):1-17, 2002.
  15. Michael Soltys, Berkowitz's Algorithm and Clow Sequences, Electronic Journal of Linear Algebra, 9:42-54, 2002. [ELA repository]
  16. Stephen Cook and Michael Soltys, Boolean Programs and Quantified Propositional Proof Systems, Bulletin of the Section of Logic, 28(3):119-129, 1999.

Proceedings

  1. Neerja Mhaskar and Michael Soltys, Non-repetitive strings over alphabet lists, WALCOM: Algorithms and Computation, volume 8973 of Lecture Notes in Computer Science, pages 270-281, February 2015. [doi] [shuffle-square] [shuffle-generator] [blog]
  2. 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 1138-1144, Pomorski Park Naukowo-Techniczny (PPNT), Gdynia, September 2014. Best Paper Award. [doi] [slides] [blog]
  3. 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 777-788, IST, Klosterneuburg, Austria, August 2013. Click here for an expanded proof of Claim 8 in the paper. [doi] [slides]
  4. Michael Soltys, Circuit complexity of shuffle, the International Workshop on Combinatorial Algorithms (IWOCA), volume 8288 of the Lecture Notes in Computer Science, pages 402-411, Rouen, France, July 2013. [doi] [slides]
  5. 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]
  6. 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]
  7. David L. Parnas and Michael Soltys, Basic Science for Software Developers, 14th International Symposium on Formal Methods, pages 15-20, Canada, August 2006.
  8. 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] [arXiv]
  9. 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]
  10. Michael Soltys, Matrix algebra with quantification over permutations, 9th Meeting on Computer Algebra and Applications (EACA), pages 301-305, Santander, July 2004.
  11. Michael Soltys, Finite Fields and Propositional Proof Systems, The 7th World Multiconference on Systemics, Cybernetics and Informatics, pages 141-146, Orlando, Florida, July 2003.
  12. 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

  1. Ariel Fernández and Michael Soltys, Feasible combinatorial matrix theory: polytime proofs for König's Min-Max and related theorems, short presentation at LICS 2013. [slides] [full version]
  2. Michael Soltys and Greg Herman, Unambiguous functions in logarithmic space, 5th Conference on Computability in Europe (CiE), pages 162-175, Heidelberg, August 2009. [slides]
  3. 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]
  4. 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

  1. Algorithms on Strings, joint seminar of Mathematics and Computer Science, California State University at Channel Islands, February 4, 2015. [slides]
  2. 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.
  3. How safe is your data?, Toronto Association of Police and Private Security (TAPPS), invited talk, May 12, 2014. [slides] [blog]
  4. An algorithmic view of Computer Science, Department of Computer Science, California State University at Channel Islands, November 1, 2013. [slides]
  5. Unshuffling a Square is NP-hard, Department of Computer Science and Engineering, Theory seminar, University of California, San Diego, December 3, 2012. [slides]
  6. NIST Approach to Information Security, Formal Requirements and Information Security Enhancement (FRAISE) Research Group, McMaster University, May 2012.
  7. An overview of cryptography: A mathematical perspective on public key cryptosystems, McMaster Advanced Optimization Laboratory, October 2008.
  8. Computational complexity, Universidad de Rio Cuarto, Argentina, February 2008.
  9. Computational complexity, Ulam Seminar, University of Colorado at Boulder, September-December 2007.
  10. Computational complexity, University of Poznan, June 2007.
  11. Proof complexity, Algorithmics Research Group, Jagiellonian University, Krakow, May 2007.
  12. Computational complexity: an overview of open problems, Universidad Autonoma, Madrid, December 2006.
  13. The proof complexity of matrix algebra, An Isaac Newton Institute Workshop, New Directions in Proof Complexity, Cambridge, April 2006. [slides]
  14. Tim Paterson and Michael Soltys, A propositional proof system with quantification over permutations, Franco-Canadian Workshop on Combinatorial Algorithms (COMAL), August 2005.
  15. Proof complexity of the Cayley-Hamilton theorem, Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), Rutgers University, New Jersey, March 2005
  16. Proof complexity of matrix algebra, Oberwolfach workshop in proof complexity, Germany, March 2005.
  17. Proof complexity of linear algebra, University of California at San Diego, January 2005.
  18. Proof complexity, Grupo de Lenguajes y Sistemas Informaticos (LSI), Universidad Politecnica de Cataluna (UPC), Barcelona, May 2004.
  19. Matrix products, Symposium for Computing in the XXI century, McMaster University, October 2001.
  20. Complexity of derivations of matrix identities, Institute for Advanced Studies (IAS), Workshop on Proof Complexity, Princeton, December 2000.
  21. Boolean programs and quantified propositional proof systems, Canadian Mathematical Society Winter Meeting, Montreal, December 1999. [slides]

Technical reports

  1. Michael Soltys, Gaussian lattice reduction algorithm terminates in polynomial time, McMaster Computing and Software Technical Report (CAS-11-10-MS), 2011.
  2. 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.
  3. Greg Herman and Michael Soltys, A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem, 2008. [arXiv]
  4. David L. Parnas and Michael Soltys, Basic Science for Software Developers, McMaster SQRL Technical Report (7), 2002.
  5. 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

  1. 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]
  2. Más que difícil, complejo; interviewed by Bruno Massare for Information Technology (Argentina), May 2008.
  3. 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