28 citations · 79 across the 28 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013★ 4 cited
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our a…
cs.CC2013★ 2 cited
On the Structure of Boolean Functions with Small Spectral Norm
Amir Shpilka, Avishay Tal, Ben lee Volk
In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is ). Specifically, we prove the follo…
cs.CC2013★ 1 cited
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
Michael A. Forbes, Amir Shpilka
Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are d…