• Diese Seite als PDF öffnen.

An Introduction to Zero Error Identification Capacity

Keywords:
Identification via channels, identification with zero mis-rejection probability

Description

1. The zero error capacity (C_0) for transmission (Shannon 1956) is the least upper bound of rates at which it is possible to transmit information across the noisy channel with zero probability of error.
   
   
2. Similarly a zero error capacity for identification (Ahlswede et al 1996) is the least upper bound of rates at which it is possible to identify information across the noisy channel with zero probability of type I error (type II is still nonzero).
   
   
3. In Identification scheme (Ahlwsede and Dueck 1989) the receiver is not interested in to estimate the sent message but rather it wants to answer reliably to a binary question with Yes/No answers. The question is: Is the actual sent message is my desired message or not?
   
   
4. Identification codes (with randomized encoder) the code size scales doubly exponential in block length, n (e^e^(nc)) which apparently outperform the classic Shannon codes with a code size of only single order exponential (e^(nc)).
   
   
5. As preliminaries, we study the Shannon zero error capacity as its own merit for transmission and a relation to Shannon zero error capacity of a graph. Further, we study and understand the identification capacity of a noisy channel and at the end we aims to perceive the zero error identification capacity of a noisy channel (i.e. type I error = 0 and type II error is not zero).
   
   
6. On the way of understanding C_0id, we need to address the zero-error capacities for transmission such as Erasure, List and Detection. Finally we draw the link between C_0id and C_0.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Analysis of Identification for the Binary Symmetric Channel and a comparison to decoding problem

Keywords:
Identification, Binary Symmetric Channel, Communication Complexity

Short Description:
Problem of transmission and Identification over the BSC is investigated and analysed. Further it will be shown that identification would be easier than decoding problem in terms of minimum number of bits of communication

Description

Assuming that the communication channel between two processors P1 and P2 makes an error with probability ε>0, the identification problem is to determine whether P1 and P2 have the same n-bit integer. The decoding problem is for P2 to determine the n-bit integer of P1. For the latter problem we show that given any arbitrarily large constant λ>0, there exists an ε, 0<ε<1/2, for which no scheme requiring less than λn bits of communication can guarantee (for large n) any bound q<1 on the error probability. On the other hand, given any arbitrarily small constant γ>0 and any ε, 0<ε<1/2, the identification problem can be solved with (1+γ)n bits of (one-way) communication with an error probability bounded by c2^{-αn}, where c and α are positive constants. 

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Identification Without Randomization for the Discrete Memoryless Channel

Keywords:
Identification, Identification Without Randomization, Complexity of Distributive Computing, One-Way/Two-Way Probabilistic Communications

Short Description:
Identification without randomization for a general DMC would be studied and investigated. Method of coding, decoding sets, type I/II errors and a closed-form solution of non-randomized identification capacity will be considered and analysed.

Description

In theory of Identification introduced by Ahlswede and Dueck the perspective of  communications is changed from decoding to identification, i.e., the receiver is only interested to check whether or not his message was sent by transmitter. Ahslwede and Dueck proved that by means of local randomness (at encoder) they can achieve doubly exponential gain in code size which outperfrom substantially the classical scheme of Shannon transmission. (only exponential gain in code size). However, in many cases, there is no need to exploit the Randomization at encoder and thus the view of identification without randomization is introduced.

On the other hand to derive probabilistic complexity of models for one/two way communications for distributive computing (communication between two processors for determine copperatively value of an identification function) similar ideas were discussed. The student should understand those ideas and try to find the link between them and idea of Identification of Ahlswede and Dueck. Ideally the student attempt to derive forward or/and backward proof for non-randomized identification capacity of a general DMC.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Machine Learning Analysis and Optimization of High Frequency Mass IoT Queries to Get Most Current State

Description

1. CIRRANTiC is providing worldwide quality assured information about public chargepoints for electric vehicles. This includes not only so-called static information (Address, Plugtypes, Costs) but also dynamic occupancy information (currently available or occupied).
   
   
2. This dynamic state information is collected worldwide via REST calls to chargepoint operator provided APIs. Often, those requests are directed to 1 single chargepoint, thus we have to collect current state information for each chargepoint with a single request. Furthermore, to provide most up-to-date occupancy information, our backend system 'FUSiON' repeats this request cycle usually every 5 minutes.
   
   
3. The problem here is, that not only our backend is issuing hundred of thousands requests each day, but also the chargepoint operator backends have to answer these requests in time; + communication payload. But, since chargepoint usage frequency is very different from chargepoint to chargepoint (top usage are ~ 15 times a day for approx. 1 hour, low usages are ~ 3 times per week!). And/or it may vary depending on current time, weekday or season.
   
   
4. Here we see enormous potential in using machine learning algorithms to identify usage pattern classes and then to iterative (learning) adjust request frequency on this usage pattern.
   
   
5. The result would be a concept/document + implemented software/algorithm + analysis on saved traffic that will allow to optimise query frequency / pattern for chargepoints to the max as a basis for optimising our backend services. Selected API connections to chargepoint operators would be provided for this optimisation

Prerequisites

Supervisor:

Student

• Diese Seite als PDF öffnen.

Identifying Zeros of a Function

Keywords:
Identifikation, Identifying Zeros of a Function

Short Description:
Implementation of stochastic algorithms for estimation of zeros of a function. Furthermore, relation to identification of zeros of functions and theoretical bound is investigated.

Description

Implement an algorithm for Identification of zeros of a stochastically given function.
An study of Identification's fundamental concepts along with theorems for Identifying zeros of a function as well as analysing the algorithm and results must be presented and obtaind.

Prerequisites

Supervisor:

Student