## Deterministic Identification Over the Binary Symmetric Channel

**Keywords: **

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

**Short Description: **

Identification without randomization over the binary symmetric channel (BSC) would be studied and investigated. Method of coding, decoding sets, type I/II errors and a closed-form solution of non-randomized (deterministic) 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 the Binary Symmetric Channel (BSC).

#### Prerequisites

- Familiarities with fundamental concepts of Information Theory, such as Entropy, Mutual Information, Hamming Distance, Rate, Probability of Error, The Binary Symmetric Channel etc)
- Familiarity with fundamentals of Identification Theroy

#### Supervisor:

Mohammad Salariseddigh