Theoretical Computer Science

Seminar

Summer Term 2019

News

Mai 08

The seminar has been scheduled for 11:30 on Monday, in room IZ 358

April 23

For the second kick-off meeting we suggest 11:30 on Thursday, April 25, presumably in room IZ 305

April 18

The possible topics have been expanded, see below.

April 03

If you are interested in participating but have not registered yet, just come to the kickoff meeting!

April 03

The date for the Kickoff meeting has been fixed, see below.

Organisation

• The kickoff meeting will take place on Monday, April 15, at 15:00 in room IZ 305.
• We will present possible topics and the details of the organization at the kickoff meeting.
• Number of participants: We give topics to at most 12 students.
• Target audience: Computer Science students. This is a joint seminar for Bachelor's and Master's students.

Requirements

• prepare and give a talk of 30 minutes (including questions) during the lecture period, and
• write a seminar paper in English or German, 10 pages using the LIPIcs LaTeX style until the end of the term.

Topics

• Complexity Theory:
  Fourier Meets Möbius: Fast Subset Convolution
• Automatic verification:
  either Fragment Abstraction for Concurrent Shape Analysis (master level)
  or An Integrated Specification and Verification Techniquefor Highly Concurrent Data Structures (bachelor level)
• The hidden subgroup problem concerns certain computationally hard problems often used in cryptographic protocolls, e.g., factoring, the discrete logarithm problem, and the shortest vector problem. All these would become "easy", if a quantum computer became available; algorithms for solving these problems already exist (e.g., Shor's algorithm).
  
  Lately, a very efficient graphical calculus for describing the underlying mathematics has been developed, which allegedly makes it much easier to understand, why the proposed algorithms work. This achievement in large part is due to Bob Coecke, who together with Aleks Kissinger has since written a book on this topic. Another important researcher in this area is Jamie Vicary These new techniques may be applicable to other areas than quantum computations.
  
  Possible papers for presentations:
  
  • Shor's original paper from 1994:
    Algorithms for Quantum Computation: Discrete Logarithms and Factoring
    
  • Jozsa's paper linking Shor's algorithm to the hidden subgroup problem, uses traditional notation:
    Quantum factoring, discrete logarithms and the hidden subgroup problem
    
  • Vicary's paper introducing his version of the graphical calculus; has a nice appendix entitled "Topological Algebra"; this is suitable for 2 talks:
    The Topology of Quantum Algorithms
    
  • A paper by Kissinger and Gogioso that establishes "strong complementarity" as essential ingredient for the success of the diagrammatic calculus:
    Fully Graphical Treatment of the Quantum Algorhithm for the Hidden Subgroup Problem
    
  • An paper by Coecke, Duncan, Kissinger and Wang on "strong complementarity":
    Strong Complementarity and Non-locality in Categorical Quantum Mechanics
    
  • An paper by Vicary and Stay on using the graphical calculus for verifying cryptographic protocols:
    Bicategorical Semantics for Nondeterministic Computation
    
  • An older paper linking the hidden subgroup problem with Eigenvalues; does not use the graphical calculus; probably less suitable for a talk:
    The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer
    
  
  If you have questions regarding the topics, please contact Dr. Jürgen Koslowski.