28 citations · 110 across the 12 of their papers we have counts for
Showing 2010Show all
3 papers · 1 filter
cs.DS2010★ 13 cited
Combinatorial Approximation Algorithms for MaxCut using Random Walks
Satyen Kale, C. Seshadhri
We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and…
cs.DS2010★ 10 cited
Is submodularity testable?
C. Seshadhri, Jan Vondrak
We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a…
cs.CC2010★ 1 cited
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
Nitin Saxena, C. Seshadhri
We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem…