Category Archives: Theoretical Computer Science

Simons Institute Summer Program on Cryptography

Today started the 2 month Summer Program on Cryptography at the Simons Institute in Berkeley. The Simons Institute for the Theory of Computing is an exciting new venue for collaborative research in theoretical computer science. The Institute typically hosts two concurrent programs per semester, where each is led by a small group of organizers who are recognized experts in their fields, and involves about 40-50 invited long-term participants (a mix of senior and junior researchers) who spend at least one month (usually longer) at the Institute.

The Cryptography program started today with an one week bootcamp that is intended to bring every participant on the same page regarding the recent developments in crypto. This day was extremely instructive because the lectures were not only very up to date but also very well taught, as opposed to the standard conference talk.

And what is really amazing is that the lectures were recorded and are now available online! So have a look at them!

 

Intersection of 3 Matroids

Inspired by Jack Edmonds and my Professor Dr. Rainer Schrader I decided to start doing research on intersections of 3 matroids. Matroids are really cool. Motivations come from Linear Algebra but if you want to keep it simple, you could just define it as follows:

Definition: A Matroid is a pair (E,F) where E is a finite set, F\subseteq 2^E and the following constraints hold:

  1. F is not empty
  2. X\in F, Y\subseteq X \Rightarrow Y\in F
  3. For X,Y \in F with |X|<|Y| there is a y \in Y\setminus X such that X\cup \lbrace y\rbrace \in F

Sets in F are called independent.

If we have got weights on the Elements and if the weight of a subset of E is defined as the sum of the weights of all its elements, we can use the greedy algorithm to find an optimum independent set in polynomial time. Of course we would therefor need a method which allows us to check whether a set is independent or not in polynomial time.

So what is the intersection of matroids?

Continue reading

Example for Reduction of the Shortest Path Problem to the Assignment Problem

Two days ago I published my blog entry My Solution to a Question from Jack Edmonds: Reduction of the Shortest Path Problem to the Assignment Problem. Here I will give an example to illustrate how the reduction works.

So let's start with the graph shown in figure 1.

graph1

Figure 1

We will construct the bipartite graph shown in figure 2. On the left is the set X, containing copies of all inner nodes and the node t. On the right is the set Y, containing a second copy of all inner nodes and the node s. For each edge (a,b) in the initial graph we add an edge from the node that corresponds to a on the right side to the node that corresponds to b on the left side. In addition to that, we link all pairs, which are the blue horizontal lines. Continue reading

My Solution to a Question from Jack Edmonds: Reduction of the Shortest Path Problem to the Assignment Problem

Image_37-m

Jack Edmonds

I am very happy that I had the chance today to attend a lecture held by Jack Edmonds, who is regarded as one of the most important contributors to the field of combinatorial optimization.

During his talk, Jack asked us to think about how to reduce the shortest path problem on directed graphs with rational costs on the edges to the assignment problem. I thought a bit about it and want to present my solution here.

First of all, let's recap what the shortest path problem and the assignment problem is. Continue reading

K-Opt and the Lin-Kernighan-Heuristic for the Traveling Salesman Problem

For the seminar "Selected Fields in Computer Science" offered by Prof. Dr. R. Schrader in summer 2013 at the University of Cologne I dealt with the concept of local search and presented the resulting K-Opt Algorithm for the NP-complete Travelling salesman problem that gives results with a quality determined by the choice of k.

Furthermore my seminar paper covered the Lin-Kernighan-Heuristic which is an in the real world often used heuristic algorithm for getting approximate solutions for the TSP that are usually > 95% of the optimum for real world data.

The seminar paper is in German and can be downloaded here: K-Opt and the Lin-Kernighan-Heuristic for the Traveling Salesman Problem (German)