Talks
Fall 2018

# A Short List of Equalities Has Large Sign Rank

Friday, September 14th, 2018 3:30 pm4:00 pm

We exhibit a natural function F on n variables, that can be computed by just a linear sized decision list of Equalities', but whose sign rank is at least exp(n^(1/4)). This yields the following two new unconditional complexity class separations.