2004-51: A $O(n^2)$ lower bound for swaping the order of $n$ input bits in planar boolean circuit

DIMACS TR: 2004-51

A $O(n^2)$ lower bound for swaping the order of $n$ input bits in planar boolean circuit

Author: Bin Tian

ABSTRACT When confined to a 2 dimensional world, many regular tasks become supprisingly hard. One example is to swap the order of $n$ input bits in a planar boolean circuit. Mario Szegedy conjectured that $O(n^2)$ gates are necessary. This paper gives a short proof.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-51.ps.gz

DIMACS Home Page