8 citations · 15 across the 3 of their papers we have counts for
3 papers
cs.CC2019★ 8 cited
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
Ankit Garg, Christian Ikenmeyer, Visu Makam +3
We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized su…
cs.CC2013★ 2 cited
Breaking the quadratic barrier for 3-LCCs over the Reals
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
We prove that 3-query linear locally correctable codes over the Reals of dimension require block length for some fixed, positive . Geometrically, this means th…
cs.CC2013★ 5 cited
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique
Raghu Meka, Avi Wigderson
Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantia…