
A $\textit{sigma partitioning}$ of a graph $G$ is a partition of the vertices
into sets $P_1, \ldots, P_k$ such that for every two adjacent vertices $u$ and
$v$ there is an index $i$ such that $u$ and $v$ have different numbers of
neighbors in $P_i$. The $\textit{ sigma number}$ of a graph $G$, denoted by
$\sigma(G)$, is the minimum number $k$ such that $ G $ has a sigma partitioning
$P_1, \ldots, P_k$. Also, a $\textit{ lucky labeling}$ of a graph $G$ is a
function $ \ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent
vertices $ v $ and $ u$ of $ G $, $ \sum_{w \sim v}\ell(w)\neq \sum_{w \sim
u}\ell(w) $ ($ x \sim y $ means that $ x $ and $y$ are adjacent). The $\textit{
lucky number}$ of $ G $, denoted by $\eta(G)$, is the minimum number $k $ such
that $ G $ has a lucky labeling $ \ell :V(G) \rightarrow \mathbb{N}_k$. It was
conjectured in [Inform. Process. Lett., 112(4):109112, 2012] that it is $
\mathbf{NP} $complete to decide whether $ \eta(G)=2$ for a given 3regular
graph $G$. In this work, we prove this conjecture. Among other results, we give
an upper bound of five for the sigma number of a uniformly random graph.

One of the phenomena that influences significantly the performance of
lowdensity paritycheck codes is known as trapping sets. An $(a,b)$ elementary
trapping set, or simply an ETS where $a$ is the size and $b$ is the number of
degreeone check nodes and $\frac{b}{a}<1$, causes high decoding failure rate
and exert a strong influence on the error floor. In this paper, we provide
sufficient conditions for exponent matrices to have fully connected
$(3,n)$regular QCLDPC codes with girths 6 and 8 whose Tanner graphs are free
of small ETSs. Applying sufficient conditions on the exponent matrix to remove
some 8cycles results in removing all 4cycles, 6cycles as well as some small
elementary trapping sets. For each girth we obtain a lower bound on the lifting
degree and present exponent matrices with column weight three whose
corresponding Tanner graph is free of certain ETSs.

A locally irregular graph is a graph whose adjacent vertices have distinct
degrees, a regular graph is a graph where each vertex has the same degree and a
locally regular graph is a graph where for every two adjacent vertices u, v,
their degrees are equal. In this work, we study the set of all problems which
are related to decomposition of graphs into regular, locally regular and/or
locally irregular subgraphs and we present some polynomial time algorithms,
NPcompleteness results, lower bounds and upper bounds for them. Among our
results, one of our lower bounds makes use of mutually orthogonal Latin squares
which is relatively novel.

One of the serious issues in communication between people is hiding
information from others, and the best way for this, is deceiving them. Since
nowadays face images are mostly used in three dimensional format, in this paper
we are going to steganography 3D face images, detecting which by curious people
will be impossible. As in detecting face only its texture is important, we
separate texture from shape matrices, for eliminating half of the extra
information, steganography is done only for face texture, and for
reconstructing 3D face, we can use any other shape. Moreover, we will indicate
that, by using two textures, how two 3D faces can be combined. For a complete
description of the process, first, 2D faces are used as an input for building
3D faces, and then 3D textures are hidden within other images.

A NotAllEqual (NAE) decomposition of a graph $G$ is a decomposition of the
vertices of $G$ into two parts such that each vertex in $G$ has at least one
neighbor in each part. Also, a 1inDegree decomposition of a graph $G$ is a
decomposition of the vertices of $G$ into two parts $A$ and $B$ such that each
vertex in the graph $G$ has exactly one neighbor in part $A$. Among our
results, we show that for a given graph $G$, if $G$ does not have any cycle of
length congruent to 2 mod 4, then there is a polynomial time algorithm to
decide whether $G$ has a 1inDegree decomposition. In sharp contrast, we prove
that for every $r$, $r\geq 3$, for a given $r$regular bipartite graph $G$
determining whether $G$ has a 1inDegree decomposition is $ \mathbf{NP}
$complete. These complexity results have been especially useful in proving $
\mathbf{NP} $completeness of various graph related problems for restricted
classes of graphs. In consequence of these results we show that for a given
bipartite 3regular graph $G$ determining whether there is a vector in the
nullspace of the 0,1adjacency matrix of $G$ such that its entries belong to
$\{\pm 1,\pm 2\}$ is $\mathbf{NP} $complete. Among other results, we introduce
a new version of {Planar 1in3 SAT} and we prove that this version is also $
\mathbf{NP} $complete. In consequence of this result, we show that for a given
planar $(3,4)$semiregular graph $G$ determining whether there is a vector in
the nullspace of the 0,1incidence matrix of $G$ such that its entries belong
to $\{\pm 1,\pm 2\}$ is $\mathbf{NP} $complete.

We propose BQTRU, a noncommutative NTRUlike cryptosystem over quaternion
algebras. This cryptosystem uses bivariate polynomials as the underling ring.
The multiplication operation in our cryptosystem can be performed with high
speed using quaternions algebras over finite rings. As a consequence, the key
generation and encryption process of our cryptosystem is faster than NTRU in
comparable parameters. Typically using Strassen's method, the key generation
and encryption process is approximately $16/7$ times faster than NTRU for an
equivalent parameter set. Moreover, the BQTRU lattice has a hybrid structure
that makes inefficient standard lattice attacks on the private key. This
entails a higher computational complexity for attackers providing the
opportunity of having smaller key sizes. Consequently, in this sense, BQTRU is
more resistant than NTRU against known attacks at an equivalent parameter set.
Moreover, message protection is feasible through larger polynomials and this
allows us to obtain the same security level as other NTRUlike cryptosystems
but using lower dimensions.

In this paper, we define two matrices named as "difference matrices", denoted
by $D$ and $DD$ which significantly contribute to achieve regular singleedge
QCLDPC codes with the shortest length and the certain girth as well as regular
and irregular multipleedge QCLDPC codes.
Making use of these matrices, we obtain necessary and sufficient conditions
to have singleedge $(m,n)$regular QCLDPC codes with girth 6, 10 and 12.
Additionally, for girth 6, we achieve all nonisomorphic codes with the minimum
lifting degree, $N$, for $m=4$ and $5\leq n\leq 11$, and present an exponent
matrix for each minimum distance. For girth 10, we provide a lower bound on the
lifting degree which is tighter than the existing bound. More important, for an
exponent matrix whose first row and first column are allzero, we demonstrate
that the nonexistence of 8cycles proves the nonexistence of 6cycles related
to the first row of the exponent matrix too. All nonisomorphic QCLDPC codes
with girth 10 and $n=5,6$ whose numbers are more than those presented in the
literature are provided. For $n=7,8$ we decrease the lifting degrees from 159
and 219 to 145 and 211, repectively. For girth 12, a lower bound on the lifting
degree is achieved.
For multipleedge category, for the first time a lower bound on the lifting
degree for both regular and irregular QCLDPC codes with girth 6 is achieved.
We also demonstrate that the achieved lower bounds on multipleedge
$(4,n)$regular QCLDPC codes with girth 6 are tight and the resultant codes
have shorter length compared to their counterparts in singleedge codes.
Additionally, difference matrices help to reduce the conditions of considering
6cycles from seven states to five states. We obtain multipleedge
$(4,n)$regular QCLDPC codes with girth 8 and $n=4,6,8$ with the shortest
length.

In this paper we give lower bounds on the size of $(a,b)$ elementary trapping
sets (ETSs) belonging to variableregular LDPC codes with any girth, $g$, and
irregular ones with girth 8, where $a$ is the size, $b$ is the number of
degreeone check nodes and satisfy the inequality $\frac{b}{a}<1$. Our proposed
lower bounds are analytical, rather than exhaustive searchbased, and based on
graph theories. The numerical results in the literarture for $g=6,8$ for
variableregular LDPC codes match our results. Some of our investigations are
independent of the girth and rely on the variables $a$, $b$ and $\gamma$, the
column weight value, only. We prove that for an ETS belonging to a
variableregular LDPC code with girth 8 we have $a\geq2\gamma1$ and
$b\geq\gamma$. We demonstrate that these lower bounds are tight, making use of
them we provide a method to achieve the minimum size of ETSs belonging to
irregular LDPC codes with girth 8 specially those whose column weight values
are a subset of $\{2,3,4,5,6\}$. Moreover, we show for variableregular LDPC
codes with girth 10, $a\geq(\gamma1)^2+1$. And for $\gamma=3,4$ we obtain
$a\geq7$ and $a\geq12$, respectively. Finally, for variableregular LDPC codes
with girths $g=2(2k+1)$ and $g=2(2k+2)$ we obtain $a\geq(\gamma2)^k+1$ and
$a\geq2(\gamma2)^k+1$, respectively.

A proper labeling of a graph is an assignment of integers to some elements of
a graph, which may be the vertices, the edges, or both of them, such that we
obtain a proper vertex coloring via the labeling subject to some conditions.
The problem of proper labeling offers many variants and received a great
interest during recent years. We consider the algorithmic complexity of some
variants of the proper labeling problems, we present some polynomial time
algorithms and $ \mathbf{NP} $completeness results for them.

LDPC lattices were the first family of lattices which have an efficient
decoding algorithm in high dimensions over an AWGN channel. Considering
Construction D' of lattices with one binary LDPC code as underlying code gives
the well known Construction A LDPC lattices or 1level LDPC lattices.
Blockfading channel (BF) is a useful model for various wireless communication
channels in both indoor and outdoor environments. Frequencyhopping schemes and
orthogonal frequency division multiplexing (OFDM) can conveniently be modelled
as blockfading channels. Applying lattices in this type of channel entails
dividing a lattice point into multiple blocks such that fading is constant
within a block but changes, independently, across blocks. The design of
lattices for BF channels offers a challenging problem, which differs greatly
from its counterparts like AWGN channels. Recently, the original binary
Construction A for lattices, due to Forney, have been generalized to a lattice
construction from totally real and complex multiplication fields. This
generalized Construction A of lattices provides signal space diversity
intrinsically, which is the main requirement for the signal sets designed for
fading channels. In this paper we construct full diversity LDPC lattices for
blockfading channels using Construction A over totally real number fields. We
propose a new iterative decoding method for these family of lattices which has
complexity that grows linearly in the dimension of the lattice. In order to
implement our decoding algorithm, we propose the definition of a parity check
matrix and Tanner graph for full diversity Construction A lattices. We also
prove that the constructed LDPC lattices together with the proposed decoding
method admit diversity order n1 over an nblockfading channel.

Low density parity check (LDPC) lattices are obtained from Construction D'
and a family of nested binary LDPC codes. We consider an special case of these
lattices with one binary LDPC code as underlying code. This special case of
LDPC lattices can be obtained by lifting binary LDPC codes using Construction A
lattices. The LDPC lattices were the first family of lattices which have
efficient decoding in high dimensions. We employ the encoding and decoding of
the LDPC lattices in a cooperative transmission framework. We establish two
efficient shaping methods based on hypercube shaping and Voronoi shaping, to
obtain LDPC lattice codes. Then, we propose the implementation of block Markov
encoding for oneway and twoway relay networks using LDPC lattice codes. This
entails owning an efficient method for decomposing fullrate codebook into
lower rate codebooks. We apply different decomposition schemes for oneway and
twoway relay channels which are the altered versions of the decomposition
methods of low density lattice codes (LDLCs). Due to the lower complexity of
the decoding for LDPC lattices comparing to LDLCs, the complexity of our
schemes are significantly lower than the ones proposed for LDLCs. The
efficiency of the proposed schemes are presented using simulation results.

LDPC lattices were the first family of lattices that equipped with iterative
decoding algorithms under which they perform very well in high dimensions. In
this paper, we introduce quasi cyclic low density parity check (QCLDPC)
lattices as a special case of LDPC lattices with one binary QCLDPC code as
their underlying code. These lattices are obtained from Construction A of
lattices providing us to encode them efficiently using shift registers. To
benefit from an encoder with linear complexity in dimension of the lattice, we
obtain the generator matrix of these lattices in "quasi cyclic" form. We
provide a lowcomplexity decoding algorithm of QCLDPC lattices based on sum
product algorithm. To design lattice codes, QCLDPC lattices are combined with
nested lattice shaping that uses the Voronoi region of a sublattice for code
shaping. The shaping gain and shaping loss of our lattice codes with dimensions
$40$, $50$ and $60$ using an optimal quantizer, are presented. Consequently, we
establish a family of lattice codes that perform practically close to the
sphere bound.

The regular number of a graph G denoted by reg(G) is the minimum number of
subsets into which the edge set of G can be partitioned so that the subgraph
induced by each subset is regular. In this work we answer to the problem posed
as an open problem in A. Ganesan et al. (2012) [3] about the complexity of
determining the regular number of graphs. We show that computation of the
regular number for connected bipartite graphs is NPhard. Furthermore, we show
that, determining whether reg(G) = 2 for a given connected 3colorable graph G
is NPcomplete. Also, we prove that a new variant of the Monotone NotAllEqual
3Sat problem is NPcomplete.

The lowdensity paritycheck (LDPC) lattices perform very well in high
dimensions under generalized minsum iterative decoding algorithm. In this work
we focus on 1level LDPC lattices. We show that these lattices are the same as
lattices constructed based on Construction A and lowdensity latticecode
(LDLC) lattices. In spite of having slightly lower coding gain, 1level regular
LDPC lattices have remarkable performances. The lower complexity nature of the
decoding algorithm for these type of lattices allows us to run it for higher
dimensions easily. Our simulation results show that a 1level LDPC lattice of
size 10000 can work as close as 1.1 dB at normalized error probability (NEP) of
$10^{5}$.This can also be reported as 0.6 dB at symbol error rate (SER) of
$10^{5}$ with sumproduct algorithm.

In this paper a new class of lattices called turbo lattices is introduced and
established. We use the lattice Construction D to produce turbo lattices. This
method needs a set of nested linear codes as its underlying structure. We
benefit from turbo codes as our basis codes. Therefore, a set of nested turbo
codes based on nested interleavers (block interleavers) and nested
convolutional codes is built. To this end, we employ both tailbiting and
zerotail convolutional codes. Using these codes, along with construction D,
turbo lattices are created. Several properties of Construction D lattices and
fundamental characteristics of turbo lattices including the minimum distance,
coding gain and kissing number are investigated. Furthermore, a multistage
turbo lattice decoding algorithm based on iterative turbo decoding algorithm is
given. We show, by simulation, that turbo lattices attain good error
performance within $\sim1.25 dB$ from capacity at block length of $n=1035$.
Also an excellent performance of only $\sim.5 dB$ away from capacity at SER of
$10^{5}$ is achieved for size $n=10131$.

In this work we establish some new interleavers based on permutation
functions. The inverses of these interleavers are known over a finite field
$\mathbb{F}_q$. For the first time M\"{o}bius and R\'edei functions are used to
give new deterministic interleavers. Furthermore we employ Skolem sequences in
order to find new interleavers with known cycle structure. In the case of
R\'edei functions an exact formula for the inverse function is derived. The
cycle structure of R\'edei functions is also investigated. The selfinverse and
nonselfinverse versions of these permutation functions can be used to
construct new interleavers.

The concept and existence of sphereboundachieving and capacityachieving
lattices has been explained on AWGN channels by Forney. LDPC lattices,
introduced by Sadeghi, perform very well under iterative decoding algorithm. In
this work, we focus on an ensemble of regular LDPC lattices. We produce and
investigate an ensemble of LDPC lattices with known properties. It is shown
that these lattices are sphereboundachieving and capacityachieving. As
byproducts we find the minimum distance, coding gain, kissing number and an
upper bound for probability of error for this special ensemble of regular LDPC
lattices.