Let $G = (V_1, V_2, E)$ be a bipartite graph with $|V_1| = |V_2| = n$. Let $A=\{a_{ij}\}^{n}_{i,j=1}$ be the $n\times n$ matrix satisfying $$ a_{ij} =\begin{cases} 1 & \ if\ \{i,j\} \in E\\ 0 & if\ \{i,j\} \notin E \end{cases} $$Define the permanent of $A$ by: \begin{equation*} \operatorname{P...
The Wallace-Bolyai-Gerwein theorem states that any polygon can be formed from another by cutting it into a finite number of pieces and recomposing these by translations and rotations if and only if the two polygons have the same area. It is easy to see this: An equilateral triangle can be cut i...
Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with coefficients of size $O(poly(n))$ bits with promise that they are equal volume is there a scisso...
« first day (2341 days earlier) ← previous day next day → last day (1565 days later) »