Applied Algebra and Discrete Mathematics

Organizers:

In the autumn semester 2014 we organize an intensive course in Applied Algebra and Discrete Mathematics.
The aim is to present some relevant problems in this field, to understand the theoretical background and to implement and compare the computational tools which can deal with these problems.
The intensive course consists of two parts: a regular course Applied Discrete Mathematics (MV9990) at the University of Szeged and 2-weeks Winter School at the University of Würzburg.
We plan to present the problems and the theoretical background in the regular course and focus on the implementations in the Winter School.
The Winter School is open for everybody, the preparation can be made individually.

Part 1: Python and SAGE

Basic concepts of Information Theory and Error Correcting Codes
Noisy channel, Shannon's Theorem, block codes, linear codes.
Length, dimension, Hamming distance, weight, weight distribution, minimum distance,
Generating matrix, parity check matrix, syndrom decoding.
Weight distribution of random linear codes
Vladimir Blinovsky, Uri Erez, Simon Litsyn
Weight distribution moments of random linear/coset codes
Tests for random binary and q-ary codes
Reed-Solomon codes and Berlekamp-Massey decoding
S. Gao
A NEW ALGORITHM FOR DECODING REED-SOLOMON CODES
Implementation in GUAVA
LDPC codes and iterative belief propagation decoding
Bit error rate, package error rate, BER curve

Basic concepts of Complexity Theory
Graphs and algorithms
Automorphisms, isomorphisms, invariants
NP-complete problems and their solvers
3-SAT ➙ Wikipedia
Clique ➙ CLIQUER
Exact Cover ➙ Dancing Links (DLX)
Reformulating problems

Linear Programming relaxations
Semidefinite Programming and combinatorial optimization
Goemans-Williamson MAX CUT algorithm
Lovasz Theta function of small graphs
Integer Linear Programming, LLL algorithm
Groebner basis methods

Place:	University of Würzburg (Germany)
Date:	18/01/2015 – 29/01/2015, which includes 2 days of travel
Organizers:	Gábor P. Nagy (Szeged), Miklós Maróti (Szeged), Peter Müller (Würzburg)
Subjects:	Coding Theory, Cryptography, Groebner bases, Combinatorial Optimization, Linear and Semidefinite Programming
Main target group:	Master students in Mathematics
Prerequisites:	Linear Algebra, Calculus
Credits:	4 ECTS
Working language:	English, German
Registration fee:	EUR 100/person