Galactica test Ka’Chava

Suppose \(T\) is a function from \(V\) to \(W\). Let the “graph” of \(T\) be the subset of \(V \times W\) such that:

\begin{equation} graph\ T = \{(v,Tv) \in V \times W \mid v \in V\} \end{equation}

Show that \(T\) is a linear map IFF the graph of \(T\) is a subspace of \(V \times W\).

Review: A Linear Map

Recall that a function \(T: V \to W\) is called a linear map if it is a map that…

776 is a VC firm lead by Reddit cofounder Alexis Ohanian.

PERFECT-MATCHING

Given a bipartite graph \(G = \qty(U,V,E)\), is there a perfect matching (a one to one correspondence between \(U\) and \(V\) nodes)?

This is in both NP and coNP

But, PERFECT-MATCHING is in \(P\)

Yet, with a randomized algorithm, PERFECT-MATCHING can be solved in parallel time \(O\qty(\log^{2} n)\).

NP trivial

I hand you the matching

Not Hall’s Theorem

Sufficient: Suppose \(S \subseteq U\), consider \(N\qty(S) \subseteq V\), the neighborhood of \(S\) is \(|N(s)|< |S|\), then there is no perfect matching.