A Remarkable Connection Between Communication Complexity and Circuit Depth
Lower Bounds Computer scientists are interested in proving lower bounds for their algorithms. Lower bounds are important because they give algorithm designers some metric about how efficient their algorithms can be. Computer scientists are usually interested in showing lower bounds for the running time of Turing Machines, which are computational models that emulate how our computers work (with some “small” overhead). Non-Uniform Circuits As is the usual motif in theoretical computer science, showing lower bounds for Turing Machines is considered difficult, and computer scientists have found it easier to analyse lower bounds in the setting of non-uniform circuits....