Maximum Cut

greedy cut -> \(\frac{1}{2}\)-approximation

maximization approximation ratio \(\alpha\) \(\(\frac{SOL_{G}}{OPT_{G}} \geq \alpha\)\)

minimization ... \(\leq\)

best approximation now 0.878~ (SDP semi-definite programming)

unique games conjecture -> hard to do better.

如何设计的?

Random Cut

Theorem for uniform random cut \(E(S, T)\) in graph \(G\).

Then

De-randomization by conditional expectation.

Travel from root to leaf while mark the vertex on decision tree.

De-randomization by pairwise independence

pairwise independent \(X_{v}\)

mutual independent (\(\log n\)) -> pairwise independent (\(n\))

use Parity construction

enumerate all assignments of \(\log n\) bit.

Parity search.

Fingerprinting

answer equality.

AB=C ?

\(O(n^{\omega})\)

find a truth

Freivald's Algorithm 1979

pick a uniform random \(r \in \{0, 1\}^{n}\)

check \(A(Br) = Cr\)?

proof ???

each time \(\frac{1}{2}\)

Polynomial Identity Testing (PIT)

\(f, g \in F[x]\) of degree \(d\)

if \(f = g\) ?

f and g are black-box.

You can do evaluation.

Deterministic algorithm (polynomial interpolation)

Fundamental theorem of algebra

Randomized algorithm

pick a uniform random r

check if \(f(r) = 0\)

communication complexity

consider # of bits communicated

Yao 1979

Every deterministic communication protocol solving EQ communicates \(n\) bits in the worst-case.

use a small field like [p] \(Z_{p}\)

pick a prime \(p \in [n^2, 2n^2]\)

probability \(O(\frac{1}{n})\)

what about \(f \in F[x_{1}, \cdots, x_{n}]\) of degree d.

poly-time deterministic for PIT -> either NEXP != P/poly or #P != FP

means that w.h.p. there is a poly-time deterministic for PIT.

There are some unknown powerful weapons.

Vandermonde determinant (like a black block)

Schwartz-Zippel Theorem

\(f \neq 0 \rightarrow \mathrm{Pr}[f(x_{1}, \cdots, x_{n})=0] \leq \frac{d}{|S|}\)

# of any \(f \neq 0\) in any cube \(S^{n}\) \(\leq d |S|^{n-1}\)

application of Schwartz-Zippel

graph perfect matching

isomorphism of rooted tree

Reed-Muller codes

hardness vs randomness tradeoff

PCP

binary graph perfect matching

Hall's theorem (matching theorem!)

Hungarian method O(n^3)

Hopcroft-Karp algorithm \(O(m\sqrt{n})\)

Edmonds matrix

entries are variables (n*n not same as adjacent matrix)

perfect matching -> permutation

det(A) != 0 <=> exists a perfect matching

use Schwartz-Zippel to check \(det(A) = 0 ?\)

(Chistov's algorithm) to solve det(A) parallel!

Fingerprinting: hidden requisite: random function

another fingerprint （通信协议那里）

直接解读成为2进制表示，pick random prime \(p \in [k]\)

Karp-Rabin algorthm (pattern-matching)

Balls into Bins

birthday 单射

coupon collector 满射

occupancy 最大值

1-1 birthday

on-to coupon collector

pre-image size occupancy

Birthday Paradox

\(m > 57\) more than 99% two same birthday

use chain rule

Perfect Hashing

\(m = n^2\) Pr[no collision]

Simple Uniform Hash Assumption

H(|[n] - > [m]|) = nlogm

Break the assumption !

Universal Hashing (Universal hash family)

k-universal

Linear congruential model

Proposal Algorithm (Gale-Shapley algorithm)

Conwey Lattice theorem

Principle of Deferred Decisions

Poisson approximation

m balls into n bins \(\sim Bin(m, \frac{1}{n})\)

i.i.d. Poisson random variables \(Y_{1}, \cdots, Y_{n} \sim Pois(\frac{m}{n})\)

for \(k \in \mathbb{Z}^{+}\)

Coupon collector:

(Poisson approximation brings independence here)

So

(sharp threshold like monotonous properties in random graph)

像是水龙头调参！

Occupancy problems:

wtf...

Theorem: \(\forall m_{1}, \cdots, m_{n} \in \mathbb{N}\) s.t. \(\sum_{i=1}^{n}m_{i} = m\)

When \(m = n \ln n + cn\)

i.i.d. \(Y_{1}, \cdots, Y_{n} \sim Pois(\frac{m}{n})\) and \(Y = \sum_{i=1}^{n} Y_{i}\)

Theorem: \(Y_{1}, \cdots, Y_{n} \sim Pois(\frac{m}{n})\), \(\forall\) nonnegative function \(f\)

Occupancy problem:

\(\mathbb{E}\) becomes \(\mathbb{Pr}\) when \(f\) is an indicator.

Load Balancing

application:

HashTable's query time complexity

Distributed computation (namely load balancing )

\(Y_{i,j}\) iff ball \(j\) lands in bin \(i\).

Conclusion

\(m = \Theta(n)\), \(O(\frac{\log n}{\log \log n})\) whp

\(m = \Omega(n\log n)\), \(O(\frac{m}{n})\) whp

whp \(1 - \frac{1}{n}\) or \(1 - \frac{1}{n^{c}}\) usually c does not have influence on time complexity.

why such definition? usually polynomial false examples

wlp

wvlp(exp) whlp

\(C_{m}^{t} \leq \frac{em}{t}^{t}\)

Concentration

Chernoff Bounds (Herman Chernoff) much stronger thant Markov's inequality (linear descent)

convenient chernoff bounds (when \(\mathbb{E} \in \Omega(\log n)\), somehow linear)

Moment generating function + extended Markov's inequality

1.Use Markov's inequality on moment generating function

2.use independence of \(X_{i}\), (NOT linearity of expectation)

3.\(1+y \leq e^{y}\)

4.optimize \(\lambda\)

(More) Chernoff Bounds

negatively associated r.v.

Hoeffding's inequality

Hoeffding's lemma

\(X \in [a, b]\), \(\mathbb{E}[X]=0\)

Hoeffding's inequality in Action:

Randomized Quicksort

\(\Theta (n\log n)\) whp

proof: consider every path then union bound

Power of two choices

place the ball in the less loaded bin.

Power of d choices \(O(\log^{d}(n))\)? X!

Hashing and Sketching

based on random mapping

Count distinct elements

input: \(x_{1}, \cdots, x_{n} \in U = [n]\)

output: \(Z = |\{x_{1}, \cdots, x_{n}\}|\)

Data stream model: input date item comes one at a time.

Naive alg: \(\Omega(z\log N)\)

Sketch: (lossy) representation of data using space << Z

Is it possible? No

Lower bound: (Alon-Matias-Szegedy Godel prize): any deterministic(exact or approx) alg must use \(\Omega(N)\) bits of space in the worst case. (Intuition: communication complexity set disjoin)

must use both random and approx

Sketcher!: fu jian yi bo, yi quan chao ren

\((\epsilon, \delta)\)-estimator: \(\hat{Z}\)

PAC learning

insight: need both random and approx

Shakespeare: 30k words

(idealized)uniform hash function h: \(U \rightarrow [0,1]\)

\(\{h(x_{1}), \cdots, h(x_{n})\}\)

estimator:

First order approximation

\(\hat{Z} = \frac{1}{\min_{i} h(x_{i})} - 1\)

estimator variance is too large!

Markov's inequality

Corollary

\(f(x) \geq 0\)

Chebyshev's inequality

variance cannot be bounded.

找找是哪里贡献过去的

exchange of sum and variance needs only pair-wise independent.

超纲内容 Universal Hash family (Carter and Wegman 1979) Flajolet-Martin algorithm

k-universal

strong k-universal

Linear congruential hashing:

Degree-k polynomial in finite field with random coefficients

zeros(y) = max(i: 2^{i}|y) denote # of trailing 0's

一个函数能做到的最好的了

BJKST Algorithm

2-wise independent hash function \(h: [N] \rightarrow [M]\)

对理想化的 min sketch 的离散化.

定义一个随机变量, 写成 pair-wise 事件的和. (方便求期望和方差)

Frequency Moments

Data stream: \(x_{1}, x_{2}, \cdots, x_{n} \in U\)

for each \(x \in U\), define frequency of \(x\) as \(f_{x} = |\{i: x_{i} = x\}|\)

k-th frequency moments: \(F_{k} = \sum_{x \in U} f^{k}_{x}\)

Space complexity for \((\epsilon, \delta)\)-estimation: constant \(\epsilon, \delta\)

for \(k \leq 2\): polylog(N) AMS'96

for \(k > 2\): \(\theta(N^{1 - \frac{2}{k}})\) Indyk-Woodruff'05

Count distinct elements: \(F_{0}\)

optimal algorithm [Kane-Nelson-Woodruff'10] \(O(\epsilon^{-2}+\log N)\)

Frequency estimation

output estimator of \(f_{x}\) within additive error

multiplicative error 太难了

Heavy hitters: items that appears \(> \epsilon n\) times.

防止ddos

Data Structure for set

look CS168 Tool box!

bloom filter

数据库

bloom counter

count min sketch (CMS) 为什么这里只需要 2-universal 呢??? 感觉是因为扩大了内存

Concentration of Measure

概率论沉思录

Chernoff Bound

Bernstein Inequality

sum of independent trials

Sub-Gaussian Random variables

A centered(\(\mathbb{E}[Y] = 0\)) random variable Y is said to be sub-Gaussian with variance factor \(\nu\) if

Another interpretation of Chernoff-Hoeffding

The method of bounded differences

(McDiarmid's Inequality)

任何 lipschitz function 在 prod measure 都接近一个常函数

即使 alg 不随机, data 也可能随机.

Chernoff -> 1-Lipschitz

Hoeffding -> \((b_{i} - a_{i})\)-Lipschitz

心理史学(?)

consider # empty bins in Balls into Bins

is 1-Lipschitz.

Pattern Matching

k-Lipschitz

Sprinkling Points on Hypercube

iso pari metric

Harper's inequality (iso pari metric in Hamming Space)

telagrand inequality

McDiarmid's Inequality (worst-case)

For independent random variable \(X_{1}, X_{2}, \cdots, X_{n}\), if n-variate function \(f\) satisfies the Lipschitz condition: for every \(1 \leq i \leq n\),

for any possible \(i\) and \(y_{i}\).

Then for any \(t > 0\), \(\(\mathbb{Pr}[|f(x_{1}, \cdots, x_{n}) - \mathbb{E}f(x_{1}, \cdots, x_{n})| \geq t ] \leq 2e^{-\frac{t^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}}\)\)

This is a very powerful tool which can directly lead to Chernoff bound and Hoeffding bound.

Martingale

A sequence of random variables \(X_{0}, X_{1}, \cdots\) is a martingale if for all \(t>0\),

This expectancy is actually a function.

\(f(X_{0}, X_{1}, \cdots, X_{t-1})\)

e.g. Fair gambling game

Super-Martingale

Sub-Martingale

Martingale (Generalized Version) (filtration of a sequence of \(\sigma\)-algebra):

A sequence of random variables \(Y_{0}, Y_{1}, \cdots\) is a martingale

w.r.t. to \(X_{0}, X_{1}, \cdots\) if for all \(t \geq 0\),

\(Y_{t}\) is a function of \(X_{0}, \cdots, X_{t}\)

A fair gambling game:

\(X_{i}\): outcome (win/loss) of the \(i\)-th betting

\(Y_{i}\): capital after the \(i\)-th betting

Azuma's Inequality

For martingale \(Y_{0}, Y_{1}, \cdots\) (w.r.t. \(X_{0}, X_{1}, ...\)) satisfying:

for any \(n\geq 1\) and \(t > 0\):

Martingale rules: 如何必胜!

赌输了就加倍, 赢了立马跑路!

所以下注是有上限的...

(别想了别想了)

Doob Martingale

A Doob sequence \(Y_{0}, Y_{1}, \cdots, Y_{n}\) of an \(n\)-variate function \(f\) w.r.t. a random vector \((X_{1}, ..., X_{n})\) is:

Theorem:

The Doob sequence \(Y_{0}, Y_{1}, \cdots, Y_{n}\) is a martingale w.r.t. \(X_{1}, X_{2}, \cdots, X_{n}\).

Dimension reduction

Metric embedding

\(d(x, x) = 0\)

\(d(x, y) = d(y, x)\)

\(d(x, y) + d(y, z) >= d(x, y)\)

low-distortion: for small \(\alpha \geq 1\)

\(\forall x_{1}, x_{2} \in X\), \(\frac{1}{\alpha}d_{X}(x_{1}, x_{2}) \leq d_{Y}(\phi(x_{1}), \phi(x_{2})) \leq \alpha d_{X}(x_{1}, x_{2})\)

somehow approximation

spherical -> planar ? exists such \(\alpha\)?: NO

convert the problem from a hard metric space into a easy metric space. (find a low distortion mapping)

Euclidean embedding

Input: n points \(x_{1}, x_{2}, \cdots, x_{n} \in \mathbb{R}^{d}\)

Output: \(y_{1}, \cdots, y_{n} \in \mathbb{R}^{k}\)

usually k << d (the curse of dimensionality)

consider how small can k be

For what distance || . ||

The embedding should be efficiently constructible.

Johnson-Lindenstrauss Theorem 1984 (also check CS168Toolbox)

k = \(O(\frac{\log n}{\epsilon^{2}})\) optimal! (k is irrelevant to \(d\)!)

A linear transformation!

The probabilistic method: for random \(A \in \mathbb{R}^{k \times d}\)

We just need to prove this probability is greater than 0 in order to prove this theorem.

What kind of "random"?

Efficient construction of random \(A \in \mathbb{R}^{k \times d}\)

1. projection onto uniform random k-dimensional subspace; (Johnson-Lindenstrauss, Dasgupta-Gupta)
2. independent Gaussian entries; (Indyk-Motwani)
3. i.i.d. -1/+1 entries (Achlioptas)

independent Gaussian entries

For some suitable k = \(O(\frac{\log n}{\epsilon^2})\)

Entries of \(A \in \mathbb{R}^{k \times d}\) are choosen i.i.d. from \(\mathcal{N}(0, \frac{1}{k})\)

Here we use concentration of measurement

Chernoff bound for \(\chi^2\) distributions

---

How to generate \(k\) orthonormal unit vectors.

Uniformly and randomly generate unit vectors

Refusal sampling. Then Gram-Schmidt.

But how to generate unit vectors.

\(X = (X_{1}, X_2, \cdots, X_d)\) where \(X_i \sim \mathcal{N}(0, 1)\), then normalize.

unit => conditioned on

observation

=> random unit vector -> deterministic k-dimensional sub-space (like directly choose pre-k components)

---

Nearest Neighbor Search (NNS)

Metric space (X, dist):

Find the closest datapoint to input \(x\)

applications: pattern matching, database, bioinformatics

core: NNS

when dimension d is small: k-d tree, Voronoi diagram

One of stall and query must be the curse.

Hamming space \(\{0, 1\}^d\)

consider Hamming distance

when \(d \gg \log n\)

conjectured requires either super-poly(n) space or super-poly(d) time

cell-probe model Yao'81 (information theory)

decision tree interacts with a code

Currently SOTA(Yitong'08!) \(\(t = \Omega(\frac{d}{\log \frac{S}{nd}})\)\)

Blessing: randomization + approximation

Approximation Nearest Neighbor (ANN)

c-ANN (Approximation Nearest Neighbor) \(\(dist(x, y_i) \leq c \cdot \min_{1 \leq j \leq n} dist(x, y_j)\)\)

gap decision

(c, r)-ANN (Approximation Near Neighbor) return \(y_i\) that dist(\(x, y_i\))\(\leq c\cdot r\) if \(\exists y_j\) s.t. \(dist(x, y_j) \leq r\)

return "no" if \(\forall i, dist(x, y_i) > cr\)

either if otherwise (or further computation with arbitrary)

actually define r-ball and cr-ball

gap decision -> c-ANN

\(r_0 = D_{min}\)

\(r_k = \sqrt{c} \cdot r_{k-1}\)

\(r_{log_{c}(D_{max}/D_{min})} = D_{max}\)

\(\forall r, (\sqrt{c}, r)\)-ANN, return the first data \(y_k\)

PLEB (point location in eco box)

Why \(D_{min}\) and \(D_{max}\) are enough?

Hamming space (c, r)-ANN

Dimension reduction

(JLT ? open)

consider \(f: \{0, 1\}^{d} \rightarrow \{0,1\}^{k}\), \(k = O(\log n)\)

conserving the r-ball

then make an offline table ... (\(O(n)\))

\(A\in GF(2)^{k\times d}\) i.i.d. Bernoulli(p)

store all s-balls \(B_s(u) = \{y_i | dist(u, z_i) \leq s\}\) for all \(u \in \{0, 1\}^{k}\)

\(\forall x, y \in \{0, 1\}^d:\)

Then union bound \(\Rightarrow\) w.h.p.

two steps samplings

LSH (locality sensitive hashing) [Indyk-Motwani 1998]

A random \(h: X \rightarrow U\) is an \((r, cr, p, q)\)-LSH if \(\forall x, y \in X\):

Proposision

\(\exists\) an \((r, cr, p, q)\)-LSH \(h: X \rightarrow U\) $\Rightarrow $ \(\exists\) an \((r, cr, p^k, q^k)\)-LSH \(h: X \rightarrow U^k\)

Suppose there is \((c, cr, p^*, \frac{1}{n})\)-LSH.

Let \(q^k < \frac{1}{n}\)

independent trials \(\frac{1}{p^*}\)

use FKS hash

\(\rho = \frac{\log p}{\log q}\)

for Hamming space, randomly pick a bit \(i \in [d]\)

\(\rho = \frac{1}{c}\)

But optimal for Hamming space ...

Fourier transform log convex (left for homework)

Lovasz Local Lemma

k-SAT

SAT-solver

k-CNF(conjunctive normal form) exactly k variables

Determine a k-CNF whether is satisfiable

FAITH!

Clauses are disjoint: always satisfiable

\(m < 2^k\) is always satisfiable.

The probabilistic method

Draw uniform random

Bad event \(A^i\) Clause \(C_i\) is violated

\(\mathbb{P}[A_i] = 2^{-k}\)

then union bound ...

\(\mathbb{P}[\lor] \leq m2^{-k}\)

The probabilistic method fourth edition (Noga Alon, Joel H. Spencer, Erdos)

why not more powerful bound

Limited Dependency

Dependency degree \(d\)

each clause intersects $\leq $ \(d\) other clauses

"local" union bound ? \(d2^{-k} < 1\) ? NO

(LLL) \(e(d+1)2^{-k} \leq 1\)

or

\(4d2^{-k} \leq 1\)

LLL:

"Bad" events \(A_1, \cdot, A_m\), where all \(\mathbb{P}[A_j] \leq p\)

Dependency degree d:

each \(A_{i}\) is "depenedent" of \(\leq d\) other events

(each \(A_i\) is mutually independent of all except \(\leq d\) other events)

Dependency graph

Vertices are bad events \(A_1, \cdots, A_m\).

Each \(A_i\) is mutually independent of non-adjacent events.

这东西是唯一定义的吗?

Now consider CSP

independent random variables: \(X_1, X_2, X_3, X_4\)

bad events (defined on subsets of variables)

Variable framework

also there is the abstract framework.

\(\Gamma(c)\) neighborhood

\(A_1, \cdot, A_m\) has a dependency graph given by \(\Gamma(\cdot)\)

\(A_i\) is mutually independent of all \(A_i \notin \Gamma(A_i)\)

LLL

\(p = \max_{i} \mathbb{P}[A_i]\) and \(d = \max_{i}|\Gamma(A_i)|\)

留作业了

then

CSP

Variables: \(x_1, \cdots, x_n \in [q]\)

Constrains: \(C_1, \cdots, C_m\)

each \(C_i\) is defined on a subset \(vbl(C_i)\) of variables

\(C_i: [q]^{vbl(C_i)} \rightarrow \text{True, False}\)

Any \(x \in [q]^n\) is a CSP solution if it satisfied all \(C_1, \cdots, C_m\)

Examples: abab

Hypergraph coloring:

proper \(q\)-coloring of H:

\(f: V \rightarrow [q]\) such that no hyperedge is monochromatic

Theorem: for any k-uniform hypergraph H of max-degree \(\Delta\),

\(k \geq \log_{q}\Delta + \log_q\log_q\Delta + O(1)\)

Uniformly and independently color each \(v \in V\) a random color \(\in [p]\)

Bad event \(A_e\) for each hyperedge \(e\in E \subset C_v^k\): e is monochromatic

\(\mathbb{P}[A_e] \leq p = q^{1-k}\)

Dependency degree for bad events \(d \leq k(\Delta - 1)\)

Apply LLL

LLL(asymmetric case):

\(\exists a_1, \cdots, a_m \in [0, 1)\):

LLL(symmetric case) proof!

For asymmetric case:

conditioned probability. Induction

I.H.: \(\mathbb{P}[A_i | \bar{A_{j_{1}}} \cdots \bar{A_{j_{k}}}] \leq a_i\) holds for all smaller \(k\)

It never makes sense! Move the formulas around.

We want to find the exact solution.

What's next:

tight(er) LLL condition: Shearer's bound

tighter bounds when more (than just local dependency structure) are known: the probabilistic method beyond LLL.

Algorithmic LLL(The Moser-Tardos Algorithm)

"Bad" events \(A_1, \cdots, A_m\) in a probability space

Give an efficient alg:

find such a good sample \(\sigma \in \Omega\) avoiding \(\lor A_i\)

Pick the Variable framework for LLL (CSP with independent variables)

Moser-Tardos Algorithm:

draw independent samples of \(X_1, \cdots, X_n\);

while \(\exists\) a bad event \(A_i\) that occurs:

resample all \(X_j \in vbl(A_i)\);

Assume the oracles for draw random variables and check if \(A_i\) occurs.

Needs two oracles: 1. draw ind. samples of \(X_j\), check if \(A_i\) occurs

很容易构造出 \(A_i\) 是啥 NP-hard 什么的。

\(X_j\) 也不容易 sample 出来

Thm [Morse-Tardo'10]

terminates within \(\sum_{i=1}^{m}(1 - \frac{1}{1-\alpha_i}) = \frac{m}{d}\) samples a.k.a. linear time.

Random 随便的感觉 不一定有机会性 莫名其妙的 (???)

来自于一种无规律性(?)

not artificial!

Stochastic 才是真的有随机性

Execution Log (bold proof)

\(B\) of the M-T algorithm

\(B_1, B_2, \cdots, \in = \{A_1, \cdots, A_m\}\)

random sequence of resampled bad events.

to prove

use the random bits technique "resampling table"

Witness tree \(T(B, t)\): each node \(u\) with label \(A_{[u]}\), siblings have distinct labels

Witness tree is actually a DAG with partial order \(\leq\) maintaing levels.

Initially, \(T\) constains a single root \(r\) with \(B_t\)

for \(i = t - 1\) to 1 : if \(B_i \in \Gamma^+(A_{[u]})\) for some node \(u \in T\)

add child \(v \rightarrow\) deepest such \(u\), labeled with \(B_i\)

\(T(B, t)\) is the resulting \(T\)

Witness tree is the finite truncation of Universal covering.

Proposition: \(\forall s \neq t\), \(T(B, s) \neq T(B, t)\)

enumerate all the rooted trees ...

就想办法把\(\mathbb{E}\)放进来。比较常见的做法。

Lemma 1(coupling 耦合法): For any particular witness tree \(\tau\):

(其实是等于的)

proof:

consider the simulating on resampling table.

Example

Random graph

\(G(n, p_1)\), \(G(n, p_2)\) \(p_1 \leq p_2\)

To prove,

\(\mathbb{P}[p_1 \text{ connected}] \leq \mathbb{P}[p_2 \text{ connected}]\)

Following the coupling rule, fliping two coins.

Algorithm analysis ends after the coupling lemma...

Random tree (Galton-Watson process)

Grow a random witness tree \(T_A\) with root-label \(A\).

initially, $T_A$ is a single root with label $A$

for i=1,2,...:
    for every vertex u at depth i (root has depth 1) in T_A
    for every A_j \in \Gamma^{+}(A_[u]):
        add a new child v to u ind. with prob. a_j and label it with A_j;

stop if no new child added for an entire level    

Lemma 2. For any particular witness tree \(\tau \in \mathcal{T}_{A_{i}}\):

proof:

double counting ...

Moser's algorithm and Entropic proof

Moser's fix-it algorithm

Fix(\(C_i\))：

resample all variables in \(vbl(C_i)\);

while \(\exists\) violated \(C_j \in \Gamma^{+}(C_i)\):

Fix(\(C_j\));

Theorem:

\(d<2^{k-3}\) \(\Rightarrow\) total # of calls to Fix() is \(O(m\log m + \log n)\)

Incompressibility Principle

"Lossless compression of random data is impossible"

For any injective function Enc: \(\{0, 1\}^{N} \rightarrow^{1 to 1} \{0, 1\}^{*}\), for uniform random \(s \in \{0, 1\}^{N}\), for any integer \(l>0\),

听懵逼了