  Polar codes are the latest breakthrough in coding theory, as they are the
first family of codes with explicit construction that provably achieve the
symmetric capacity of discrete memoryless channels. Ar{\i}kan's polar encoder
and successive cancellation decoder have complexities of $N \log N$, for code
length $N$. Although, the complexity bound of $N \log N$ is asymptotically
favorable, we report in this work methods to further reduce the encoding and
decoding complexities of polar coding. The crux is to relax the polarization of
certain bit-channels without performance degradation. We consider schemes for
relaxing the polarization of both \emph{very good} and \emph{very bad}
bit-channels, in the process of channel polarization. Relaxed polar codes are
proved to preserve the capacity achieving property of polar codes. Analytical
bounds on the asymptotic and finite-length complexity reduction attainable by
relaxed polarization are derived.
  For binary erasure channels, we show that the computation complexity can be
reduced by a factor of 6, while preserving the rate and error performance. We
also show that relaxed polar codes can be decoded with significantly reduced
latency. For AWGN channels with medium code lengths, we show that relaxed polar
codes can have lower error probabilities than conventional polar codes, while
having reduced encoding and decoding computation complexities.
