21 citations · 34 across the 4 of their papers we have counts for
4 papers
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…
Clustering is difficult only when it does not matter
Amit Daniely, Nati Linial, Michael Saks
Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {\em that can be clu…