Angebotene Arbeiten

In the group testing problem, the goal is to identify a small subset of defective items of size k within a larger set of items of size n, based on a number T of tests.

In the paper [1] the authors analyze doubly-regular random design for non-adaptive group testing. In particular, they consider setting with approximate recovery in linear regime, when the number of defectives is linear and equals k=pn. Approximate recovery means that it is allowed to make a mistake, as long as the probability that an element is classified incorrectly is lower than some fixed ε>0. There are two types of error: false-positive and false-negative. Define a false-positive rate (FPR) as the probability that a non-defective item(picked uniformly at random) is declared defective. False-negative rate (FNR) is defined as the probability that a defective item (picked uniformly at random) is declared non-defective.

The authors use DD (definitely defective) algorithm, which always has FPR=0. They evaluate a rate of a random code, generate with doubly-regular design. However, due to the properties of this designs, the graph of the rate depending on parameter p looks discontinuous. It suggests that their design is suboptimal and can be improved. Some of the possible approaches are to use different designs, such as Bernoulli design or design with a constant column weight. It is also possible to modify a doubly-regular design by considering different parameters s for submatrices X_1, ..., X_r (see paper [1] for details).

In this project it is suggested to improve the results of the paper [1] by considering one of the aforementioned designs.

[1] Tan, N., Tan, W., & Scarlett, J. (2022). Performance Bounds for Group Testing With Doubly-Regular Designs. arXiv preprint arXiv:2201.03745.

-knowledge of probability theory is required

-programming skills are desirable

In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the so-called federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.

Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.

The goal of this work is to design, implement and analyze coding- and information-theoretic solutions for privacy and security in federated learning.

• Coding Theory (e.g., Channel Coding)
• Information Theory
• Machine Learning Basics

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

One advantage can be gained by using pseudo randomness to generate both the input and the code itself.
Your task will be implementing the identification codes described in the attached pdf (an english translation of a paper published in russian in a russian journal) aiming at the fastest implementation and smallest collisions, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI from TUM and CeTI from TU Dresden, the latter having already some preliminary implementation of pseudo-random identification using various pseudo-random generators. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

The student attempt to study the deterministic identification capacity

of a DMC subject to power constraint and generalize it for the K-identification.

Basics of Information Theory and Channel Coding.

Familiarity with the fundamentals of Identification Theory

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

Your task will be implementing the identification codes described in

• https://ieeexplore.ieee.org/abstract/document/782144

aiming at the fastest implementation, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

In [1] we consider a short-reach fiber-optic link with a single photodiode at the receiver, which is a so-called direct detector (DD). The DD outputs a signal, propotional to the squared magnitude of its input. At first glance, this makes phase modulation challgenging. In [1] we showed that inter-symbol intereference (ISI) can be used to retrieve the phase. A suboptimal symbol-wise MAP detector was then proposed for phase retrieval. However, the detector exhibits a large complexity, which grows exponentially in the amount of ISI.

The task of the student is to efficiently approximate the MAP detector using a NN.  An appropriate NN type/structure needs to be selected. Finally, lower bounds on the achievable rates are computed to evaluate the performance of the NN and compare it to the MAP detector [1].

[1] D. Plabst et al., "Achievable Rates for Short-Reach Fiber-Optic Channels With Direct Detection," in Journal of Lightwave Technology, vol. 40, no. 12, pp. 3602-3613, 15 June15, 2022, doi: 10.1109/JLT.2022.3149574.

Machine Learning

Statistical Signal Processing

We are interested in computing upper bounds (on capacity) for frequency-selective channels with a memoryless nonlineary at the transmitter/receiver.

One application for these bounds are short-reach fiber-optic communication systems with a single photodiode at the receiver. The photodiode is a memoryless nonlinearity, as it produces an output that is proportional to the squared magnitude of the input signal.

A simple upper bound for the above model is given in [Sec. III D, 2].

Information Theory

Linear System Theory

A common assumption for the construction of error correcting codes is that errors occur independently.

However, in many applications errors are actually highly correlated.
Coding in the cover-metric considers correlated errors which occur as 2-dimensional burst errors.

Such errors can be corrected using rank-metric codes.
Originally Gabidulin codes were proposed for this.
In [1], low-rank parity check (LRPC) codes are introduced, which utilize a probabilistic decoding procedure.

The goal of the master thesis is to

• apply LRPC codes to the cover-metric

• derive expressions on the success probability of the decoding by modifying the existing results for the rank metric

• check these results using simulations

Depending on personal preference, this basic idea will be extended into different directions:

•  consider interleaved scenario as in [2]

• consider a modified construction, which utilizes the additional structure of cover-metric errors compared to rank-metric errors (cf. [3])

If you are interested, please write an email, then we'll discuss the details.

[1] Aragon, Gaborit, Hauteville, Ruatta, Zemor, "Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography", https://arxiv.org/abs/1904.00357

[2] Renner, Jerkovits, Bartz, "Efficient Decoding of Interleaved Low-Rank Parity-Check Codes", https://arxiv.org/abs/1908.10839

[3] Bitzer, Renner, Wachter-Zeh, Weger, "Generic Decoding in the Cover Metric", https://arxiv.org/abs/2205.12738

Channel coding

In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the so-called federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.

Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.

The goal of this work is to design, implement and analyze coding- and information-theoretic solutions for privacy and security in federated learning.

• Coding Theory (e.g., Channel Coding)
• Information Theory
• Machine Learning Basics

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

One advantage can be gained by using pseudo randomness to generate both the input and the code itself.
Your task will be implementing the identification codes described in the attached pdf (an english translation of a paper published in russian in a russian journal) aiming at the fastest implementation and smallest collisions, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI from TUM and CeTI from TU Dresden, the latter having already some preliminary implementation of pseudo-random identification using various pseudo-random generators. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

As part of an ongoing project with Huawei we are looking into quantum machine learning algorithms applied to decoding at the end of an optical fiber in the non-linear regime.

So far we have tried only the quantum version of k-mean clustering, however the goal is to test further quantum algorithms, in particular quantum support vector machines next, and their classical quantum-inspired counterpart.

The projects will involve reading the literature on quantum machine learning algorithms and quantum-inspired algorithms, find or come up with an implementation (this will involve the use of quantum libraries, in particular so far we have use qiskit), and benchmark the performance.

Knowledge of quantum mechanics or quantum information is highly recommended.

See the attached document, i.e., click on "Diese Seite als PDF öffnen".

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

Your task will be implementing identification with Goppa codes, aiming at the fastest implementation, and testing their performance in comparison to other current implementations. The reference articles for this implementation are:

• https://ieeexplore.ieee.org/document/1056879
• https://ieeexplore.ieee.org/document/1057344

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

Your task will be implementing the identification codes described in

• https://ieeexplore.ieee.org/abstract/document/782144

aiming at the fastest implementation, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

As part of the NewCom Project, new communication paradigms are investigated from an experimental perspective in order to construct proof-of-concept implementations that demonstrate the theoretical results obtained for Post-Shannon Communication schemes. In particular, this MSc thesis focuses on Identification Codes and their integration into a simulation environment where vehicular networks are modelled.

For this, the master student will first conduct a review of the state-of-the-art use cases for identification in the scientific literature and in form of patents, with an emphasis on V2X communications. By using an open-source V2X implementation based on LDR’s Simulation of Urban Mobility (SUMO) framework integrated with ns-3’s implementation of the ITS-G5 and LTE standards and conducting simulation in specific scenarios, the student will gain a first impression of the performance of the system using traditional transmission schemes. The integration of existing implementation of identification codes culminates this thesis, where KPIs will be defined in order to compare the advantages of using identification instead of transmission in the context of V2X communications.

Details about the C++ tools/libraries

The software used for the simulation of the vehicular network communication is ezCar2x

• https://www.ezcar2x.fraunhofer.de/en.html
• https://gitlab.cc-asp.fraunhofer.de/ezcar2x

which build on and integrates the NS-3 (network simulation) and SUMO (traffic simulation) libraries

• https://sumo.dlr.de/docs/index.html
• https://www.nsnam.org/

For the identification part and identification code based on Reed-Muller codes needs to be reimplemented (work in progress) from Python into C++ using the Givaro library

• https://github.com/linbox-team/givaro
• https://casys.gricad-pages.univ-grenoble-alpes.fr/givaro/

• Knowledge of communications engineering, mobile communications, wireless channel models, signal processing, and channel coding techniques (experience in LTE/5G cellular networks is a plus)

• Interest in novel communication concepts as well in their practical implementation

• Software experience: MATLAB, C++ and Python (experience with ns-3 or SUMO is a plus)

• Comfortable working with Linux operative systems and distributed version control tools (e.g., gitlab)

• Goal-oriented and structured work style

The goal of this project is to implement in Python/Sagemath the security functions (at least one of four) described in https://arxiv.org/abs/2102.00983
Sagemath contains libraries for mosaics, BIBDs, etc, that can be used for the project.

Motivation:
There are various types of security definitions.
The mutual information based types, in increasing order of security requirement are

1. Weak secresy asks that the average mutual information of the eavesdropper I(M:E)/n goes to 0 for a uniform message M (average here means averaged over the blocklength n, an additional average over M is implicit in the mutual information)
2. Strong secrecy asks that the total mutual information I(M:E) goes to 0,
3. Semantic security asks that the total mutual informaiton I(M:E) goes to 0 for any distribution of the message M (and thus in particular for all distributions that pick any of two chosen messages with 1/2 probabilty)

Then there are the almost-equivalent respective indistiguishablity types  of security requirements (below |P-Q|_1 is the statistical distance and Exp_M is expectation value over M)

1. average indistinguishability 1/n Exp_M | P_{E|M} - P_E |_1 for a uniform message M goes to 0 (again average refers over the blocklegth n, clearly there is also the average over M)
2. total indistiguishability Exp_M | P_{E|M} - P_E |_1 for a uniform message M goes to 0
3. indistinguishability |P_{E|m} - P_{E|m'}|_1 for any two messages m and m' goes to 0.

Each of the indistiguishabilities can also be written using KL digvergence instead of statistical distance, in which case the conditions are exactly equivalent to their mutual information versions.

Strong secrecy is the standard security requirement considered in information-theoretic security, while semantic security is the minimum requirement considered in computational security.
Information-theoretic (physical-layer) security differs from computational security in that the secrecy is guaranteed irrespective of the power of the adversary, while in computational security E is computationally bounded. Computational security also assumes that the message is at least of a certain length for the schemes to work, and thus if the message to be secured is too small it needs to be padded to a larger message.

In practice, information theoretic security is expensive, because the messages that can be secured can be only as long as the keys that can be generated. However, in identification only a very small part of the message needs to be secured, which in computational security triggers padding and thus waste, but on the other side makes information-theoretic security accessible and not so expensive.

At the same time, the security of identification implicitly requires semantic security. It has been known for a while that hash functions provide information-theoretic strong secrecy. However, because the standard for information-theoretic security has been strong secrecy, before https://arxiv.org/abs/2102.00983 no efficient functions where known to provide information-theoretic semantic security.
We need an implementation of these type of functions so that we can integrate information-theoretic security into our identification project.

This paper uses the partial transpose as a tool to derive upper bounds on device-independent QKD
https://arxiv.org/abs/2005.13511
In this project the goal is to try to generalize the above to the other tools like the reallignment criterion:
https://arxiv.org/abs/quant-ph/0205017
https://arxiv.org/abs/0802.2019

basics of quantum information/quantum formalism

Generalize semantic security of classical-quantum channels to infinite dimensional channel (not necessarily gaussian)

• [1] finite dimensional classical-quantum case
  https://arxiv.org/abs/2001.05719
• finite and infinite dimensional classical case
  https://arxiv.org/abs/1811.07798
• [this subpoint can be a project by itself] the finite dimesional case needs to be recast into smooth-max information (instead than Lemma 5.7 of [1]) as the classical case does, this paper proves properties of the smooth-max-inf in finite dimension that we would need for that
  https://arxiv.org/abs/2001.05719
• papers regarding the capacity for infinite dimensional channels
  http://arxiv.org/abs/quant-ph/9912067v1
  http://arxiv.org/abs/quant-ph/0408009v3
  http://arxiv.org/abs/quant-ph/0408176v1

quantum information theory

Asypmtotic continuity is a property in the form of inequalities (classically known also as inequalities of the reverse-Pinker type) that is necessary to prove upper bounds on operational capacities.

The (quantum) relative entropy (also known as quantum divergence and classically also known as Kullbackt-Leibler divergence), can be used to define various entanglment measures many of which have a proven asymptotic continuity.

Of particular interest are the restricted quantum relative entropies defined by Marco Piani (https://arxiv.org/abs/0904.2705), many of which satisfy asymptotic continuity (A.S.)

• https://arxiv.org/abs/quant-ph/9910002
• https://arxiv.org/abs/quant-ph/0203107
• https://arxiv.org/abs/quant-ph/0507126
• https://arxiv.org/abs/1210.3181
• https://arxiv.org/abs/1507.07775
• https://arxiv.org/abs/1512.09047

In the above there are maybe 2-3 different proof styles.
We can group the results in the above as follows:

• A.S. for entropy, conditional entropies, mutual information, conditional mutual information
• A.S. for relative entropies with infimum over states on the second argument
• A.S. relative entropies with infimum over state *and maximization over measurement channels*

The goal of the project is to generalize the last case to asymptotic continuity for relative entropies with infimum over state and maximization over *general* channels.

• Partial results toward this goal can be found in the appendix of my PhD thesis: http://web.math.ku.dk/noter/filer/phd18rf.pdf
• Such a result would have immediate applications to this paper: https://arxiv.org/abs/1801.02861

Possible new proof directions are

• using Renyi α-realtive entropies with the limit α->1
• using Kim's operator inequality from
  https://arxiv.org/abs/1210.5190
  to get an operator inequality looking like a reverse strong subadditivity (see https://www.youtube.com/watch?v=P3-xI1u1Y2s for a good overview and in particular at minute 31:20 for the reverse SSA)

Knowledge of quantum information is highly recommended/required.
Knowledge of matrix analysis will be a strong advantage.

relevant papers
https://arxiv.org/abs/1310.6043
https://arxiv.org/abs/1304.5944
https://arxiv.org/abs/1310.6045
https://arxiv.org/abs/1703.05876
https://arxiv.org/abs/1303.6357
background papers
https://ieeexplore.ieee.org/document/7509657

Knowledge of quantum theory as provided by the course Algorithms in Quantum Theory or similar

The goal of this work is to try to upper bound the device-independent distillable key in terms of locally restricted relative entropy of entanglement (an entanglement measure).

The following are relevant works/articles

• works toward even *a definition* of device independent distillable key
  https://arxiv.org/abs/2005.13511
  https://arxiv.org/abs/2005.12325
  https://arxiv.org/abs/1810.05627
• works relating distillable entanglement and distillable key to locally restricted relative entropy measures
  https://arxiv.org/abs/1609.04696
  https://arxiv.org/abs/1402.5927
• the first definition of restricted relative entropies
  https://arxiv.org/abs/0904.2705
• important properties of restricted relative entropies, and some overview of entanglement measures
  https://arxiv.org/abs/1210.3181
• my PhD thesis
  http://web.math.ku.dk/noter/filer/phd18rf.pdf

Strong background in quantum theory is required, preferably in quantum information theory, which is not covered by the course Algorithms in Quantum Theory

In this thesis, the student after studying deterministic identification will construct the explicit codes for certain channels.

Interested student are encouraged to contact me and send me a CV as well as all the academic transcripts and relevant courses that they have attended.

As well familiarity with the following is required:

Background in Information Theory and Channel Coding

Familiarity in fundamentals of Identification Theory

In [1] we consider a short-reach fiber-optic link with a single photodiode at the receiver, which is a so-called direct detector (DD). The DD outputs a signal, propotional to the squared magnitude of its input. At first glance, this makes phase modulation challgenging. In [1] we showed that inter-symbol intereference (ISI) can be used to retrieve the phase. A suboptimal symbol-wise MAP detector was then proposed for phase retrieval. However, the detector exhibits a large complexity, which grows exponentially in the amount of ISI.

The task of the student is to efficiently approximate the MAP detector using a NN.  An appropriate NN type/structure needs to be selected. Finally, lower bounds on the achievable rates are computed to evaluate the performance of the NN and compare it to the MAP detector [1].

[1] D. Plabst et al., "Achievable Rates for Short-Reach Fiber-Optic Channels With Direct Detection," in Journal of Lightwave Technology, vol. 40, no. 12, pp. 3602-3613, 15 June15, 2022, doi: 10.1109/JLT.2022.3149574.

Machine Learning

Statistical Signal Processing

We are interested in computing upper bounds (on capacity) for frequency-selective channels with a memoryless nonlineary at the transmitter/receiver.

One application for these bounds are short-reach fiber-optic communication systems with a single photodiode at the receiver. The photodiode is a memoryless nonlinearity, as it produces an output that is proportional to the squared magnitude of the input signal.

A simple upper bound for the above model is given in [Sec. III D, 2].

Information Theory

Linear System Theory

Capacity and capacity-achieving distributions are available for some memoryless channels. For the average-power constrained memoryless channel with additive white Gaussian noise, Shannon provided a closed form description of capacity. Closed form solutions for capacity also exist for some simple discrete memoryless channels (DMCs). In addition, numerical algorithms for calculating the capacity (and capacity-achieving discrete distributions) of general DMCs are available through the works of Arimoto and Blahut.

However, often wireless or fiber-optic channels of practical interest contain intersymbol interference (ISI), and the memory due to ISI can no longer be neglected. When considering discrete channel inputs, one may be interested in determining the capacity and capacity-achieving distribution for these ISI channels. In fact, discrete stationary Markov processes asymptotically achieve the capacity of finite-state ISI channels as the order of the Markov process goes to infinity.

An algorithm [1] for optimizing discrete Markov processes of a certain order M is presented to maximize the information rate between channel input and output. As the order of the Markov process increases, tighter lower bounds on capacity are obtained.

[1] A. Kavcic, "On the capacity of Markov sources over noisy channels," GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270), 2001, pp. 2997-3001 vol.5, doi: 10.1109/GLOCOM.2001.965977.

Further reading (if required):

[2] P. O. Vontobel, A. Kavcic, D. M. Arnold and H. -A. Loeliger, "A Generalization of the Blahut–Arimoto Algorithm to Finite-State Channels," in IEEE Transactions on Information Theory, vol. 54, no. 5, pp. 1887-1918, May 2008, doi: 10.1109/TIT.2008.920243.

[3] T. Lang, A. Mezghani and J. A. Nossek, "Channel-matched trellis codes for finite-state intersymbol-interference channels," 2010 IEEE 11th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2010, pp. 1-5, doi: 10.1109/SPAWC.2010.5670890.

Information Theory

We consider the problem of running a distributed machine learning algorithm on the cloud. This imposes several challenges. In particular, cloud instances may have different performances/speeds. To fully leverage the performance of the instances, we want to characterize their speed and potentially use the fastest ones. To explore the speed of the instances while exploiting them (assigning computational tasks), we use the theory of multi-armed bandits (MABs).

The goal of the research intership is to start by implementing existing theoretical algorithms [1] and possibly adapting them based on the experimental observations.

[1] M. Egger, R. Bitar, A. Wachter-Zeh and D. Gündüz, Efficient Distributed Machine Learning via Combinatorial Multi-Armed Bandits, submitted to IEEE Journal on Selected Areas in Communications (JSAC), 2022.

• Information Theory
• Machine Learning Basics
• Python (Intermediate Level)

In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the so-called federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.

Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.

The goal of this work is to design, implement and analyze coding- and information-theoretic solutions for privacy and security in federated learning.

• Coding Theory (e.g., Channel Coding)
• Information Theory
• Machine Learning Basics

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

One advantage can be gained by using pseudo randomness to generate both the input and the code itself.
Your task will be implementing the identification codes described in the attached pdf (an english translation of a paper published in russian in a russian journal) aiming at the fastest implementation and smallest collisions, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI from TUM and CeTI from TU Dresden, the latter having already some preliminary implementation of pseudo-random identification using various pseudo-random generators. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

In the work [1], we developed a method to analyze the dimension of quadratic-curve-lifted Reed-Solomon codes and its asymptotic behavior. The method gives tighter bound on the dimension compared to the estimation given in [2], which defines a more general class of lifted Reed-Solomon codes with regard to curves of higher degree. 

In this work, the student is expected to extended the method in [1] to the general class of codes in [2] to analyse the dimension and its asymptotic behavior.

As part of an ongoing project with Huawei we are looking into quantum machine learning algorithms applied to decoding at the end of an optical fiber in the non-linear regime.

So far we have tried only the quantum version of k-mean clustering, however the goal is to test further quantum algorithms, in particular quantum support vector machines next, and their classical quantum-inspired counterpart.

The projects will involve reading the literature on quantum machine learning algorithms and quantum-inspired algorithms, find or come up with an implementation (this will involve the use of quantum libraries, in particular so far we have use qiskit), and benchmark the performance.

Knowledge of quantum mechanics or quantum information is highly recommended.

See the attached document, i.e., click on "Diese Seite als PDF öffnen".

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

Your task will be implementing identification with Goppa codes, aiming at the fastest implementation, and testing their performance in comparison to other current implementations. The reference articles for this implementation are:

• https://ieeexplore.ieee.org/document/1056879
• https://ieeexplore.ieee.org/document/1057344

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.

The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.

Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.

It turns out that choosing good sets of funtions {T_i} is the same as choosing error-correction codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

Your task will be implementing the identification codes described in

• https://ieeexplore.ieee.org/abstract/document/782144

aiming at the fastest implementation, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

The coding will be in Python/Sagemath.
The working language will be in English.

Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.

This paper uses the partial transpose as a tool to derive upper bounds on device-independent QKD
https://arxiv.org/abs/2005.13511
In this project the goal is to try to generalize the above to the other tools like the reallignment criterion:
https://arxiv.org/abs/quant-ph/0205017
https://arxiv.org/abs/0802.2019

basics of quantum information/quantum formalism

In original scheme of identificaion via channels (Ahlswede and Dueck, 1989), a non-constructive method for coding for noiseless channel was studied. To address the explicit construction of identificaion codes, foremost Ahlswede and Verboven, 1991 provide a number theoretic approach based on the two successive prime number encryption. This method require the knowledge of first 2^n prime numbers for a block-length of n codeword. In this research internship, this method along with related prime number encryption tools and theorems would be investigated. Further, the extension of this scheme to a general DMC will be analyzed.

Interested student are encouraged to contact me and send me a CV as well as all the academic transcripts and relevant courses that they have attended.

As well familiarity with the Basics of following is required:

1. information/identification theory
2. channel coding
3. prime number theorem (Chebyshev)

It would be shown that under suitable formulations (preserving all salient features) the two problem of Identification (Ahlswede and Dueck, 1989) and Authentication (Simmons, G. J. 1984) are in essence very close to each other. This equivalency was conjectured first by M. S. Pinsker. In this research internship the student is expected to address this conjecture. Both problems must be studied separately and then the similar essence of them should be drawn out. In particular the identification codes and authentication codes along with theire relation will be investigated.

1. Background in Information Theory and Channel Coding
2. Familiarity with fundamentals of Identification Theory

References:

1. Simmons, G. J. 1984, “Message authentication: a game on hypergraphs,” Congressus Numer. 45:161-192.
2. Simmons, G. J. 1982, “A game theory model of digital message authentication,”  Congressus Numer., 34, 413-424
3. Simmons, G. J. 1985, “Authentication theory/coding theory,” in: Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, vol. 196, Springer-Verlag, Berlin, pp. 411-432.
4. E. Gilbert, F. J. MacWilliams and N.J. A. Sloane, 1974, “Codes which detect deception,” Bell System Tech. J., 53, 405-424.
5. R. Ahlswede and G. Dueck, “Identification via channels,” in IEEE Trans. on Inf. Theory, vol. 35, no. 1, pp. 15-29, Jan. 1989, doi: 10.1109/18.42172.
6. L. A. Bassalygo, M. V. Burnashev, “Authentication, Identification, and Pairwise Separated Measures”, Problems Inform. Transmission, 32:1 (1996), 33–39