21 citations · 34 across the 4 of their papers we have counts for
3 papers · 1 filter
Towards an algebraic natural proofs barrier via polynomial identity testing
Joshua A. Grochow, Mrinal Kumar, Michael Saks +1
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if a…
Hellinger volume and number-on-the-forehead communication complexity
Troy Lee, Nikos Leonardos, Michael Saks +1
Information-theoretic methods have proven to be a very powerful tool in communication complexity, in particular giving an elegant proof of the linear lower bound for the two-party…
On the practically interesting instances of MAXCUT
Yonatan Bilu, Amit Daniely, Nati Linial +1
The complexity of a computational problem is traditionally quantified based on the hardness of its worst case. This approach has many advantages and has led to a deep and beautiful…