Complexity Lower Bounds

Principal Investigator: Meera Sitharam

Here I intend to continue my work in proving concrete (circuit, proof, communication) complexity lower bounds. Particularly using the slew of techniques that come out of the approximation framework (discussed under another project). Of immediate interest are the following. A geometry problem that would make significant progress towards the 2-level weighted threshold circuit lower bound, as well as a probabilistic communication complexity lower bound. The problem is of independent interest to combinatorial geometers as well. And a group of problems in the representation theory of the symmetric group Sn which have been useful for lifting certain non-constant proof complexity lower bounds to linear lower bounds (see recent paper).