We discuss original results from algorithmic complexity theory. A detailed list of topics can be found at the bottom of this page and will be presented at the initial meeting

The seminar will be held as a block seminar.

• date: April 26th, 16:00
• room: F2.425
• participation at the initial meeting is mandatory for this seminar

1. Complexity of counting problems and approximate counting: In counting problems we are not just interested in finding a single solution tom some problem instance, e.g. a satisfying assignment. Instead, we want to compete the number of solutions, e.g. the number of satisfying assignments. We consider two results in this area:
• Toda’s theorem that determines the complexity of counting problems with respect to the polynomial time hierarchy. Literature: Fortnow, Lance. "A Simple Proof of Toda's Theorem." Theory of Computing 5.1 (2009): 135-140.
• A result by Stockmeier that shows how to solve these problems approximately. Literature: Stockmeyer, Larry. "On Approximation Algorithms for #P." Journal of Computing14.4 (1985): 849-861.
2. Locality sensitive hashing: A hash function is called locality sensitive if for objects that are close (according to some distance measure) the probability of a collision is significantly larger then for objects that are far apart. Locality sensitive hashing has numerous applications to near neighbour search, coding problems and other areas. We consider two topics:
• An introduction to locality sensitive hashing and its application to near neighbour search. Literature: Har-Peled, Sariel, Piotr Indyk, and Rajeev Motwani. "Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality." Theory of Computing 8.1 (2012): 321-350.
• An application of locality sensitive hashing to coding problems. Literature: May, Alexander, and Ilya Ozerov. "On computing nearest neighbors with applications to decoding of binary linear codes." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2015.
3. Coding and lattice problems have numerous applications in communication and cryptography. But there complexity is only partially understood. In addition to the paper that applies locality sensitive hashing to coding problems we consider two results:
• The first one presents of very general algorithm to solve various problems from coding and lattice theory. Literature: Blum, Avrim, Adam Kalai, and Hal Wasserman. "Noise-tolerant learning, the parity problem, and the statistical query model." Journal of the ACM (JACM) 50.4 (2003): 506-519.
• The second considers the problem of bounded distance decoding in lattices and relates it to a variant of the shortest vector problem in lattices. Literature: Bai, Shi, Damien Stehlé, and Weiqiang Wen. "Improved reduction from the Bounded Distance Decoding problem to the unique Shortest Vector Problem in lattices." LIPIcs-Leibniz International Proceedings in Informatics. Vol. 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
4. Compressive sensing compressive sensing allows one to recover spares vectors from few random projections. It has numerous applications in communication, signal processing, informations theory. We look at a paper that looks at compressive sensing from the perspective of combinatorial optimization and approximation algorithms. Literature: Baraniuk, Richard G., et al. "Model-based compressive sensing." IEEE Transactions on Information Theory 56.4 (2010): 1982-2001.

Essay

Your essay should be 10 to 12 pages. It should be in the style of a scientific paper. If you like, you can use our LaTeX templates as a starting point. 

Talk

Your talk should last 1h including discussion (so you should plan to talk around 50-55 minutes). You will be able to show slides (bring your own laptop with HDMI or VGA or contact your supervisor). The format is 16:9. If you like, you can use one of our templates as a starting point.

First meeting

Here, we will present the available seminar topics and you will be asked to choose one.

Introductory talk

Here, we ask you to present an overview of your topic. This should include roughly 15 minutes where you explain the overall topic and your plans for the essay. In the other 15 minutes you should focus on some part of the topic and explain it formally; your supervisor will help you choose this topic (typically the proof of a simple but central theorem or the structure of a larger proof). Usually there is no need for you to prepare slides, but you should have a good plan of what you present on the whiteboard.

Essay structure

We ask you to turn in a skeleton version of your essay that contains section headings and 0 to 3 sentences per section explaining the section's goals. This is purely for your benefit so that you can get early feedback.

Essay version 1

We strongly recommend Version 1 of the essay to be "feature complete", i.e. everything you plan to have in the final essay should be included in this version. This is your chance to get comprehensive feedback on your work.

Exemplary talk by Prof. Blömer

Prof. Blömer will give a talk on a related topic in order to give you an example how your own talk should look like.

Essay version 2

The second version of the essay should incorporate the feedback given for version 1. We will read this version and give feedback again.

Talk structure

We ask you to turn in the structure of your talk. This can be in the form of slides (with sketched content) or textually. We will give feedback for this.

Talk

You will present your topic for all seminar participants and the supervisors. Your talk should last 1h including discussion (so you should plan to talk around 50-55 minutes).