Given the need for ever higher performance, and the failure of CPUs to keep providing single-threaded performance gains, engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a ... more >>>

For a complexity class C and language L, a constructive separation of L \notin C gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every C-algorithm attempting to decide L. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>