Algorithms and Complexity Antoine Joux

News

19.01.2022

Time table for second presentations

The second presentations will be on February 2nd and 9th, according to the following schedule:

February 2nd, 2022:

10:00 : Polynomial multiplication / Quantum Fourier Transform --- Ferdinand Könneker

10:30 : Sort algorithms / Time complexity of different... Read more

The second presentations will be on February 2nd and 9th, according to the following schedule:

February 2nd, 2022:

10:00 : Polynomial multiplication / Quantum Fourier Transform --- Ferdinand Könneker

10:30 : Sort algorithms / Time complexity of different data structures --- Mohamed Genedy

11:00 : GCD algorithms / Factoring polynomials--- David Hares

11:30 : Primality testing / Factoring--- Simon Hasir

 

February 9nd, 2022:

10:00 : Graph algorithms / Network flow problem --- Felix Rausch

10:30 : P versus NP / Solving SAT instances --- Moritz von Zülow

11:00 : Computing with Circuits / Karp-Lipton Theorem--- Julian Dietz 

11:30 : Randomized / probabilistic algorithms --- Eric Petryka

Unless you have a extremely pressing obligation (contact me in that case), please make sure that you attend all presentations.

24.12.2021

In preparation for the second presentations

Dear Students,

There will be an information session for your second talks of the proseminar on January 5th, 2022, 10:00-10:30 in the same zoom room as usual.

Merry Xmas to all !

 

--------------------------------------------

Short Summary for those... Read more

Dear Students,

There will be an information session for your second talks of the proseminar on January 5th, 2022, 10:00-10:30 in the same zoom room as usual.

Merry Xmas to all !

 

--------------------------------------------

Short Summary for those who were not present at the meeting:

1) The presentations will take pale on Feb 2nd and Feb 9th (usual room)

2) You need to choose the exact topic you want to address (extension on the topic of your first presentation) and send it to me before Jan 12th by email

3) If you have strong preferences for Feb 2 or Feb 9, let me know so that I can account for it in the schedule

 

Also, due to the unfortunate current situation, it seems preferable to do the presentations virtually rather than in person.

 

23.11.2021

Time table for first presentations

The first presentations will be on December 8th and 15th, according to the following schedule:

December 8th, 2021:

10:00 : Computing with Circuits --- Julian Dietz 

10:30 : Randomized / probabilistic algorithms --- Eric Petryka [Cancelled]

11:00 => 10:30... Read more

The first presentations will be on December 8th and 15th, according to the following schedule:

December 8th, 2021:

10:00 : Computing with Circuits --- Julian Dietz 

10:30 : Randomized / probabilistic algorithms --- Eric Petryka [Cancelled]

11:00 => 10:30 : Sort algorithms  --- Mohamed Genedy

11:30 => 11:00 : Polynomial multiplication --- Ferdinand Könneker

 

December 15th, 2021:

 9:30 : Sort algorithms  --- Mohamed Genedy

10:00 : Graph algorithms --- Felix Rausch

10:30 : Primality testing --- Simon Hasir

11:00 : GCD algorithms --- David Hares

11:30 : P versus NP  --- Moritz von Zülow

12:00 : Randomized / probabilistic algorithms --- Eric Petryka

Unless you have a extremely pressing obligation (contact me in that case), please make sure that you attend all presentations.

08.11.2021

Exam registration

Dear Students,

I would like to remind you that you need to register for the exam of the proseminar, using your HISPOS access.

Please do it as soon as possible and contact studium if there is a difficulty with the registration.

I would like confirmation by... Read more

Dear Students,

I would like to remind you that you need to register for the exam of the proseminar, using your HISPOS access.

Please do it as soon as possible and contact studium if there is a difficulty with the registration.

I would like confirmation by email to me once you are registered.

 

Best,

Antoine Joux

28.10.2021

Preliminary Topic Assignation

Currently, the topics are pre assigned as follows:

Topic A : Computation models --- Unassigned

Topic B : P versus NP  --- Moritz von Zülow

Topic C: Randomized / probabilistic algorithms --- Eric Petryka

Topic D : Interactive proofs  ---... Read more

Currently, the topics are pre assigned as follows:

Topic A : Computation models --- Unassigned

Topic B : P versus NP  --- Moritz von Zülow

Topic C: Randomized / probabilistic algorithms --- Eric Petryka

Topic D : Interactive proofs  --- Unassigned

Topic E : Sort algorithms  --- Mohamed Genedy

Topic F : Computing with Circuits --- Julian Dietz 

Topic G : Graph algorithms ---  Felix Rausch

Topic H : GCD algorithms --- David Hares

Topic I : Polynomial multiplication --- Ferdinand Könneker

Topic J : Primality testing --- Simon Hasir

 

The final assignation will be done during our meeting on November 3rd, 10-12

 

Algorithms and Complexity

Description

This proseminar is meant to provide students an overview over foundational results in the area of algorithms and complexity. As a proseminar's primary purpose is to learn presentation skills, the seminar will feature two presentations from each student.

Depending on the Covid-19 situation, this proseminar will be organized via a visioconference system or on-site in block sessions.


After each presentation, the fellow students and lecturers will provide feedback on how to improve the presentation. This general feedback must then be taken into account for the second block of the course, where again each student will present.


For the first presentation, the student will present one of the proposed topics (based on one or two of the suggested references).

To not bore the audience, the second presentation will be on a related topic and based on a different reference document (book or research article).
This second reference will be chosen by the students (not from the initial list of references) and the relevance of the choice will be part of the grading of the second presentation.

The first presentations will count towards 30% of the overall grade, the choice of the second reference will count for 30% and the second presentation itself will count for the remaining 40% of the overall grade. Attendance in the proseminar meetings is mandatory. Because of the block structure, any absence needs a doctor's note as justification.

 

References
[1] Arora and Barak. Computational Complexity : A Modern Approach.
http://theory.cs.princeton.edu/complexity/book.pdf

[2] Introduction to Algorithms (3rd edition). Cormen, Leiderson, Rivest, Stein.

[3] Algorithms and Complexity. Wilf.  Internet edition available at https://www.math.upenn.edu/~wilf/AlgoComp.pdf

[4] Complexity of Algorithms. Gacs and Lovasz. Internet edition available at http://web.cs.elte.hu/~lovasz/complexity.pdf

[5] Lecture Notes on Computational Complexity. Trevisan. Internet edition available at https://people.eecs.berkeley.edu/~luca/notes/complexitynotes02.pdf

The references are available from the library.

https://www.infomath-bib.de/tmp/vorlesungen/info-advanced_algorithms_and_complexity.html

List of topics
Topic A : Computation models
[1] - Chapter 1
[4] - Chapter 2

Topic B : P versus NP
[1] - Chapter 2
[2] - Chapter 34
[3] - Chapter 5
[4] - Chapter 6
[5] - Chapter 1

Topic C: Randomized / probabilistic algorithms
[1] - Chapter 7
[2] - Chapter 5
[4] - Chapter 7
[5] - Chapter 5 and 6

Topic D : Interactive proofs
[1] - Chapter 8
[4] - Chapter 14
[5] - Chapter 13 (+14)

Topic E : Sort algorithms
[2] - Part II
[3] - Section 2.2

Topic F : Computing with Circuits
[1] - Chapter 6
[4] - Chapter 16
[5] - Chapter 4


Topic G : Graph algorithms
[2] - Part VI
[3] - Chapter 3 (+2.3)
[4] - Section 4.4

Topic H : GCD algorithms
[2] - Chapter 31
[3] - Chapter 4

Topic I : Polynomial multiplication
[2] - Chapter 30
[3] - Sections 2.5 and 2.6

Topic J : Primality testing
[2] - Section 31.8
[3] - Chapter 4
[4] - Section 7.3

 

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators