Cryptography and Complexity Reading Seminar

Organizers: Alex Myasnikov and Sasha Ushakov

Mondays, Wednesdays, 12:30.
Room: Babio 320
Subscribe to receive automatic announcements about the seminar

Seminar schedule:

• April 23rd. P. Weil, "Algebraic and logical methods for the classification of regular languages."
• April 4th. M. de Mare, "Strengths and weaknesses of quantum computing"
• March 28th. P. Babaali, "Automata, regular languages and thier asymptotic properties."
• March 13th. A. Ushakov, "Polynomial-time solution of the word problem in Baumslag-Gersten group"
  Download slides
• March 7-14. A. Duncan, "Introduction to Quantum Computation"
  Download slides
• February 20th. A. Ushakov. "Polynomiality of the Word problem in the group of automorphisms of a free group".  
  Download paper.
• February 13th. A. Myasnikov. "Incomplete decision procedures for Presburger arithmetic".  
• February 7th. S. Rybalov. "Natural proofs".  
  Download slides.
  See discussion at AlgebraForum
• February 5th. M. Elder. "Asymptotic density of subgroups of Thompson's group F".  
  Suggested reading.
• January 29th. S. Rybalov. "Quantifier elimination for Presburger arithmetic".  
• January 24th. S. Rybalov. "Fischer-Rabin's proof for lower bounds on the computational complexity of the decision problem for Presburger arithmetic".
  Download slides.
   

Quantum Computation:

• Eleanor G. Rieffel, Wolfgang Polak. "An Introduction to Quantum Computing for Non-Physicists"
• Batty, Braunstein, Duncan and Rees. "Quantum Algorithms in Group Theory."
• Batty, Braunstein, Duncan "Extending the Promise of the Deutsch-Jozsa-Hoyer Algorithm for Finite Groups"
• Lectures of the Sixth Canadian Summer School on Quantum Information Processing

Presburger arithmetic:

• M.J.Fischer, M.O.Rabin. Super-Exponential Complexity of Presburger Arithmetic.
• Predrag Janicic, Ian Green, Alan Bundy, A comparison of decision procedures in Presburger arithmetic
• Felix Klaedtke. On the Automata Size for Presburger Arithmetic.